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