Let's get the standard joke out of the way.

Definition of recursion:

Recursion - see Recursion.

There are some who just take to it 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’s 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. 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

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

Imagine that instead of simply using a command to print a message we write a function (or a subroutine), 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. And 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.

It is just an alternative way of creating a loop using self reference but it quickly becomes so much more.

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

<ASIN:0465045669>

<ASIN:0465030912>

<ASIN:0465030785>