# Question: the fibonacci sequence is given by 1 1 2 3...

###### Question details

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) {

}