A Case for Recursion -The Binary Tree

Let’s look at an example of recursion in action where its use really simplifies things because it is natural and necessary. Suppose you have a binary tree, i.e. data that starts at a root node and where each node has a left and a right child node. Your problem is to write a program that starts at the root node and prints the name of every node in the tree. You could write this program without recursion, but compared to the recursive version it would be very complicated.

For a recursive approach let’s use a Left(node) function to return the left child of the current node and Right(node) to return the right node. We can now write a recursive tree list as:

Function list_tree(node)
 if node = nothing then Return
 print node
 list_tree(Left(node))
 list_tree(Right(node))
Return

This looks almost too easy – where is the work actually done?

If you start if off with:

list_tree(root)

where root is the start of the tree, the recursive calls work their way down the left branch from the root node and then the left branch of the right child of the root node. It’s so easy it seems crazy to contemplate any other way of doing the job! It is this sort of example that makes programmers fall in love with recursion - provided they really understand it.

Just to make sure you understand what is going on, work out what happens if you move the print node to the end of the routine. What happens if you change Left for Right and vice versa?

The reason why this tree listing works so well as a recursion is that the data is recursive in its basic nature. For example, try this definition of a binary tree:

A binary tree is a node with a binary tree as its left child and a binary tree as its right child.

You can see that this is an explicitly recursive description of a binary tree and this is the reason why recursion fits so well with this particular data structure.

There have even been programming methodologies that make use of the idea that the algorithm is always derived from the data structure and this "recursive data needs recursive algorithms" is just a special case.

More fundamental is the fact that without recursion this example needs a variable number of for loops.

Nested Loops

There is a deeper reason why recursion is often easier to use, but more difficult to understand. Many problems require loops within loops, or nested loops, to work. As long as you know the number of loops that have to be nested then no problem and everything works. But some problems need a variable number of nested loops and these are the ones that are more easily solved using recursion.

You can see this in the case of listing the binary tree. If the tree is of a specified depth then you can list it by writing a loop for each level of the tree nested within the first.

for each node                    for the first level
  for each child node            for the second level
    for each child child node    for the third level

and so on. Of course, if you don’t know how many levels the tree has you can’t finish the program, but you can do it recursively with no such problem. It is as if you are trying to say if there are n levels in the tree you nest n loops. For this reason, you can say that recursion is equivalent to a variable number of nested loops and it’s useful whenever this sort of structure is needed.

An even simpler example is printing tuples, which was the example given in the previous chapter. You can easily write a program that prints i,j for values from 1 to 10

for i= 1 To 10
 for j= 1 To 10
  print(i,j)
 next j
next i

You would have no problem in extending this to printing i,j and k. In fact, no matter how many values were required, you could write the program using the required number of nested loops. However, if the number of values required is only specified after the program starts running, then you don't know beforehand how many nested loops to use and you can't do it. Well, you can, but it’s a lot more difficult and you would probably need to use a stack or some similar data structure to store the index variables.

Again the problem is a lot easier to express as a recursion:

function tuple(N) 
     if (N == 0) return
     for i = 0 To 10
       print(i)
       tuple(N-1);       
     }
}

The parameter N is used to “count” the number of loops needed. When it reaches zero we have enough and the function just returns. Otherwise it starts a for loop and then calls tuple(N-1) which starts yet another for loop or returns if the job is done.

In other words, if you find that you have a problem where you want to write an unknown number of nested loops then you can solve the problem most easily using recursion.

The fact that recursion is often equivalent to nested loops is the reason that some programs take exponential time, see the previous chapter for a full explanation. However, if recursion is implementing n nested loops then it is of order O(aⁿ), where a is the average time for a single loop to complete.

Summary

• The simplest way of repeating anything is to use a loop and the shape of the flow of control is indeed just a loop.

• There are conditional loops and enumeration loops but the only type of loop you need is the conditional loop.

• Recursion, or self-reference, is another way of repeating things. It isn't a necessary construct as it can be emulated using loops, but it is very useful.

• Infinite recursion is the equivalent of an infinite loop.

• The most important idea in recursion is that a complete copy of a function is brought into existence with each recursive call.

• You can think of the flow of control in recursion as a spiral moving up each time the function is called and then spiraling down as each function completes.

• The block of code before the recursive call is executed on the way up the spiral and the block of code after the recursive call is executed on the way down the spiral.

• If the block of code after the recursive call is eliminated we have tail recursion, which is efficient to implement.

• Recursion can be useful when implementing an algorithm that has a common recursive definition. It is more necessary, however, when the data structure is itself recursive.

• Recursion is the easiest way to implement a variable number of nested loops and this is also the reason why recursive algorithms are exponential.

• Many paradoxes arise from contradictory self-reference, which can be thought of as infinite recursions. The result of an infinite recursion is undecidable and all of the paradoxes of computer science are infinite recursions.

• Recursion is an example of self-reference which lends itself easily to mysticism and is often called a strange loop. Human consciousness is the result of us observing us, which in turn is an example of the universe observing itself, a strange loop that goes beyond the scope of this book

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>

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info