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
  pop

1. A "push" and its corresponding "pop" occur in the same column.
2. Two "push" operations that occur in the same column correspond to two nodes at the same level in the recursion tree. For example, the root of the recursion tree is 7 and it has two children 6 and 5; these correspond to the "push 6" in Line 2 and the "push 5" in Line 32, that appear in the same column.