Could someone please explain how many calls will be stored in stack for the recursive method below and why? When is something stored in stack exactly? Apparently it is 49 calls, but I don't understand why. Thanks.
public static long fib( int n ){ // n = 50
if( n <= 1 )
return 1;
else
return fib( n - 1 ) + fib( n - 2 );
}
how many calls will be stored in stack for the recursive method below and why?
With an input of 50, the max amount of stack frames at any given moment, including the initial call to fib, will be 50. (So there will be at most 49 recursive calls stored on the stack at any given moment).
The reason there can be at most 50 stack frames is:
The initial call to fib(50) is 1 stack frame.
Then with this statement, return fib( n - 1 ) + fib( n - 2 );
the recursive call to fib on the left will execute first, putting fib(49) on the stack. We'll hit the return line again putting fib(48) on the stack. This will repeat until fib(1) is on the stack hitting the return 1; statement. This will return to fib(2) and allow the right recursive call to execute in the statement return fib( n - 1 ) + fib( n - 2 );.
To make long stories short, ALL the left recursive calls execute before even 1 right recursive call does. So it's easy to see you'll have fib(50), fib(49), ..., and finally fib(1) for the last recursive call, leading to a maximum of 50 stack frames when executing fib(50);.
When is something stored in stack exactly?
When you call a function, a stack frame is allocated, and after the function returns, the stack frame is deallocated. Even the function call for main is stored on the stack. However, stack frames may be optimized away, but that is a more advanced topic.
See this question I asked when I was a wee lad if you'd like to know more about stack frames being optimized away:
Does a stack frame really get pushed onto the stack when a function is called?
Additional Edit:
If you'd like to understand how the recursion is happening with a visual, place your finger at the top of the root, and trace around the outside of the tree going down the left side first:
Imagine a stack frame as a human worker that you send off to get you some information. Forget Fibonacci for a moment and think of an easier recursive formula, the sum.
int sum(int n) {
if (n == 1) {
return 1;
} else {
return sum(n - 1) + n;
}
}
sum(1) = 1
sum(2) = sum(1) + 2 = 1 + 2 = 3
etc...
Now imagine when you call sum(n), you send off a human to go find the results for you. He is not "finished" working until he gives you the results you asked for. However, he also needs to call sum(n - 1) which he can only do by putting another human to work. Now we have two humans working at once! The question you are asking is what is the max number of humans working simultaneously? If you include yourself, the answer is n for both the sum algo as implemented above, and for Fibonacci as you implemented it.
The number of calls to fib in the stack is the number of times fib needs to be called to evaluate fib(n).
fib(50) will have more than 49 calls to the fib function.
Take a smaller example. If you call fib(3), this will call fib(2) and fib(1). fib(2) will call fib(0) and fib(1). That is already 5 calls to fib for fib(3).
For a larger value of n, each call to fib(3) will be result in a total of 5 calls because the values are not stored anywhere. The only way for fib to evaluate is to call itself for two smaller values.
The Fibonacci sequence is a standard example of a bad use of recursion because the cost is exponential. I will let you work out exactly how many calls are needed.
