/*
Fibonacci Sequence - an efficient way
-compute the nth fibonacci # using recursion

recursive formula=> f(n) = f(n-1) + f(n-2)

n         0 1 2 3 4 5 6 7  8  9
f(n)      0 1 1 2 3 5 8 13 21 34

*/


#include <stdio.h>
#include <stdlib.h>

#define N 13

//saves the value of f(n-2) so only f(n-1) is computed
int fibval;

int fibo(int n)
{
     int res1, res2;
     printf("At call %d\n", n);
     
     //the base case n==0 is not needed when we save f(n-2)
     if(n == 1)
     {
          fibval = 1;
          return 1;
     }
        
     res1 = fibo(n-1);
     res2 = fibval; //get the value of fibo(n-2)
     
     printf("At call %d, returned from %d with %d and %d with %d\n", n, n-1, res1, n-2, res2);
     
     fibval = res1; //save the value of fibo(n-1) for the fibo(n+1) call
     return res1+ res2;
}

int main()
{
    printf("fibonacci sequence of %d is %d\n", N, fibo(N));
    system("pause");
}