Recursion is the process of defining a problem, or the solution to a problem, in terms of simpler versions of itself.  In practice, recursion is when a function or procedure repeatedly calls itself.

A recursive call uses the same algorithm repeatedly, each time to solve a simpler version of the problem.  It works towards a ‘base case’ which is the solution to the “simplest” possible problem.  Recursion is used to solve a problem when the recursive solution makes the code simpler and easier to follow.

Consider the problem Find your way home…

1. If you are at home, stop
2. Take one step towards home
3. Find your way home

We don’t go home if we are already there.  We do a very simple action that makes our problem easier to solve.  We redo the entire algorithm.

Recursion and the call stack

It is useful to think of recursive calls in terms of the call stack (also known as the execution stack, the machine stack, and the activation stack).

When one regular, non-recursive, function calls another, it is suspended while the function it called is running.  Once the called function has finished, control is returned to the caller.  When a call is made, the return address of the caller (along with other CPU register values) is pushed onto the call stack.  If there is a calling chain (a calls b, which then calls c, which then calls d, etc.), the stack will grow until the final function in the sequence ends.  The call stack is then dismantled as control is passed back down the chain.  The call stack is used by the caller to pass parameters to the function it is calling, and later, by the function that was called, to pass a return value back to its caller.

With recursion, when a function invokes itself, something similar happens.  Each invocation of the function, that is each running instance of the function, is suspended when it invokes itself again.  The call stack is used to pass parameters and return values between invocations.

N Factorial

A classic problem with a recursive solution is to find the factorial of a natural number, N.

The factorial of N, or N factorial, is written as N!

Let’s consider the mathematics first:

5 factorial, or 5! is calculated as follows:

5! = 5 * 4 * 3 * 2 * 1 = 120

Here we are taking the natural number 5, and multiplying it by one less.  We then multiply the result by two less, then multiply the result by three less, etc. until we are multiplying by one.

You should be able to see that 5! = 5 * 4!

This can be expressed as:

5 * (5-1) * (5-2) * ….. * 1)

Or more generally:

N * (N-1) * (N-2) * ….. * (N-(N-1))

Hence:

N! = N * (N-1)!

This could be implemented programmatically as a function using iteration (a loop).

    Function factorial(n)

        Dim Result As Integer

        Dim i As Integer

        Result = 1

        For i = 1 To n

            Result = Result * i

        Next

        Return Result

    End Function

It could also be implemented using recursion.  Notice where the function calls itself, n * Factorial(n-1)

    Function factorial(n)

         If n = 1 Then

            Return 1

            Exit Function

        End If

        Return n * factorial(n – 1)

    End Function

Head recursion versus tail recursion

This refers to the order of execution in the recursive instruction, that is, the line of code in which the program calls itself.

Head recursion

With head recursion, the recursive call is at the start of the recursive instruction.  Recursion occurs before any other operation in the instruction that contains the recursive call.

The following example is very similar to the N! function.  For the number 5 it will calculate 5 + 4 + 3 + 2 + 1.

    Function HeadSum(x As Integer)

        ‘Head recursion

        If x = 1 Then

            Return x

        Else

            Return x + HeadSum(x – 1)

        End If

    End Function

Notice that in the line containing the recursive call, the recursive function is called BEFORE adding it to x.  The return value of a new invocation must be resolved before the addition can be performed.  With each successive call of the function, the addition operations cannot be performed immediately.  The addition operations are performed only when the base case has been met, all of the calls have been made, and each invocation of the function returns control to its previous invocation.

If you called HeadSum(5), this is what the VB.NET runtime engine would evaluate.

HeadSum (5)
5 + HeadSum(4)
5 + (4 + HeadSum(3))
5 + (4 + (3 + HeadSum(2)))
5 + (4 + (3 + (2 + HeadSum(1))))
5 + (4 + (3 + (2 + 1)))
15

Tail recursion

With tail recursion, the recursive call is at the end of the recursive instruction. A function call is said to be tail recursive if there is nothing else to do in the instruction after the function returns a value, except return its value.

This example solves the same problem as in the previous example, but notice that recursive function is called AFTER the addition has been performed.

    Function TailSum(x, running_total)

        ‘Tail recursion

        If x = 0 Then

            Return running_total

        Else

            Return TailSum(x – 1, running_total + x)

        End If

    End Function

The calculations x – 1 and running_total + x are done before the results are passed as parameters.  Hence the sequence of events is as follows:

TailSum(5, 0)
TailSum(4, 5)
TailSum(3, 9)
TailSum(2, 12)
TailSum(1, 14)
TailSum(0, 15)
15

The Role of the Stack

With a head recursive function the computer ‘remembers’ each previous state of the problem. This information is held by the computer on the call stack and each invocation of the function has its own workspace known as a stack frame.  As we saw in the head recursive example above, with each successive call of the function, the addition operation is not performed – yet.  The addition operations are only be performed while the call stack is being dismantled.

With the tail recursive version of the function, when each invocation of the function finishes, there is nothing else for the preceding invocation to do.  When a function invokes itself with tail recursion, the current recursive instance is done executing at that point,  so saving its stack frame is a waste.  Specifically, creating a new stack frame on top of the current, finished, frame is a waste of space.  In tail recursion, the caller is simply replaced on the stack with the callee, so that instead of nesting the stack deeper, the current stack frame is reused.  A compiler is said to implement tail recursion if it recognises this case and replaces tail recursive code with iterative machine code.  Indeed, tail recursive algorithms can be easily implemented by programmers as iterative solutions instead.