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 2
Return

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 that the functions are called in.

This is one of the reasons that recursion is more than just a simple loop. A loop just goes in one direction but recursion goes down the chain of calls and then back up again.

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

So tail recursion is good because it can be efficiently implemented but you can see that limiting yourself to tail recursion is missing some of the power of recursion because it only has a forward order of execution like a simple loop.  

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 second level
    For each child child node of the third 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 in the tree you 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.

An even simpler example is printing tuples. You can easily write a program that prints i,j for values from 1 to 10

For i= 1 To 10
 For j= 1 To 10
  print(i,j)
 Next j
Next i

You would have no problem in extending this to printing i,j and k. In fact no matter how many values I asked for you could write the program using the required number of nested loops. However if I say that I want to specify the number of values after you start the program running then you don't know before hand how many nested loops you need. You can't do it. Well you can but its a lot more difficult and you would probably need to use a stack or some similar data structure to store the index variables. Again the problem is a lot easier to express as a recursion - try it.

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

The Working Programmer's Guide To Language Paradigms 

Functional And Dysfunctional Programming

The Essence Of Loops 

Covariance And Contravariance - A Simple Guide

Dangerous Logic - De Morgan & Programming

Lambda Calculus For Programmers

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

<ASIN:0465026567.>

<ASIN:0471816523>

<ASIN:0465030793>

<ASIN:1530634857>

<ASIN:0465030912>

<ASIN:0471701467>