Tim Van Wassenhove

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