Recursion

### New Book Reviews!

 Recursion
Written by Mike James
Article Index
Recursion
Conditional recursion
Forward and backward recursion

## Forward and backward recursion

In general a recursive object looks something like:

`Function xxx(parameters) list of instructions 1 If condition Then Call xxx list of instructions 2Return`

The first list of instructions is obeyed on the way up the spiral i.e. as the instances of the function are being built and the second list is obeyed on the way back down the spiral as the instances are being destroyed. You can also see the sense in which first list occurs in the order you would expect but the second is obeyed in the reverse order.

Sometimes a recursive function has only the first or the second list of instructions and these are easier to analyse and implement.

For example a recursive function that doesn't have a second list doesn't need the copies created on the way down the recursion to be kept because they aren't made any use of on the way up!

This is usually called tail end recursion because the recursive call to the function is the very last instruction in the function i.e. in the tail end of the function. Many languages can implement tail end recursion more efficiently than general recursion because they can throw away the state of the function before the recursive call so saving stack space.

## What’s it for?

So that’s it – that’s recursion mastered.

You now understand what recursion does but you might well be still wondering what’s it for?

There are some people who see what its for at once and more or less invent recursion for themselves the rest of us need some pointers on how to spot where it could be useful.

Let’s look at an example of recursion in action.

Suppose you have a binary tree, i.e. data that starts at a root node and with each node has a left and a right child node. Your problem is to write a program that starts at the root node and prints the name of every node in the tree.

Now you could write this program without recursion but compared to the recursive version it would be very complicated.

Suppose we have a function Left(node) that returns the left child of the current node and a function Right(node) that returns the right node. We can now write a recursive tree list as:

`Function list_tree(node) If node=nothing Then Return Print node Call list_tree(Left(node)) Call list_tree(Right(node))End Sub`

This looks almost too easy – where is the work actually done?

If you start if off with Call list_tree(root) the recursive calls work their way down the left branch from the root node and then the left branch of the right child of the root node.

It’s so easy it seems crazy to contemplate any other way of doing the job!

Just to make sure you understand what is going on work out what happened if you move the “print node” to the end of the routine. What happens if you change Left for Right and vice versa?

The reason why this tree listing works so well as a recursion is that the data is recursive in its basic nature. For example, try this definition of what a binary tree is:

A binary tree is a node with a binary tree as its left child and a binary tree as its right child.

You can see that this is an explicitly recursive definition of what a binary tree is and this is the reason why recursion fits so well with this particular data structure.

There have even been programming methodologies that make use of the idea that the algorithm is always derived from the data structure and this "recursive data needs recursive algorithms" is just a special case. For more on the relationship between data structures and algorithms see Jackson Structured Programming.

## Nested loops

There is a deeper reason why recursion is often easier to use but it’s more difficult to understand.

Many problems require nested loops, that is loops within loops, or nested loops, to work.

As long as you know the number of loops that have to be nested then no problem and everything works. But some problems need a variable number of nested loops and these are the ones that are more easily solved using recursion.

You can see this in the case of listing the binary tree. If the tree is of a specified depth then you can list it by writing a loop for each level of the tree nested within the first.

`For each node at the first level For each child node for the first level  For each child child node            of the first level`

and so on. Of course if you don’t know how many levels the tree has you can’t finish the program but you can do it recursively with no such problem.

It is as if you are trying to say if there are N levels nest N loops. For this reason you can say that recursion is equivalent to a variable number of nested loops and its useful whenever this sort of structure is needed.

In other words if you find that you have a problem where you want to write an in general unknown number of nested loops then you can solve the problem most easily using recursion.

## Self reference

People get very “spooky” about recursion and credit it with almost magical properties.

It all starts with:

This sentence is false.

which if you assume it is true asserts its own falsity, and if you assume it is false asserts its own truth. It is like a sort of logical flip-flop.

Then the spookiness  moves on to the fact that our consciousness seems to be recursive – I’m observing myself observe myself – and so on. Then there are fractals, recursive patterns, and recursive programs seem to do so much without ever seeming to do anything.

If you would like to discover more about the philosophical aspects of recursion and “strange loops” then there is no better book on the subject than Godel, Escher, Bach: An Eternal Golden Braid, by Douglas R. Hofstadter - see the side bar for more details.

#### Related Articles

Cartoon - Recursion