How to adress elements of a recursive function?

Question

Take a recursive function, say:

public static long rekurs(long n) {
    if (n == 0) {
        return 1;
    } else if (n == 1) {
        return 1;
    } else {
        return rekurs(n - 1)*(rekurs(n - 2)+4;
    }
}

When n=20, the function has to find all the values S(n) for n=2,...,19 first.
When I let n go from 20 to 21, it does the same thing again (plus finding S(20)).

Now I want to create an array, in which the found values S(n) for n=2,...,19 are filled into, so that the function for n=21 does not have to do the same thing again, but how do I get those elements?

---

This is the solution I figured out, it's a little bit different from the lecture example. The keyword that helped me is "dynamic programming".

import java.util.Arrays;

public class Bsp13 {

public static final int N = 0;
public static final int Ende = 20;

public static long[] schroe = new long[N + Ende + 1];

public static void main(String[] args) {

    schroe[0] = 1;
    schroe[1] = 1;

    for (int n = 2; n <= Ende + N; n++) {
        schroe[n] = ((6 * n - 3) * (schroe[n-1]) - (n - 2) * (schroe[n-2])) / (n + 1);
    }

    System.out.println(schroe[N]);
    System.out.println(Arrays.toString(schroe));
    System.out.println(schroe[N+Ende]);
    }
}

Answer 1

What you are trying to do is called dynamic programming. Basically it is bookkeeping in order to not compute subsolutions more than once. So basically, you need a mapping of n values to solution values. I would suggest you use a dictionary-like-datastructure for this task.

When a value for n needs to be computed, you first check whether the solution is in the dictionary, if yes you return the result. If not, you compute the result and put it into the dictionary.

Think about how you would initialize this dictionary and how you would pass it down to the recursive function calls.

Here's a lecture video on dynamic programming where the computation of Fibonnaci-numbers using dynamic programming is explained, which is very similar to what you are trying to do: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-19-dynamic-programming-i-fibonacci-shortest-paths/