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