The Fibonacci sequence is given by 1, 1, 2, 3, 5, 8, 13, 21, . The first two numbers are 1, and subsequent numbers are the sum of the previous two. If Fib(k) represents the kth number in the sequence, then we have Fib(1) = Fib(2) = 1, and Fib(k) = Fib(k-1) + Fib(k-2) for k > 2.

a) Consider the Fib and main functions below.

int Fib(int k) {

if (k <= 2) {

return 1;

} return Fib(k-1) + Fib(k-2);

}

int main() {

int m = 4;

int n = Fib(m);

return 0;

}

Draw the progression of the function call stack for the program. Each time there is a new function call or a function returns, there should be a depiction of the call stack. For example, if the first line of the main function is int m = 2;, then the first few call stacks may look like this:

Call stack Last function call Last function return Function parameters (for function that is called or returned) Function return value

main m = 2 n = ? Main N/A N/A N/A

Fib k = 2 main m = 2 n = ? Fib N/A k = 2 N/A

main m = 2 n = 1 N/A Fib k = 2 1

Note that in the last row of the above table, the function Fib called with parameter k = 2 has finished execution, and returns a value of 1. Fib with parameter k = 2 has been popped from the call stack, which is why it is not shown. Answer this question in the format of the 5-column table shown above. Make sure to keep track of all local variables in every function currently in the call stack.

b) Write a different version of Fib, called FibIter, that also returns the kth Fibonacci sequence, but only uses iteration. Use a loop; no recursion allowed in this part! The function prototype is as follows. Please use comments to help the reader understand your code.

int FibIter(int k) {

}