Is there some way to speed up recursion by remembering child nodes?

Question

For example, Look at the code that calculates the n-th Fibonacci number:

fib(int n)
{
    if(n==0 || n==1)
        return 1;
    return fib(n-1) + fib(n-2);
}

The problem with this code is that it will generate stack overflow error for any number greater than 15 (in most computers).

Assume that we are calculating fib(10). In this process, say fib(5) is calculated a lot of times. Is there some way to store this in memory for fast retrieval and thereby increase the speed of recursion?

I am looking for a generic technique that can be used in almost all problems.

Answer 1

Yes your insight is correct. This is called dynamic programming. It is usually a common memory runtime trade-off.

In the case of fibo, you don't even need to cache everything :

[edit] The author of the question seems to be looking for a general method to cache rather than a method to compute Fibonacci. Search wikipedia or look at the code of the other poster to get this answer. Those answers are linear in time and memory.

**Here is a linear-time algorithm O(n), constant in memory **

in OCaml:

let rec fibo n = 
    let rec aux = fun
        | 0 -> (1,1)
        | n -> let (cur, prec) = aux (n-1) in (cur+prec, cur)
    let (cur,prec) = aux n in prec;;



in C++:

int fibo(int n) {
    if (n == 0 ) return 1;
    if (n == 1 ) return 1;
    int p = fibo(0);
    int c = fibo(1);
    int buff = 0;
    for (int i=1; i < n; ++i) {
      buff = c;
      c = p+c;
      p = buff;
    };
    return c;
};

This perform in linear time. But log is actually possible !!! Roo's program is linear too, but way slower, and use memory.

Here is the log algorithm O(log(n))

Now for the log-time algorithm (way way way faster), here is a method : If you know u(n), u(n-1), computing u(n+1), u(n) can be done by applying a matrix:

| u(n+1) |  = | 1 1 | | u(n)   |
| u(n)   |    | 1 0 | | u(n-1) |    

So that you have :

| u(n)    |  = | 1 1 |^(n-1) | u(1) | = | 1 1 |^(n-1) | 1 |
| u(n-1)  |    | 1 0 |       | u(0) |   | 1 0 |       | 1 |

Computing the exponential of the matrix has a logarithmic complexity. Just implement recursively the idea :

M^(0)    = Id
M^(2p+1) = (M^2p) * M
M^(2p)   = (M^p) * (M^p)  // of course don't compute M^p twice here.

You can also just diagonalize it (not to difficult), you will find the gold number and its conjugate in its eigenvalue, and the result will give you an EXACT mathematical formula for u(n). It contains powers of those eigenvalues, so that the complexity will still be logarithmic.

Fibo is often taken as an example to illustrate Dynamic Programming, but as you see, it is not really pertinent.

@John: I don't think it has anything to do with do with hash.

@John2: A map is a bit general don't you think? For Fibonacci case, all the keys are contiguous so that a vector is appropriate, once again there are much faster ways to compute fibo sequence, see my code sample over there.