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 Lisp, 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.

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*. Thiis 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]
# for [1:] - see 'slicing' in the Python reference manual
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

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
then we can call `printList()` recursively. If not 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.

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

Previous Next Contents

If you have any questions or feedback on this page
send me mail at:
alan.gauld@btinternet.com