12. Recursion Optimization

This of this as a quick pitstop and a precursor to pattern matching algorithms.

Memoization

With recursion, code generally produces many calls with similar input. Take, for example, the fibonacci sequence which without memoization runs in $O(2^n)$.

public int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

With memoization, this time complexity can be decreased by using some space complexity with an array.

// array is of size n
public int fibonacci(int n, int[] array) {
    if (n <= 1) {
        array[n] = n;
        return n;
    } else {
        if (array[n - 1] == 0) {
            array[n - 1] = fibonacci(n - 1);
        }
        if (array[n - 2] == 0) {
            array[n - 2] = fibonacci(n - 2);
        }
    }
    return array[n - 1] + array[n - 2];
}

Backtracking

If we proceed forward to a solution that is apparent there is no solution, then we can "undo" or backtrack the solution to a point where there exist an alternative solution. This is ideal for maze solving or the n-queens problem (demo). It does, however, require the developer to store the previous values, again trading space for time complexity.

Next Page →