# 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

There’s another, a bit more awkward, recursion style that is almost as performant as your fib_normal.cpp. It’s kinda like an inside-out for loop (pardon the highly technical computer science terminology). 😎

#include

using namespace std;

int fib_recurse(int f0, int f1, int s1, int s2)

{

if (s1 == s2)

{

return f1;

}

else

{

return fib_recurse(f1, f0 + f1, s1 + 1, s2); // recursive call here

}

}

int fib(int i)

{

if (i == 0)

{

return 0;

}

else if ((i == 1) || (i == 2))

{

return 1;

}

else

{

return fib_recurse(0, 1, 1, i);

}

}

int main()

{

int n = 40;

cout << fib(n);

return 0;

}