# Tim Van Wassenhove

Passionate geek, interested in Technology. Proud father of two

What is a recursive function? It is a function where the value for input n is calculated as a linear combination of the previous 1, 2, …, n-1 function values. An example is the fibonacci function: f(n) = f(n-1) + f(n-2).

If we program this our first code would look like:

``````function fibonacci(\$n)
{
if (\$n < = 1) { return \$n; } return fibonacci(\$n-1) + fibonacci(\$n-2);
}
``````

It becomes clear that this is really inefficient. For example if we call fibonacci(3) the following function calls will be made:

fibonacci(3)

• fibonacci(2) – fibonacci(1) — fibonacci(0) –fibonacci(1)

We can optimize this function by implementing it as an iteration. We still have to calculate all the previous values, thus the time-complexity of this algorithm is O(n). Here is the code:

``````function fibonacci(\$n)
{
if (\$n < = 1) { return \$n; }
\$nmin2 = 0;
\$nmin1 = 1;
\$result = 0;
for (\$i = 2; \$i <= n; ++\$i) {
\$result = \$nmin1 + \$nmin2;
\$nmin2 = \$nmin1;
\$nmin1 = \$result;
}
return \$result;
}
``````

Time to take our math course and lookup a non-recursive function for fibonacci. Eureka, we have found one! The algorithm has constant time complexity. The proof for this function is can be found here.

``````function fibonacci(\$n)
{
\$denominator = pow((1+sqrt(5))/2, \$n) -- pow((1-sqrt(5))/2, \$n);
\$nominator = sqrt(5);
return \$denominator / \$nominator;
}
``````