Recursion to Iteration: Fibonacci Sequence

The Fibonacci sequence consists of these numbers {0, 1, 1, 2, 3, 5, 8, 13, 21, 34…}. Intuitively, one can see that the next number in the sequence will be a summation of the current number and the previous number. The Fibonacci sequence written recursively is:

public static int fibRecursive(int n) {
        if(n < 0){
            throw new IllegalArgumentException("n < 0");
        }
        if (n <= 1)
            return n;
        return fibRecursive(n - 1) + fibRecursive(n - 2);
}

Behind the scenes, each recursive function call gets pushed on the stack as a stack frame therefore we can emulate recursion calls using a stack:

public static int fibUsingStack(int n) {
        if(n < 0){
            throw new IllegalArgumentException("n < 0");
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(n);
        int sum = 0;
        while (!stack.empty()) {
            Integer next = stack.pop();
            if (next == 0 || next == 1) {
                sum += next;
                continue;
            }
            stack.push(next - 2);
            stack.push(next - 1);
        }
        return sum;
}

This is just a fun learning exercise which helps create understanding on how to convert recursive functions to iterative functions. It wouldn’t make sense to use a stack for this use case.