What will we cover?

- A definition of recursion
- How recursion works
- How recursion helps simplify some hard problems

Note: This is a fairly advanced topic and for most applications you don't need to know anything about it. Occasionally, it is so useful that it is invaluable, so I present it here for your study. Just don't panic if it doesn't make sense straight away.

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 actually 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 (signified by an exclamation mark after the number: n!) is defined as being the product of all the numbers up to and including the argument, and the factorial of 0 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 == 0: 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 negative
number it goes into an infinite loop! To fix that, add a test to check
for `n` being less than 0 and return `None` (since
the factorial of a negative number is undefined!). 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. 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...
```

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
```

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]) == list: 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. Because of the memory issue,
and its potential to crash the interpreter, Python builds in
a limit to how many levels of recursion it will allow. If
you exceed that limit your program will terminate with an
`RecursionError` (which you could, of course, catch using
`try/exccept`. Here is a simple example that shows
the error:

>>> def f(n): return f(n+1)

Notice that in this case it was caused by the fact we had no terminating condition, but even in a well written function a very large input data set would be enough to trigger it. In that case the only solution is to rewrite the solution using normal loops (the good news is that it has been proved that it is always possible to do that, no matter how tricky it seems!).

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

<script type="text/vbscript">Function factorial(N) if N < 0 Then Factorial = -1 'a negative result is "impossible" if N = 0 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 < 0) return NaN // NaN - Not a Number - means it's invalid if (n == 0) 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.