Task 10.1 - Fibonacci Numbers

In this lab session the aim is to implement a stack data structure to replace recursive function calls. For this consider the follow simple program to calculate Fibonacci numbers recursively:

public class Fibonacci {
  public static long fib (int n) {
    if (n < 2) {
      return n;
    }
    return fib (n - 1) + fib (n - 2);
  }
  public static void main(String[] args) {
    if (args.length != 1) {
      System.err.println ("First argument is number of Fibonacci numbers printed");
    } else {
      int N = Integer.parseInt (args[0]);
      for (int l = 1; l <= N; l++) {
        System.out.println (l + ": " + fib (l));
      }
    }
    return;
  }
}

In principle recursive function calls can be replaced by putting a task on a stack and the process the tasks on the stack in a loop, until the stack is empty. The processing of a task can add an additional task on the stack to simulate recursion. This is how the problem has been solved for the H-tree example. As here there are return values, it is not as simple as to convert the recursion into an iteration using a stack frame simulation. There are various ways to deal with this, some more efficient than others.

Other recursive algorithms often also require the return values from the recursive calls. E.g. consider the minimax algorithm. Here you have a similar problem of creating an iterative version of the algorithm by suitably storing the return values without using too much memory. As in general you do not know the return values (you do for the Fibonacci numbers, so this is a simpler case than the general problem).