Num of function calls in recursive Fibonacci routine
This is MAW 3.24:
If the recursive rotuine in Section 2.4 used to computeFibonacci numbers is run for N = 50, is stack space likely to run out?Why or why not?
unsigned long
Fib(int N)
{
if (N <= 1)
return 1;
else
return Fib(N1) + Fib(N2);
}
Let's first do an empirical experimentation. By running our test program numCalls and we can get the following output:
i Fib(i) numCalls
i = 0 1 1
i = 1 1 1
i = 2 2 3
i = 3 3 5
i = 4 5 9
i = 5 8 15
i = 6 13 25
i = 7 21 41
i = 8 34 67
i = 9 55 109
i = 10 89 177
i = 11 144 287
i = 12 233 465
i = 13 377 753
i = 14 610 1219
i = 15 987 1973
i = 16 1597 3193
i = 17 2584 5167
i = 18 4181 8361
i = 19 6765 13529
... snip ...
i = 50 20365011074 40730022147
We know that the Fibonacci numbers are defined by the following recurrence relation:
We define \(F(0) = F(1) = 1\). Now, we want to find out the number of recursive calls made to calculate \(F(n)\). We use \(G(n)\) to denote the number of calls made by the recursive program in calculating \(F(n)\). Let's examine the output above. We see that \(G(0) = G(1) = 1\) and to compute \(G(n)\) for arbitrary \(n\), we'll make an initial call, and then \(G(n1)\) calls to calculate \(F(n1)\) and \(G(n2)\) calls to calculate \(F(n2)\). Thus, we have the following recurrence relation for \(G(n)\):
Let's solve this recurrence relation by establish the relationship between \(F(n)\) and \(G(n)\) and then, we can get the closed form based upon the closed form of \(F(n)\).
Let's suppose that \(G(n)\) depends on \(F(n)\) in some way. In other words, \(G(n)\) is a function of \(F(n)\). Let's try linear form first:
Since we know that \(G(0) = G(1) = 1\) and \(F(0) = F(1) = 1\), then \ref{eq:3} becomes
Now let's plugin \ref{eq:3} into \ref{eq:2} and using the \ref{eq:1} and we have:
Now, our \ref{eq:3} becomes \(G(n) = 2F(n)  1\). That is, the number of function calls to calculate a Fibonacci number \(F(n)\) is \(2F(n)  1\).
Then the question asks about "is the stack space likely to run out?". This actually confuses
me because it seems like the author tries to indicate that there is a relationship between
the number of recursive calls and the actual space the program is going to take in call stack.
I have no clue so far. But, maybe we can find out the space of our Fib
routine
is going to take in call stack and how large the system call stack and we can compare the two
to get some insights.
We can use ulimit a
or ulimit s
to find out the size of stack that system allows:
$ ulimit a
... snip ...
stack size (kbytes, s) 10240
... snip ...
As you can see, the default stack size is 10 MB
. Let's see how large space our Fib
is going to use on stack: as of gcc 4.6
, there is an option fstackusage
to allow
us check the function max amount of stack use. Read more info here.
numCalls.c:17:1:Fib 48 static
numCalls.c:27:1:main 64 static
As you can see, Fib
only uses 48 bytes
and it's quite unlikely to drain out our stack space.
But, of course, the runing time is another thing. I mean it's going to be very slow to get the output
for \(N = 50\).
Future work

This paper mentions that \ref{eq:1} and \ref{eq:2} with their initial conditions respectively form secondorder Discrete Dynamical System (DDS). This offers some more mathematical insights. This actually reminds me equation 1.11 in Concrete Mathematics: A Foundation for Computer Science working on a generalized Josephus problem recurrence relation with a system of three equations and three unknown constant coefficients. In fact, this way of solving problem seems anywhere like differential equations, calculating moments in statistics, and so on. Quite interesting.

Lots of things can be said about call stack. In addition, "determine the amount of stack a program uses" is an interesting question that I may dig in the future.