|Programmer's Guide To Theory - Why Recursion|
|Written by Mike James|
|Monday, 13 April 2020|
Page 1 of 2
So you know what recursion is, but do you know why it is? This is what this extract from Chapter 15 of my recent book is all about.
A Programmers Guide To Theory
Now available as a paperback and ebook from Amazon.
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:
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:
Fn = n*Fn-1 with F1 = 1,
F2 = 2*F1 = 2*1
F3 = 3*F2 = 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!
|Last Updated ( Saturday, 18 April 2020 )|