/*
Fibonacci Sequence -inefficient way (try with N = 80)
-compute the nth fibonacci # using recursion
-draw the recursive tree to see why its inefficient

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 12

int fibo(int n)
{
     int res1, res2;
     printf("At call %d\n", n);
     if(n == 0) return 1;
     else if(n == 1) return 1;
        
     res1 = fibo(n-1);
     res2 = fibo(n-2);
     printf("At call %d, returned from %d with %d and %d with %d\n", n, n-1, res1, n-2, res2);
     
     return res1+ res2;
}

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