Self-Reference

So far so good, but what has all of this got to do with something far less familiar – recursion? Recursion is just another way of repeating things. It’s simple at first but 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, called 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 execution of the list of instructions it contains. 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 it’s 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 partially true in most programming languages in that each time a function is called it exists in a new "call context" which only approximates to a "completely new copy" of the function. However, while this idea of function as object isn't universally 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. That is, 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 therefore 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 and this includes any variables etc that are created by the function. 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 small function:

Function counter(ByValue i)
  if i == 3 then Return
   i = i + 1
 Call counter(i)
   Print i
Return

The ByValue is included to ensure that the parameter is passed by value. This is the default for most programming languages, 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 act on 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 from the previous function.

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. This ensures that each copy of the function that is created is a unique object that doesn't share anything with the other instances of the function.

Call counter(0) gets things going. The function first tests to see if the counter, i.e. i, is 3. If it is then the function ends. If it isn’t, i has 1 added to it. Then counter is called again.

Clearly this is a finite recursion as eventually counter will be called with a value of 3 and the recursion will come to an end. In this case we have four recursions, and four instances of the counter function. The reason it is four and not three instances of the function is that we need a final instance to test for i==3 which exits without printing i.

Ask yourself what is printed? If your answer is 1,2,3 then you need to think a little more carefully and look at the diagram below. Nothing gets printed until i reaches 3 when the next copy of the counting 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 3,2,1

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.