Recursion who needs it? This is an extract from my book Trick of the Mind which explores what it is to be a programmer.

The Trick Of The Mind - Programming & ComputationalThought

Buy Now From Amazon

Chapter List

1. The Trick Of The Mind

2. Little Languages
      Extract: Little Languages Arithmetic

3. Big Languages Are Turing Complete

4. The Strange Incident of The Goto Considered Harmful
      Extract: The Goto Considered Harmful

5. On Being Variable  

6. Representation

7. The Loop Zoo
      Extract The Loop Zoo
      Extract Advanced Loops
   

8. Modules, Subroutines, Procedures and Functions
      Extract Modular Programming

9. Top-Down Programming 

10. Algorithms
       Extract: Binary Search 
       Extract: Recursion ***NEW!!

11. The Scientific Method As Debugging 

12. The Object Of It All
       Extract Why Objects 

 <ASIN:1871962722>

<ASIN:B09MDL5J1S>

Recursion

While not an algorithm itself, the technique of recursion is used within algorithms – particularly divide-and-conquer algorithms. It is an advanced idea and potentially confusing. The status of recursion within the computer science community is split. Some think it is a marvelous invention to be used at every opportunity while others think it is a complex and error-prone approach. Both are correct.

In practice you rarely need recursion – why would you as loops and conditionals are enough to make a language Turing-complete. In other words, if you have loops and conditionals you don’t need recursion. However, recursion can be used instead of loops to make a language Turing-complete. Instead of using Ifs and loops you could use Ifs and recursion.

So what is recursion? The old joke is that its definition is “recursion – see recursion”. This is an accurate definition, however, as recursion is about self-reference. There are many paradoxes involving self-reference, but the use that we put it to in programming is not in the least paradoxical. As you can see at once, recursion is a way of repeating things and “recursion – see recursion”, is just as much a loop as any other way of expressing it.

In programming recursion is a way of implementing a loop. For example, consider the following simple function:

Function Greetings() 
  lines of instructions
  Print “Hello”
  Greetings()
Return

What does this do? If you start it off with a call to 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. It will repeat the instructions before the call to Greetings over and over again forever.

We have an infinite loop built using the trick of having a function call itself! This is the essence of recursion and while it looks like a simple loop there is more to it. Each time the function is called it starts over with fresh values of whatever variables it uses and when it returns it returns to wherever the earlier invocation of the function got to, complete with all of its variables unmodified.

For example, what does this do:

Function Counter(count)
	count = count+1
	print(count)
	If count < 4 Then Counter(count)
	print count
	Return
Counter(1)

The first call to Counter adds one to count, which is initially set to 1, and hence it prints 2. The condition is true, count is less than 4 and so Counter is called: Counter(2) and one is added to count which results in 3 being printed. Again Counter is called as Counter(3) and so on until count reaches 4, when 4 is printed and the condition is false and the print displays 4 for a second time and return happens. This causes the previous call to the function to start up again after the If instruction and so it prints its value of count which hasn’t been changed by the call it made to Counter and so it prints 3 and returns. This returns to the first call to Counter which does the same thing but prints 2 and the program is over. So what is printed is

2
3
4
4
3
2

This is probably more complicated behavior than you might have expected and it is partly this that makes recursion so much more useful.

Drawing a diagram of the flow of control in recursion is difficult, but I imagine it something like:

You can see that each time a call to counter is made we have to imagine a new copy of the function being brought into existence. There is a forward transition from each instance of the function to the next and there is a backward transition as each instance returns.

It is almost as if the flow of control spiraled up to the final instance of the function and then spiraled back down. Hence I like to think of recursion as a flow of control spiral and a loop as just a loop.

There are many other interesting things about recursion that are worth knowing, but in most cases you can simply use a loop to do the same job. For example, our previous example can be written:

Function Counter(count)
	while count < 4
       	count = count+1
		print(count)
	while count > 1	
		count = count-1
		print count
	Return

The only time that you need to use recursion is when the problem is expressed in a recursive form – and many are – or when what is needed is a variable number of nested loops.

As a final example, binary search is a natural for recursive implementation if you have that particular mind set. The binary search algorithm is naturally described recursively. First you find the middle element and see if it is the book you are looking for or if you have run out of books to look at. If this is the case you have finished and the task is over:

Function BinarySearch(Start, End, Target)
	Middle = CEIL((End-Start+1)/2)
	If shelf(Middle) == target Then Return Middle
	If Start > End Then Return Not Found

If you haven’t found the book and there are still books to look at then you want to do a binary search on either the right-hand set or the left-hand set:

	If shelf(Middle) < target Then 
	  result = BinarySearch(Middle+1,End,Target)
	Else
	  result = BinarySearch(Start,Middle-1,Target)
	Return result

Is this simpler? Some think so, most don’t.

Summary

• Algorithms are what programs implement and to do this you have to make the specification of the algorithm precise enough to allow a non-intelligent agent to follow the instructions.

• Finding a book in a big library is a good problem to illustrate the idea of implementing an algorithm because it can be solved using simple and more advanced approaches.

• The simplest is linear search which works with a library of books in no particular order.

• You can also try picking books at random, but this isn’t a good algorithm.

• If the librarian has gone to the extra effort of putting the books into order, then you can use the binary search algorithm which is much more efficient.

• Specifying the binary search algorithm in detail is a very good example of how algorithms are converted into programs.

• The binary search algorithm is an example of a general class of divide and conquer algorithms, the most important of these being the Fast Fourier Transform and Quicksort.

• Recursion is an alternative to iteration and it is particularly applicable to the binary search problem.

• The final algorithm for the book search problem is hashing. This is very efficient and doesn’t require the books to be sorted into order. If correctly implemented it can find a book in no more than a few attempts no matter how many books are involved.

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