10.1. Fibonacci Sequence

This section discusses recursive, iterative, and dynamic programming ways of generating the Fibonacci sequence.

The Fibonacci sequence is a sequence of numbers generated as follows:

• $F_0 = 0, F_1 = 1$

• $F_n = F_{n-1} + F_{n-2}$ where $n \geq 2$

Abstraction

Let us create the Fibonacci interface that contains one abstract method:

public interface Fibonacci {
    int get(int k);
}

• L2: returns the $k$'th Fibonacci number.

Recursion

The followings demonstrate how to generate the Fibonacci sequence using recursion:

Let us create the FibonacciRecursive class inheriting Fibonacci:

public class FibonacciRecursive implements Fibonacci {
    @Override
    public int get(int k) {
        return switch (k) {
            case 0 -> 0;
            case 1 -> 1;
            default -> get(k - 1) + get(k - 2);
        };
    }
}

What is the worst-case complexity of this recursive algorithm?

Dynamic Programming

The followings demonstrate how to generate the Fibonacci sequence using dynamic programming:

Let us create the FibonacciDynamic class inheriting Fibonacci:

public class FibonacciDynamic implements Fibonacci {
    @Override
    public int get(int k) {
        return getAux(k, createTable(k));
    }
    
    private int[] createTable(int k) {
        int[] table = new int[k + 1];
        table[0] = 0;
        table[1] = 1;
        Arrays.fill(table, 2, k + 1, -1);
        return table;
    }

    private int getAux(int k, int[] table) {
        if (table[k] >= 0) return table[k];
        return table[k] = getAux(k - 1, table) + getAux(k - 2, table);
    }
}

• L7: creates a dynamic table represented by an array where the $i$'th dimension is to be filled with the $i$'th Fibonacci number.

• L16: returns the value in the dynamic table if exists.

• L17: fills in the dynamic table using recursion.

What is the worst-case complexity of this dynamic programming algorithm?

Iteration

For this particular task, the efficiency can be further enhanced using iteration. Let us create the class FibonacciIterative inheriting Fibonacci:

public class FibonacciIterative implements Fibonacci {
    @Override
    public int get(int k) {
        if (k < 2) return k;
        int f0 = 0, f1 = 1, f2;

        for (int i = 2; i < k; i++) {
            f2 = f0 + f1;
            f0 = f1;
            f1 = f2;
        }

        return f0 + f1;
    }
}

Benchmark

The followings show performance comparisons: