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(0) = 0

fib(1) = 1

fib(n) = fib(n-1) + fib(n-2) for n > 1

The C++ program that computes the Fibonacci number is as follows:

#include

using namespace std;

int fib (int n) {

if (n == 0) {

return 0;

}

else if (n == 1) {

return 1;

}

else {

return fib (n - 1) + fib (n - 2);

}

}

int main () {

int num;

cout << "Which Fibonacci number? ";

cin >> num;

cout << "The number is " << fib (num) << endl;

return 0;

}

Part 1) Draw the call tree for the Fibonacci number fib(5)

Part 2) How many time is fib called? ______________

Part 3) What is the maximum number of stack frames allocated on the run-time stack? (Do not include the main stack.) ___________