Fibonacci | Recursively or Not?

You’re probably all aware of the Fibonacci number sequence. Starting with 0 and 1, the next number is determined by the sum of the previous two numbers, so the sequence begins:

0, 1, 1, 2, 3, 5, 8, 13, 21, …

This is a mathematical concept, and it is defined by a “recurrence relation” (that’s a fancy way of saying that each number (or ‘term’) is generated from a previously calculated value), of:

Fn = Fn-1 + Fn-2

with “seed” or starting values of:

F0 = 0 and F1 = 1.

So, as you can imagine, this seems to lend itself nicely to programmatic recursion. Here’s a little program that will give you the 40th number in the Fibonacci sequence, using recursion:

#include <iostream>
using namespace std;

int fib(int i)
{
    if (i == 0)
    {
        return 0;
    }
    else if ((i == 1) || (i == 2))
    {
        return 1;
    }
    else
    {
        return (fib(i-1) + fib(i-2)); //here's our recursive call
    }
}

int main()
{
    int n = 40;
    cout << fib(n);
    return 0;
}

All very nice.

Next, I wrote the same program again, this time not using recursion:

#include <iostream>
using namespace std;

int fib(int x)
{
    int number1 = 0;
    int number2 = 1;
    int next = 1;

    for (int i = 0 ; i < x-1 ; ++i)
    {
        next = number1 + number2;
        number1 = number2;
        number2 = next;
    }
    return next;
}


int main()
{
    int n = 40;
    cout << fib(n);
    return 0;
}

Then I compiled both of them using a standard compile:

g++ -Wall fib_recursive.cpp -o fibr
g++ -Wall fib_normal.cpp -o fibn

And I timed the execution of them using the bash time command:

What’s the thing that jumps straight out at you here?

That’s right. How much slower it is to use the function recursively. We’ve gone from a barely detectable execution time, to a delay of almost one and a half seconds – that’s nearly 500 times slower than the non-recursive version.

What about optimisation?

Well, that’s what I thought. So next, I compiled them with the -O3 flag:

g++ -Wall -O3 fib_recursive.cpp -o fibr
g++ -Wall -O3 fib_normal.cpp -o fibn

And then I repeated the timing:

You can see that, pretty impressively, the recursive version is now running around 60% faster than it was. However, it is still around 180 times slower than the non-recursive version.

So, what can we learn from this?

You might be wondering if it is ever right to use recursion. Recursive functions in programs (written in C and C++) are almost always expensive (i.e. they take more time than non-recursive functions). If speed is your number one priority, you would do well to avoid recursion where possible.

However (and there’s always a ‘but’), recursion can often present itself more elegantly, and be potentially easier to understand and maintain, than the equivalent non-recursive code. This does however depend on your comfort level with dealing with recursion – so it’s not going to be easier to maintain and understand if recursion gives you a headache every time you think about it.

So, to takeaway here:

• Recursion is a mathematical concept that can be implemented programmatically
• Recursion in C/C++ is almost always slower than the equivalent non-recursive code
• Recursion can provide an elegant solution that is easier for other programmers to understand
• Whether this is true in the long run depends on the skill of the individual programmers who will be maintaining the program
• If speed is your number one priority, recursion is probably not the best solution
• Understanding recursion is nonetheless an important programming skill