I mentioned in class that associated with each function call there is an activation record. This is essentially a block of memory that holds among other things (i) the arguments to the function, (ii) the local variables of the function, and (iii) a "return address." The activation records for all of the active functions are stored in the system stack. The activation record lives just long enough to allow a function to do its job; it is pushed onto the system stack when the function is called (becomes active) and it is popped when the function returns (becomes inactive). The LIFO ordering provided by the stack ensures that when the current activation record is popped we return to the function that called the current function.
Problem: This problem asks to simulate how the system stack grows and shrinks as a result of the sequence of function calls made during the standard recursive implementation of the Fibonacci function. To help in this, I have added some "pretty print" statements to the fibonacci function here: FibonacciPrint.java that shows the pushes and pops that were made to the system stack. For, say n = 7, this program produces the following output.
push 7 push 6 push 5 push 4 push 3 push 2 pop push 1 pop pop push 2 pop pop push 3 push 2 pop push 1 pop pop pop push 4 push 3 push 2 pop push 1 pop pop push 2 pop pop pop push 5 push 4 push 3 push 2 pop push 1 pop pop push 2 pop pop push 3 push 2 pop push 1 pop pop pop popThe indentations in the lines are also important and can be used the read the output as follows: