C speed up recursion

Question

int test(int n) {
    if(n <= 2)
    {
         return n;
    }
    return test(n-1) + test(n-2) + test(n-3);
}

Is there any way to speed it up without changing function declaration, when n becomes larger, it will take plenty of time to get the out put.

0.1.2.3.6.11.20

when n = 3, it should get the out put 0+1+2=3

when n = 5, it should get the out put 2+3+6=11

Answer 1

Imagine you want to find test(10). As a human, you will naturally find the algorithm to find that. Start making a table of results.

n = 0 -- result is 0
n = 1 -- result is 1
n = 2 -- result is 2

To continue the table, just use the last few numbers in the table:

n = 0 -- result is 0
n = 1 -- result is 1
n = 2 -- result is 2
n = 3 -- result is 3
n = 4 -- result is 6
...

The algorithm is "take last 3 numbers and add them, then write the answer in the new line in your table". This is easy to implement. Something like this:

n1 = 2
n2 = 1
n3 = 0
for i from 3 to n
    // Imagine you have everything up to i written on paper.
    // Here n1 is the last number, n2 is before that, n3 is before that.
    // Try to continue writing your table.

    result = n1 + n2 + n3

    // Now imagine you have written the result on paper.
    // What are the 3 last numbers now?

    n3 = n2
    n2 = n1
    n1 = result

    // Verify that in a debugger for better visualization.

// Now, after the loop is finished, n1 (the last number) is the correct answer.

return n1

Answer 2

If you want to keep using recursion you have to use memoization, or caching. The idea is, when calculating a result, store it for later.

I suggest having an array of sufficient size, say 100 entries (seeing that the numbers grow just a bit slower than 2ⁿ, this should be enough to represent any 64-bit number). Initialize it to 0:

int test(int n)
{
    static int cache[100] = {0};
    ...
}

After calculating a result, store it in the correct index:

int test(int n)
{
    ...
    result = ...
    cache[n] = result;
    return result;
}

But before applying the formula, check if the cache contains the result:

int test(int n)
{
    ...
    if (cache[n] != 0)
        result = cache[n];
    ...
}

Answer 3

Time to get out the tail recursion hammer

static int testk(int i, int n, int a, int b, int c)
{
   if (i == n) return a + b + c;
   return testk(i + 1, n, a + b + c, a, b);
}

int test(int n) {
    if (n < 2) return n;
    return testk(3, n, 2, 1, 0);
}

This is a direct translation of anatolyg's answer to tail recursion.

Answer 4

As you probably figured out, the reason your recursive solution is slow is because you recompute answers that had already been computed before.

This is why memoization works, and it allows you to maintain your top down algorithmic translation of the sequence as mathematically defined.

The disadvantage of complete memoization is that the table can be arbitrarily large. If O(1) time (at the cost of O(n) space) is not required, and O(n) time is sufficient, it is possible to perform the computation with O(1) space, and this has been illustrated in other answers as well.

All that is really required is that for any recursive calculation of test(n-1), the values for test(n-2) and test(n-3) should also be available. If you do not like creating a helper recursive function to track this information, then the below is an alternative that uses a single recursive function.

int test(int n) {

    typedef struct { int x[2]; } state;
    static const state init = { 0, 1 };
    static state last;

    if (n > 0) {
        last = init;
        return test(-n);
    }

    n = -n;
    if (n < 3) return n;

    // After the below call, last has test(n-2) and test(n-3)
    int x = test(-(n-1));
    int result = x + last.x[0] + last.x[1];
    last.x[0] = last.x[1];
    last.x[1] = x;
    return result;
}

Try it online!