The logic behind writing a Fibonacci sequence in C-CodePudding

when returning (num-2) (num-1) if num > 1 , the program works but I don't get it.
when num is 0 write 0 and when num is 1 write 1.
when num is 2, so (2-2) (2-1), program will write 1
but when num is 3, so (3-2) (3-1), this equals 3 and the program write 2,
the same when num is 4, (4-2) (4-1) equals 5 and it writes 3 and not 5.
I just wanna understand the logic behind it as I am new to programing.

#include<stdio.h>
int fibonacci_series(int num);
int main()
{
   int count, c = 0, i;
   printf("Enter number of terms:");
   scanf("%d",&count);
 
   printf("\nFibonacci series:\n");
   for ( i = 1 ; i <= count ; i   )
   {
      printf("%d\n", fibonacci_series(c));
      c  ; 
   }
 
   return 0;
}
int fibonacci_series(int num)
{
   if ( num == 0 )
     return 0;
   else if ( num == 1 )
     return 1;
   else
     return ( fibonacci_series(num-1)   fibonacci_series(num-2) );
}

CodePudding user response：

With the recursive solution, the evaluation looks something like this (I’m going to use f as the function name just to save me some typing):

f(3) ==
f(2)          f(1) ==
f(1)   f(0)   f(1) ==
1      0      1 ==
2

f(3) calls f(2) and f(1). f(2) calls f(1) and f(0).

f(4) ==
f(3)                 f(2) ==
f(2)   f(1)          f(2) ==
f(1)   f(0)   f(1)   f(2) ==
f(1)   f(0)   f(1)   f(1)   f(0) ==
1      0      1      1      0 ==
3

f(5) ==
f(4)                               f(3) ==
f(3)   f(2)                        f(3) ==
f(2)   f(1)   f(2)                 f(3) ==
f(1)   f(0)   f(1)   f(2)          f(3) ==
f(1)   f(0)   f(1)   f(1)   f(0)   f(3) ==
f(1)   f(0)   f(1)   f(1)   f(0)   f(2)   f(1) ==
f(1)   f(0)   f(1)   f(1)   f(0)   f(1)   f(0)   f(1) ==
1   0   1   1   0   1   0   1 ==
5

Each f(n) calls f(n-1) and f(n-2) and adds their results.

This is why the recursive implementation of fibonacci is so inefficient - it winds up computing the same values multiple times (many, many times as n gets large). As a definition F_n = F_n-1 F_n-2 is nice and compact, but it’s not a good way to compute it.

CodePudding user response：

Given a num that's not 0 nor 1, the function calls itself:

fibonacci_series(num-1)   fibonacci_series(num-2)

So, when num is 2, the program does not do (2-2) (2-1) like you indicated in your question:

when num is 2, so (2-2) (2-1), program will write 1

Instead, substituting 2 as num, it actually does this:

fibonacci_series(2-1)   fibonacci_series(2-2)

To evaluate this, the function calls have to be made first before the .

fibonacci_series(2-1) is same as fibonacci_series(1) which gets you the value 1.

fibonacci_series(2-2) is same as fibonacci_series(0) which gets you the value 0.

Add 1 and 0 and that's the reason you get 1. It's just a coincidence that this is same as (2-2) (2-1).

There is no such coincidence going from num=3 onwards:

fibonacci_series(3-1)   fibonacci_series(3-2)

fibonacci_series(3-1) is same as fibonacci_series(2) and as observed above the value is 1.

fibonacci_series(3-2) is same as fibonacci_series(1) and you get value 1.

That's why the program writes 2 (which is actually 1 1) instead of 3 as you thought it should be.

You can do the same kind of tracing for num=4 and so on.