Quiz 11, 11/8
The program FibonacciStack.java
simulates the pushing and popping of activation records that takes place during the execution of
the standard, recursive function to compute the nth Fibonacci number.
While this program simulates the system stack, it does not actually compute the nth Fibonacci number,
it just returns 0.
Modify the program so that in addition to what it is currently doing, it also does the following:
- Whenever it prints out "pop," it should also print out the Fibonacci number corresponding to the
activation record being popped. For example, for n = 4, we should see output such as:
push 4
push 3
push 2
pop: answer = 1
push 1
pop: answer = 1
pop: answer = 2
push 2
pop: answer = 1
pop: answer = 3
In this output, the line pop: answer = 2 states the fact that the activation record corresponding
to n = 3 is being popped and the 3rd Fibonacci number is 2.
- The function should actually return the nth Fibonacci number, rather than 0.