CODEWITHSUNDEEP
recursionstackfibonacci
Dubby
Dubby

Reputation: 1144

Fibonacci Recursion : Return address?

Usually when there is a recursive call to a function then in the stack the return address points to the next instruction after the function call. But in Fibonacci code where will the return address point to? i.e. the next line or the remaining line of code after '+' operator? 

 int Fibonacci(int x) { 
   if (x == 0) return 0;  // Stopping conditions 
   if (x == 1) return 1; 
   return Fibonacci(x - 1)/*cond1*/ + Fibonacci(x - 2);/*cond2*/ 
 }

As far as my understanding of recursion goes, cond1 gets executed until a 0 or 1 value is returned (i.e. depth first on the leftmost branch of the recursion tree) and then only will cond2 get executed and so on. Is that right? What will the return address be saved as in stack(i.e EBP) when the control is performing Fibonacci(x-1) ?

        Fibonacci(3) 
           /  \ 
          /    \ 
         /      \ 
        /        \ 
       /          \ 
Fibonacci(2)    *   Fibonacci(1) 
      /     \               \ 
     /       \               \ 
    /         \               \ 
   /           \               \ 
Fibonacci(1) * Fibonacci(0)    1  
   |              | 
   |              | 
   |              | 
   |              | 
   1              0

Upvotes: 0

Views: 467

Answers (1)

Filipe Gonçalves
Filipe Gonçalves

Reputation: 21213

Yes, your understanding of recursion is right. It will work just like a DFS.

About the return address: recall that one line of code is not one instruction. In fact, a line of code can result in lots of instructions.

In this case, the compiler will generate code resembling something like:

a = call Fibonacci(x-1)
b = call Fibonacci(x-2)
c = add a, b
return c

So the return address for Fibonacci(x-1) is the address of the next instruction - in this case, the instruction that calls Fibonacci(x-2). Note, however, that most languages don't give you a guarantee on the order of evaluation of operands, all you know is that both operands of + are fully evaluated before the addition is performed. In effect, you could have this instead:

a = call Fibonacci(x-2)
b = call Fibonacci(x-1)
c = add a, b
return c

The point is, the return address of one of the recursive calls will be the address for the instruction for the 2nd call, and the return address of the 2nd call will be an ADD instruction.

Upvotes: 2

Related Questions