So you know what recursion is, but do you know why it is? This is what this extract from Chapter 16 of my recent book is all about.

A Programmers Guide To Theory

Now available as a paperback and ebook from Amazon.

Contents

1. What Is Computer Science?
   Part I What Is Computable?
2. What Is Computation?
3. The Halting Problem
4. Finite State Machines
   Extract 1: Finite State Machines
5. Practical Grammar
6. Numbers, Infinity and Computation
   Extract 1: Numbers 
   Extract 2: Aleph Zero The First Transfinite
   Extract 3: In Search Of Aleph-One
   Extract 4: Transcendental Numbers
   
7. Kolmogorov Complexity and Randomness
   Extract 1:Kolmogorov Complexity 
8. The Algorithm of Choice 
9. Gödel’s Incompleteness Theorem
10. Lambda Calculus ***NEW!
    Part II Bits, Codes and Logic
11. Information Theory 
12. Coding Theory – Splitting the Bit
13. Error Correction 
14. Boolean Logic
    Part III Computational Complexity
15. How Hard Can It Be?
    Extract 1: Where Do The Big Os Come From
16. Recursion
    Extract 1: What Is Recursion
    Extract 2: Why Recursion
17. NP Versus P Algorithms
    Extract 1: NP & Co-NP
    Extract 2: NP Complete

<ASIN:1871962439>

<ASIN:1871962587>

Recursion is interesting from the point of view of complexity theory and computer science in general because it is the natural way of implementing algorithms that take exponential time. This isn't because recursion is in any sense bad - it's just a more advanced form of the flow of control that makes itself useful when a problem needs it. One of the advantages of recursion is that it can be used to implement "divide and conquer" algorithms that are sub-polynomial in execution time.

Recursion is not an essential concept in the sense that anything you can achieve using it you can achieve without it. If this were not the case then the Church-Turing thesis would be false. On the other hand, recursion is so powerful that it can be used as the basis for the very definition of what computation is. You can tell that attitudes to recursion vary greatly from "why do I need this" to "this is all I need", but the fact that is the subject of a well-known joke makes it harder to ignore.

Definition of recursion: Recursion - see Recursion.

Recursion is, loosely speaking, self-reference.

There are some who just take to this idea and there are others, the majority, who always feel a little unsure that they have really understood how it all works. Recursion is important because it provides a way of implementing a type of algorithm that would otherwise be difficult.

In many textbooks recursion is introduced as an advanced method and a few examples are given. Sometimes you get the impression that the topic has been included just for the reason that it is in other books. Usually the examples are problems that are already stated in recursive form and in this case a recursive implementation seems natural. What is generally overlooked is what recursion is good for. What makes a problem suitable for a recursive implementation?

The answer is surprisingly simple and it reveals the link between recursion and algorithms that have exponential runtimes.

The book includes the following topics that have been omitted from this extract: 

• Ways of Repeating Things
• Self-Reference
• Functions as Objects
• Conditional Recursion
• Forward and Backward Recursion
• The Paradox of Self-Reference

What Use is Recursion?

You understand what recursion is in terms of flow of control, but you might well be still wondering where it becomes necessary? The problem is that in many simple examples recursion isn’t even helpful, let alone necessary. A common example is working out a factorial or similar mathematical formula given in recursive form:

F_n = n*F_n-1 with F₁ = 1,

This gives:

F₂ = 2*F₁ = 2*1

F₃ = 3*F₂ = 3*2*1

and so on.

To implement this as a recursion we simply need to copy the mathematical definition:

Function F(ByValue n)
 if n == 1 then Return 1
 Return n*F(n-1)

You can see how this works. When you call the function with F(3) it evaluates 3*F(2), which in turn evaluates 2*F(1). The if statement causes F(1) to return 1, which unwinds the recursion to give 2*1, and finally 3*2*1.

Notice that this isn’t tail recursion.

You can see this more clearly if the function is written as:

Function F(ByValue n)
 if n == 1 Then Return 1
 temp = F(n-1)
 temp = n*temp
 Return temp

You can now clearly see that the calculation happens after the recursive call. That is, the calculation is performed on the way back down the recursion.

It is possible to write this using tail recursion but it isn’t as easy:

Function F(ByValue n, ByValue product)
       if (n == 1) Then Return product
       Return F(n - 1, product * n);
}

The complication is that, as we now have to do the computation on the way up the recursion, we have to use an extra parameter to pass it to the next recursive call.

However, the simplest way of computing the factorial avoids recursion altogether:

product = 1
for i = 2 to n
  product = product*i
next i

Computing the factorial as a direct loop is simple, understandable and it works. You don't need recursion to implement a factorial function. Many simple examples of recursion are like this – slightly contrived!