Recursion is really that slow in C++?

Question

I know that recursion is fast (and even faster than iteration) in some languages. But I am talking about C++ (maybe C is also the same).

I am solving an online judge problem (not homework). I solved the problem using top down approach of dynamic programming. But I got TLE at last 2 cases. Then, I used bottom up approach and the solution was accepted. However, in this problem, I thought that top down should be faster as optimization can be done to skip some states not to calculate.

Problem statement: http://www.hkoi.org/training2004/files/need-for-speed.pdf

Code is as follow:

#include <cstdio>
#include <algorithm>

using namespace std;

int n, max_t; 
int num[51][50001];
int ts[50][50];
int ms[50];
int ls[50];

#ifdef RECURSION
int solve(int rn, int tleft)
{
    if (rn >= n)
        return 0;

    if (num[rn][tleft] != -1)
        return num[rn][tleft];

    int t;
    int max_num = solve(rn + 1, tleft);
    for (int i = rn; i < n; ++i)
    {
        t = ls[i];
        for (int j = 0; j < ms[i]; ++j)
        {
            t += ts[i][j];
            if (t > tleft)
                break;

            max_num = max(max_num, solve(i + 1, tleft - t) + j + 1);
        }
    }

    num[rn][tleft] = max_num;
    return max_num;
}
#endif

int main()
{
    scanf("%d %d", &n, &max_t);

    for (int i = 0; i < n; ++i)
    {
        scanf("%d %d", ls + i, ms + i);

        for (int j = 0; j < ms[i]; ++j)
        {
            scanf("%d", ts[i] + j);
        }

        sort(ts[i], ts[i] + ms[i]);
    }

    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j <= max_t; ++j)
        {
            #ifdef RECURSION
            num[i][j] = -1;
            #else
            num[i][j] = 0;
            #endif
        }
    }

    #ifdef RECURSION
    printf("%d\n", solve(0, max_t));
    #endif

    #ifndef RECURSION
    int t;
    for (int i = n - 1; i >= 0; --i)
    {
        for (int j = 0; j <= max_t; ++j)
        {
            t = ls[i];
            num[i][j] = num[i + 1][j];
            for (int k = 0; k < ms[i]; ++k)
            {
                t += ts[i][k];
                if (t > j)
                    break;

                num[i][j] = max(num[i][j], num[i + 1][j - t] + k + 1);
            }
        }
    }

    printf("%d\n", num[0][max_t]);
    #endif
}

As you can see in recursion version, there is a line max_num = max(max_num, solve(i + 1, tleft - t) + j + 1);. Since t is incremented by an integer not always = 1, some cases are skipped. However, in iterative version, many states that are useless are calculated.

I think that if iterative solution is faster, then recursion have to be much much much slower than iteration. Is my claim correct?

More than on the language, it depends on how you implement it. It is very easy to make a function that implements recursion in a completely useless or inefficient way. — Lee White, Apr 23 '14 at 05:55
There's no such thing as "recursion is slower than iteration". There's only "this particular recursive solution of this particular problem in this particular language with this particular compiler is slower" (again, than a **specific** iterative solution, on the same machine, in the same language, with the same compiler). — The Paramagnetic Croissant, Apr 23 '14 at 05:56

score 2 · Accepted Answer · edited May 23 '17 at 11:57

Performance optimization is a very complex field and you cannot generally narrow it down to simple advice such as "iteration is faster than recursion".

Counter examples are found very quickly: For instance, most of the fastest sorting algorithms (such as Quicksort) are usually implemented recursively.

In your case, doing some cheap operations too often may turn out to be much much faster in practice than doing complex checks to prevent them, for example as there are fewer cache misses. The only way to tell if one solution is superior to the other is a careful analysis using a profiler.

See this excellent answer (actually it is more like an article) covering branch prediction: Why is it faster to process a sorted array than an unsorted array?

score 0 · Answer 2 · answered Apr 23 '14 at 06:01

Theoratically iterative == recursive, granted that you use no compiler optimizations. The main difference is that the stack gets filled with function calls with the recursive solution. Recursion however, is most often easier to convert into a multi-threaded application. Also if you have a lot of if statements, the recursive solution helps to make the code more abstract, and you can switch to another type of recursion during the execution really easily (just call the function differently or call a completely different function).

Recursion is really that slow in C++?

2 Answers2