Recursion
Written by Mike James   
Article Index
Recursion
Conditional recursion
Forward and backward recursion

 

Functions as objects

To see the difference between recursion and simple looping it helps to consider that a function is like an  object which is created each time you make use of it.

This is only sort of true in most programming languages in that each time a function is called it exists in a new "call context" which only approximates a "completely new copy" of the function.

So while this idea of function as object isn't 100% correct thinking about things in this way can make recursion much easier to understand.

For example, consider the difference between

Do
Call Greet1
Loop

and

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

In the case of the loop a single "object" or context is brought into existence and then is destroyed when the loop ends. You can think of this as at any moment in the life of the program there is a single Greet1 in existence.

Now compare this to the second version of the repeat. The first time the Greetings function is called a single Greetings object comes into existence. It does its stuff and then, before it comes to an end, it does another Call Greetings command. Now there are two Greetings objects in existence.

You can probably see where this is going. Each time the function self references, a new instance of the object comes into existence and, if we wait long enough, the result is an infinite collection of objects all waiting for the next one to finish its task.

 

rec1

Recursion builds up a collection of objects as it spirals its way to infinity

Conditional recursion

You might be beginning to see why recursion is so much more powerful than iteration. Recursion can, by the power of self reference, bring into existence as many copies of the function as are needed to complete a task.

Of course the sort of recursion we are looking at isn’t of much use because it is infinite recursion – it just goes on.

Just like an infinite loop, infinite recursion can be tamed by adding a condition that stops it happening. This gives us “finite” or “conditional” recursion.

You might think that there is nothing new here but you would be wrong and again this is another one of those “recursive” complications that is designed to catch you out just when you think you understand. To show you what I mean consider the following:

Function counter(ByValue i)
If i =5 Then Return
i = i + 1
Call counter(i)
Print i
Return

This is a small function written in an obvious pseudo code. The ByValue means that the parameter is passed by value - most programming languages pass parameters by value as the default but we need to make sure that this is the case for the recursion to work properly.

It has to be passed by value because this is the only way the new copy of the function gets its own copy of the parameter which it can do what it likes with without modifying any earlier copies. You can think of this as demanding that each function object that is created has to be a completely new copy and not inherit anything that the previous function had.

Recursion becomes complicated when you start to use parameters passed by reference or global variables. To keep things simple always use local variables and pass by value within recursive functions.

Following a Call counter(0) which gets it going, it first tests to see if the counter , i.e. “i”, is 5. If it is then the function ends. If it isn’t, it has one added to it and the counter is called again.

Clearly this is a finite recursion as eventually the counter function will be called with a value of 5 and the recursion comes to an end. In this case we have five recursions, and five instances of the counter function.

No problems but ask your self what is printed? If your answer is 1,2,3,4,5 then you need to think a little more carefully and look at the diagram below.

Nothing gets printed until i reaches 5 when the next copy of the count function comes to an end and the final copy continues on to print the value of i. Then it comes to an end and the previous instance of the object gets to carry on and print its value of i and so on back to the first copy. You should now be able to see that what is printed is 5,4,3,2,1.

 

rec2

Recursion spirals one way and then back the other.

 

It is helpful  to think of recursion as having a forward phase when the "instances" of the function are being created and a backward phase when the functions are being destroyed. You could say that recursion spirals its way out and then spirals back in the opposite direction but this might be taking things too far for some!

Even so there is a sense in which the shape of the flow of control for a recursion is a spiral that you work your way along and then work your way back along when the recursion comes to an end. If it helps think of it in this way.

<ASIN:0465030912>

<ASIN:0465030785>



 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.