4. The Fibonacci sequence is 0 1 1 2 3 5 8 13 21 . . .

Each Fibonacci number is the sum of the preceding two Fibonacci numbers. The sequence starts with the first two Fibonacci numbers and is defined recursively as fib(n)={0ifn=0,1ifn=1,fib(n−1)+fib(n−2)ifn<1.

Draw the call tree in the style of Figure 2.30 for the following Fibonacci numbers:

(a) fib(3)

(b) fib(4)

(c) fib(5)
For each of these calls, how many times is fib() called, including the call from main()? What is the maximum number of stack frames allocated on the run-time stack, not including the stack frame for main()?