Recursion is often said to separate real programmers from the pack. What is it that makes it so powerful? What is it that makes it so difficult? What is the "shape" of recursion as a flow of control?

Let's get the standard joke out of the way right at the start.

Definition of recursion:

Recursion - see Recursion.

There are some who just take to this idea like a duck to water and there are others, the majority, who always feel a little unsure that they have really understood how it all works. To cut to the point, it is a really interesting idea and if you don’t know about it already then you can look forward to some fun.

Ways of repeating things

Before we move on to recursion we need to look at the most basic ways of repeating something - if only to make sure we are using the same vocabulary.

When you first learn to program one of the key ideas is writing a set of instructions that repeats. For example, to print “Hello” repeatedly then I’d use a loop:

Do
 Print “Hello”
Loop

You can think of the Loop as an instruction to go back to the Do and repeat all of the instructions between the two all over again. In this case you just go round and round the loop forever printing “Hello” each time.

If you would like a deeper look at loops before moving on to recursion then read: The Essence Of Loops

This is an infinite loop, but most loops in sets of instructions are finite loops which repeat a number of times.

There are two broad types of finite loop, enumeration and conditional.

The difference is that an enumeration loop repeats a given number of times, i.e. print hello five times is an enumeration loop, as is the familiar For loop found in most programming languages.

A conditional loop keeps on repeating until a final end result is achieved, i.e. "stir the coffee until the sugar has dissolved" is a conditional loop, as are the familiar While or Until loops found in most programming languages. 

A loop is called a loop because it … loops

To state the most obvious fact about a loop:

a loop is called a loop, because it loops around in the text of a program.

If you take your finger and follow the sequence of instructions that occur when you have a loop - i.e. the flow of control - then you discover that you are making circular movements as you go back and repeat instructions.

There is a very deep sense in which every programmer thinks of a loop as a circular shape.

Self reference

So far so good but what has all of this got to do with something far less well known – recursion?

Well recursion is just another way of repeating things. It’s simple at first but stay alert because it has a habit of becoming complicated just when you think you are getting used to it.

Imagine that instead of simply using a command to print a message we write a function (or a procedure), i.e. a self-contained module that does the job and perhaps more. Let’s call it Greetings

Function Greetings()
 lines of instructions
 Print “Hello”
Return

Whenever you use its name the set of instructions is obeyed. So:

Call Greetings()

results in all of the instructions in the function being obeyed. In this case all that happens is that "Hello" is printed.

This is really all we need to move on to recursion. Consider the following small change:

Function Greetings()
  lines of instructions
  Print “Hello”
 Call Greetings
Return

What does this do?

If you start it off with a Call Greetings in some other part of the program you start the list of instructions it contains executing. Everything is normal until you get to the Call Greetings instruction, which starts the whole thing going again.

We have an infinite loop built using the trick of having a function call itself!

This is the essence of recursion but in this simple form it just looks like an alternative way of creating a loop.

However creating a loop using self reference quickly becomes so much more and its all to do with the way self reference automatically stores the state of things each time you call the function. 

Functions as objects

To see the difference between recursion and simple looping it helps to consider that a function is like an  object which is created each time you make use of it.

This is only sort of true in most programming languages in that each time a function is called it exists in a new "call context" which only approximates a "completely new copy" of the function.

So while this idea of function as object isn't 100% correct thinking about things in this way can make recursion much easier to understand.

For example, consider the difference between

Do
 Call Greet1
Loop

and

Function Greetings()
  lines of instructions
  Print “Hello”
 Call Greetings
Return

In the case of the loop a single "object" or context is brought into existence and then is destroyed when the loop ends. You can think of this as - at any moment in the life of the program there is a single Greet1 in existence.

Now compare this to the second version of the repeat. The first time the Greetings function is called a single Greetings object comes into existence. It does its stuff and then, before it comes to an end, it does another Call Greetings command. Now there are two Greetings objects in existence.

You can probably see where this is going. Each time the function self references, a new instance of the object comes into existence and, if we wait long enough, the result is an infinite collection of objects all waiting for the next one to finish its task.

Recursion builds up a collection of objects as it spirals its way to infinity

Conditional recursion

You might be beginning to see why recursion is so much more powerful than iteration. Recursion can, by the power of self reference, bring into existence as many copies of the function as are needed to complete a task.

Of course the sort of recursion we are looking at isn’t of much use because it is infinite recursion – it just goes on.

Just like an infinite loop, infinite recursion can be tamed by adding a condition that stops it happening. This gives us “finite” or “conditional” recursion.

You might think that there is nothing new here but you would be wrong and again this is another one of those “recursive” complications that is designed to catch you out just when you think you understand.

To show you what I mean consider the following:

Function counter(ByValue i)
  If i =5 Then Return
   i = i + 1
 Call counter(i)
   Print i
Return

This is a small function written in an obvious pseudo code.

The ByValue means that the parameter is passed by value - most programming languages pass parameters by value as the default but we need to make sure that this is the case for the recursion to work properly.

It has to be passed by value because this is the only way the new copy of the function gets its own copy of the parameter which it can do what it likes with without modifying any earlier copies. You can think of this as demanding that each function object that is created has to be a completely new copy and not inherit anything that the previous function had.

Recursion becomes complicated when you start to use parameters passed by reference or global variables. To keep things simple always use local variables and pass by value within recursive functions.

Following a:

Call counter(0)

which gets it going, it first tests to see if the counter , i.e. “i”, is 5. If it is then the function ends. If it isn’t, it has one added to it and the counter is called again.

Clearly this is a finite recursion as eventually the counter function will be called with a value of 5 and the recursion comes to an end. In this case we have five recursions, and five instances of the counter function.

No problems but ask your self what is printed?

If your answer is 1,2,3,4,5 then you need to think a little more carefully and look at the diagram below.

Nothing gets printed until i reaches 5 when the next copy of the count function comes to an end and the final copy continues on to print the value of i. Then it comes to an end and the previous instance of the object gets to carry on and print its value of i and so on back to the first copy. You should now be able to see that what is printed is 5,4,3,2,1.

Recursion spirals one way and then back the other.

It is helpful  to think of recursion as having a forward phase when the "instances" of the function are being created and a backward phase when the functions are being destroyed. You could say that recursion spirals its way out and then spirals back in the opposite direction but this might be taking things too far for some!

Even so there is a sense in which the shape of the flow of control for a recursion is a spiral that you work your way along and then work your way back along when the recursion comes to an end. If it helps think of it in this way.

<ASIN:0465030912>

<ASIN:0465030785>

<ASIN:0140289208.>

<ASIN:0465045669>