Memoization

[hediet]

Consider this code:

    public int fib(int n) {
        if(n < 2) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }

We could easily introduce memoization on side-effect free functions from int to int:

    fib_last_result: int;
    fib_last_arg: int;
    fib_last2_result: int;
    fib_last2_arg: int;

    public int fib(int n) {
        if (n == this.fib_last_arg) return this.fib_last_result;
        if (n == this.fib_last2_arg) return this.fib_last2_result;

        if(n < 2) {
            return n;
        }
        int result =fib(n - 1) + fib(n - 2);

        fib_last2_result = fib_last_result;
        fib_last2_arg = fib_last_arg);
        fib_last_arg = n; // ensure it hasn't changed
        fib_last_result = result;

        return result;
    }

We could even improve this if self-modifying code is allowed.