Tracing recursion for fibonacci series

Viewed 9781

I am trying to understand the recursion mechanism used for fibonacci series.

#include<stdio.h>
int fib(int n);
int main()
{
    int x, n;
    scanf("%d", &n);
    x = fib(n);
    printf("fibonacci number %d = %d\n", n, x);
    return 0;
}
int fib(int n)
{
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        return (fib(n -1) + fib(n - 2));
    }
}

Above is the code for the series. I can trace the program(for n=6) till the point where the first term in the return calls fib(1) and then returns 1. After that, I am kinda lost in tracing the execution. I have tried to understand it through stack diagrams but I am still confused. Can anybody help me with this? Also how can I trace the stack frame using gdb and see the variable values on stack frames?

Thanks

4 Answers
Related