Recursion

Some concepts just have to click. You stare at it for a while (or not) and then suddenly you see it. And what has been seen cannot be unseen. Recursion is one such concept; once you understand it you see it everywhere. Now, I don’t mean your two-facing-mirrors kind of recursion – I’m talking about programming, of course. Read on for more about one of the coolest concepts in the book.

Ok here’s the lamest definition for recursion I’ve come across, but it does work really well:

Recursion: see recursion.

I can understand if that doesn’t tell you too much, so let me try again. Recursion means that a process or function or other sort of code block calls itself. For a function to be recursive it needs to have a ‘base case’ and a ‘step’, or a default return value for one or more situations and a calculation for all others. Every call to a recursive function is either a base case or a step that will eventually lead to the base case.

Recursion tends to be a little bit more difficult than iteration, or ‘normal programming’. For and while loops are an integral part of iterative programming. Iteration is easy to follow, because the entire code execution is in the same block and there is no stepping in and out the same code on a different level. But once you get it, once recursion clicks for you, you’ll deeply love it.

Example

Alright enough talk, let’s walk. A great example to demonstrate recursive programming is calculating the factorial of a given number n: 
n! = n * (n-1) * (n-2) * … * 1
5! = 5 * 4 * 3 * 2 * 1

You could work it out like this:

function factorial($n)
{
      if ($n > 1)
      {
            $result = 1;
            for (; $n > 1; $n--)
            {
                  $result *= $n;
            }
            return $result;
      }
      elseif ($n == 1)
      {
            return 1;
      }
      return 0;
}

Or you could work it out like this:

function factorial($n)
{
      if ($n > 1)
      {
            return $n * factorial($n - 1); // step
      }
      elseif ($n == 1)
      {
            return $n; // base case
      }
      return 0; // base case
}

Do you see what I did there? The function factorial calls itself. The great thing about this way of programming is that it’s actually really close to the mathematical approach; this method is more concerned with what the answer for a given input is and less with telling the computer how to get there. In comparing iterative versus recursive programming, recursive is usually a lot more elegant.

For funsies, here are the different approaches.

• Iterative: 6 * 5 * 4 * 3 * 2 * 1;
• Recursive 6 * (5 * (4 * (3 * (2 * (1) ) ) ) )

Downsides

A major downside of recursion is that there is no special implementation for it in most programming languages, notably PHP. This is a problem because for every nested function call a lot of stuff happens to the internal memory arrangement of the program. The call-stack, the stack that keeps track of all the scopes, can overflow when too many recursive calls are made.

Another downside of recursion is that it can be more difficult to understand. This, to me, is not a downside per se. The expressive power and added cleanliness are not for the faint of heart mind(?) it seems.

Upsides

The recursive solution ties in closely to a mathematical principle called induction. What this exactly means is beyond the scope of this post, but the digest is that induction is a way to prove a formula by providing one or more ‘base situations’ and a ‘step’ function (seem familiar?). If you can prove that the base situation is correct and you can prove that the step is correct, you can prove that the entire formula is correct.

By extension, if your entire program is made up of functions that only return some value and don’t do anything else (have no side-effects), and you can prove every function to be correct, you’ve just proven the whole thing to be correct. Functional programming languages are generally designed with these concepts in mind. Examples of those are Miranda, Haskell and Clean, but also Scala and F#. There is a lot more coolness related to functional programming, but we’ll get to that some other time.

Another big advantage, as mentioned earlier, is that recursive programming is often more elegant. This means that the code is both more difficult (because you need to understand more concepts) and shorter (and thus more expressive; you can convey the same amount of information with less words).

DIY Recursion

I want to leave with a function that you can recursify yourself. This function calculates the nth Fibonacci number for a given n.

The Fibonacci numbers are a set of numbers that are defined as follows:

The 0^th and 1^st Fibonacci numbers are 1. Every following number is the number before and the number before that added up. For example, the 2^nd Fibonacci number is 2, because 1 and 1 is 2. The 3^rd number is 3, because 1 and 2 make 3. The 4^th number is 5, because 2 and 3 make 5.

Can you make this iterative Fibonacci function recursive? No peaking on the internets!

function fibonacci($n)
{
      if ($n >= 0)
      {
            $result = 1;
            $previous = 1;
            $prePrevious = 1;
            for (; $n > 1; $n--)
            {
                  $result += $prePrevious;
                  $prePrevious = $previous;
                  $previous = $result;
            }
            return $result;
      }
      return 0;
}