Most programmers with a few years under their belt understand recursive procedures. A recursive procedure is simply a procedure that calls itself. Understanding this is somewhat of a "rite of passage" for many programmers.

In this post we will take the discussion slightly further from recursive procedures and discuss recursive processes.

Computer Science is not so much the study of procedures as the study of processes. Procedures are used to generate processes but it is the process in the end that we are interested in.

An interesting question to ask, therefore, is - Do recursive procedures always lead to recursive processes?

At first glance this may seem like a silly question but bear with me a little more. Let's discuss this by looking at two implementations of a simple recursive function - the Factorial function: F(0) = 1; F(n) = n * F(n)

Implementation 1

Implementation 2

Now note that both implementations are recursive and both compute the Factorial function perfectly. Now let us take a look at the processes each of them generate:

Process 1

Process 2

The first process grows and shrinks which is typical of a recursive process. The second, however, does not! All it's information is contained in the current value of it's variables. Such a process is, in fact, iterative in nature.

We can now answer the question posed earlier - "Do recursive procedures always lead to recursive processes?" Surprisingly the answer is - No!

We have seen a recursive procedure that actually describes an iterative process. Such recursive processes are known as tail recursive because the recursive call is normally the last call in the recursive procedure and can be replaced with a simple goto.

In fact, compilers like Scheme recognize tail recursion and replace the call with a simple jmp instruction. Many mainstream languages (like C/C++) however, keep the call instruction (note in the diagram above, that the C/C++ version continues to behave recursively returning the same value across each call). This is one reason many programmers are unaware of the distinction.

Another way to look at our result is that iteration is a special form of recursion! If you take another look at the second process you can see f2i actually resembles a for loop.

What this means is that, for, while, and the do, loops are simply syntactic sugar in languages that are properly tail-recursive.

Why is this important? Well, it could mean that, while formulating theories in the new and exciting field of Computer Science, we may not have to deal with looping constructs because they can be handled as special cases of recursion.

In a later post, I will discuss how recursion itself can be simulated with the help of higher-order functions so in the end we may not have to deal with either recursion or iteration and are left with a much simpler system to analyse.