|Programmer's Guide To Theory - Why Recursion|
|Written by Mike James|
|Monday, 13 April 2020|
Page 2 of 2
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:
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.
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(an), where a is the average time for a single loop to complete.
A Programmers Guide To Theory
Now available as a paperback and ebook from Amazon.
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.
or email your comment to: firstname.lastname@example.org
|Last Updated ( Tuesday, 03 August 2021 )|