The Cost Of Recursion Is Not Always Expensive

During the communication with some friends today, I found that many people keep prejudices on recursion. Someone provides an example to show that recursion is much worse than loop. Here is his code:

int fib_recur1(int n) {
    if (n == 1)
        return 1;
    if (n == 2)
        return 1;
    return fib_recur1(n - 1) + fib_recur1(n - 2);
}

Here is the competing loop version:

int fib_loop(int n) {
    int n1, n2, i, tmp;
    n1 = 1;
    n2 = 1;
    for (i = 2; i < n; i++) {
        tmp = n2;
        n2 = n1 + n2;
        n1 = tmp;
    }
    return n2;
}

In this competition, the loop version is definitely much faster. But it doesn't mean that loop is better than recursion. It's the algothrim who make the result so different.

When you write the program in the same algothrim, the recursion version should look like this:

int fib_recur2_(int n1, int n2, int cnt, int target) {
    if (cnt < target)
        return fib_recur2_(n2, n1 + n2, cnt + 1, target);
    else
        return n2;
}

Let's wrap the interface with another function:

int fib_recur2(int n) {
    return fib_recur2_(1, 1, 2, n);
}

Let's run it:

int main() {
    printf("fib_recur1(10): %d\n", fib_recur1(10));
    printf("fib_loop(10): %d\n", fib_loop(10));
    printf("fib_recur2(10): %d\n", fib_recur2(10));
    return 0;
}

$ gcc a.c && ./a.exe
fib_recur1(10): 55
fib_loop(10): 55
fib_recur2(10): 55

The recursion version still consumes more memory (the calling stack) since C language do not support tail call optimization). But there should be no big difference on the speed.