# 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.

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

### 1 thought on “Fibonacci | Recursively or Not?”

1. 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;
}