Tracing recursion for fibonacci series [closed]

Question

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

Answer 1

think of some random number and draw steps of execution(like a tree). i'd always use pen and paper to understand algorithm stuff. and also, always try to break down the whole program to each tiny logic and make sure you understand each one of them. I drew this diagram for you.i'm sorry for being such a horrible artist.

Answer 2

To understand this, I renamed your fib fnction to fibonacci. Now suppose user enters 3 then the recursive call can be understand as (> is for call and < is for return):

> fibonacci(3)
|   > fibonacci(2)
|   |   > fibonacci(1)
|   |   < 1
|   |   > fibonacci(0)
|   |   < 0
|   < 1
|   > fibonacci(1)
|   < 1
< 2

Which can be understand more in a more clear way by block diagram¹.

---

_{1. Taken from C how to program by Deitel.}