What is it?

Despite what I said earlier about looping being one of the cornerstones of programming it is in fact possible to create programs without an explicit loop construct. Some languages, such as Scheme, do not in fact have an explicit loop construct like For, While, etc. Instead they use a technique known as recursion . This turns out to be a very powerful technique for some types of problem, so we'll take a look at it now.

Recursion simply means applying a function as a part of the definition of that same function. Thus the definition of GNU (the source of much free software) is said to be recursive because GNU stands for 'GNU's Not Unix'. ie GNU is part of the definition of GNU!

The key to making this work is that there must be a terminating condition such that the function branches to a non-recursive solution at some point. (The GNU definition fails this test and so gets stuck in an infinite loop).

Let's look at a simple example. The mathematical factorial function is defined as being the product of all the numbers up to and including the argument, and the factorial of 1 is 1. Thinking about this, we see that another way to express this is that the factorial of N is equal to N times the factorial of (N-1).

Thus:
1! = 1
2! = 1 x 2 = 2
3! = 1 x 2 x 3 = 2! x 3 = 6
N! = 1 x 2 x 3 x .... (N-2) x (N-1) x N = (N-1)! x N

So we can express this in Python like this:

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

Now because we decrement N each time and we test for N equal to 1 the function must complete. There is a small bug in this definition however, if you try to call it with a number less than 1 it goes into an infinite loop! To fix that change the test to use "<=" instead of "==". This goes to show how easy it is to make mistakes with terminating conditions, this is probably the single most common cause of bugs in recursive functions. Make sure you test all the values around your terminating point to ensure correct operation.

Let's see how that works when we execute it. Notice that the return statement returns n * (the result of the next factorial call) so we get:

factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1

So Python now works its way back up substituting the values:

factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24

Writing the factorial function without recursion actually isn't that difficult, try it as an exercise. Basically you need to loop over all the numbers up to N multiplying as you go. However as we'll see below some functions are much harder to write without recursion.

Recursing over lists

The other area where recursion is very useful is in processing lists. Provided we can test for an empty list, and generate a list minus its first element we can use recursion easily. In Python we do that using a technique called slicing. This is explained fully in the Python manual but for our purposes all you need to know is that using an "index" of [1:] on a list returns all of the elements from 1 to the end of the list. So to get the first element of a list called L:

first = L[0] # just use normal indexing

And to get the rest of the list:

butfirst = L[1:] # use slicing to get elements 1,2,3,4...

Let's try it out at the Python prompt, just to reassure ourselves that it works:

>>> L =[1,2,3,4,5]
>>> print L[0]
1
>>> print L[1:]
[2,3,4,5]

OK, let's get back to using recursion to print lists. Consider the trivial case of printing each element of a list of strings using a function printList:

def printList(L):
    if L:
        print L[0]
	printList(L[1:])

If L is true - non empty - we print the first element then process the rest of the list like this:

# NON PYTHON PSEUDO CODE
PrintList([1,2,3])
   prints [1,2,3][0] => 1
   runs printList([1,2,3][1:]) => printList([2,3])
   => we're now in printList([2,3])
         prints [2,3][0] => 2
         runs printList([2,3][1:]) => printList([3])
	 => we are now in printList([3])
	       prints [3][0] => 3
	       runs printList([3][1:]) => printList([])
	       => we are now in printList([])
	             "if L" is false for an empty list, so we return None
	 => we are back in printList([3])
	       it reaches the end of the function and returns None
   => we are back in printList([2,3])
	 it reaches the end of the function and returns None
=> we are back in printList([1,2,3])
   it reaches the end of the function and returns None

[Note: The above explanation is adapted from one given by Zak Arntson on the Python Tutor mailing list, July 2003]

For a simple list that's a trivial thing to do using a simple for loop. But consider what happens if the List is complex and contains other lists within it. If we can test whether an item is a List using the built-in type() function and if it is a list then we can call printList() recursively. If it wasn't a list we simply print it. Let's try that:

def printList(L):
    # if its empty do nothing
    if not L: return
    # if it's a list call printList on 1st element
    if type(L[0]) == type([]):
        printList(L[0])
    else: #no list so just print 
        print L[0] 
    # now process the rest of L 
    printList(L[1:])

Now if you try to do that using a conventional loop construct you'll find it very difficult. Recursion makes a very complex task comparatively simple.

There is a catch (of course!). Recursion on large data structures tends to eat up memory so if you are short of memory, or have very large data structures to process the more complex conventional code may be safer.

Finally, both VBScript and JavaScript support recursion too. However since there is little to say that has not already been said I will leave you with a recursive version of the factorial function in each language:

<script type="text/vbscript">
Function factorial(N)
   if N <=1 Then
      Factorial = 1
   Else
      Factorial = N * Factorial(N-1)
   End If
End Function

Document.Write "7! = " & CStr(Factorial(7))
</script>

<script type="text/javascript">
function factorial(n){
   if (n <= 1)
      return 1;
   else
      return n * factorial(n-1);
};

document.write("6! = " + factorial(6));
</script>

OK, let's now take another leap into the unknown as we introduce Functional Programming.