CODEWITHSUNDEEP
c++
Stark
Stark

Reputation: 19

How does recursion get previous values?

I'm in the basic of the basic of learning c++, and ran into an example of recursion that I don't understand. The equation is for Fibonacci numbers, and is shown below:

int fibo(int f)
{
    if (f < 3)
    {
        return 1;
    }
    else
    {
        return fibo(f - 2) + fibo(f - 1);
    }
}

How does the "else" statement work? I know that it adds the two previous numbers to get the current fibbonacci number, but how does it know, without any prior information, where to start? If I want the 7th fibonacci number, how does it know what the 6th and 5th numbers are?

Upvotes: 1

Views: 1110

Answers (2)

giusti
giusti

Reputation: 3538

A recursive function will call itself as many times as it needs to compute the final value. For example, if you call fibo(3), it will call itself with fibo(2) and fibo(1).

You can understand it better if you write down a tree representing all the function calls (the numbers in brackets are the return values):

       fibo(3) [1+1]
          |
    .--------------.
    |              |
fibo(2) [1]    fibo(1) [1]

For fibo(7), you will have multple calls like so:

                             fibo(7) [fibo(6) + fibo(5)]
                                |
              .-----------------------------------------------.
              |                                               |
           fibo(6) [fibo(5) + fibo(4)]                      fibo(5) [fibo(4) + fibo(3)]
              |                                               |
     .---------------------------------.                     ...
     |                                 | 
fibo(5) [fibo(4) + fibo(3)]        fibo(4) [fibo(3) + fibo(2)]
     |                                 |
    ...                               ...

Each recursive call will execute the same code, but with a different value of f. And each recursive call will have to call their own "editions" of the sub-cases (smaller values). This happens until everyone reaches the base case (f < 3).

I didn't draw the entire tree. But I guess you can see this grows very quick. There's a lot of repetition (fibo(7) calls fibo(6) and fibo(5), then fibo(6) calls fibo(5) again). This is why we usually don't implement Fibonacci recursively, except for studying recursion.

Upvotes: 1

Hemang Nakarani
Hemang Nakarani

Reputation: 107

In this given equation, It will go deeper in the root. When you have given Value 7 initially, it will go to function itself to get value of 7-2 = 5 and 7-1=6, still its has not value of 5 and 6. so further it will decrease value of 5 to 3 and 4 and 6 to 5 and 4. at the end when f is less then 3 it will return value 1. something like that after getting root values it will sum up those values to get total answer.

Upvotes: 4

Related Questions