CS150 Lab 5: Recursion, the Dream in a Dream in a Dream....

Due Sun. Oct. 29, 2000 at 11:59 PM

In this lab you will discover one of the most powerful and fundamental programming techniques:  recursion.    Recursion is a way of programming the processing of multiple entities such that at any given moment, one is dealing with only the local issues, not the global issues of the entire collection of entities being processed.    Recursion is a natural outgrowth of an inductive proof, as the illustrated by the classic "if you can get onto the first rung of a ladder and you know how to get from any arbitrary rung to the next, then you can climb the whole ladder."  Recursion is a very important tool in the OOP arsenal, but is certainly not limited to OOP.   It appears in procedural programming (C, Basic, Fortran, Pascal, etc), but perhaps more importantly, it is at the very foundation of functional programming languages such as Lisp and Scheme.   When you take CS275, you will notice striking similarities between this lab and the first Scheme lab in CS275.

Recursion can be a very difficult concept to grasp and even harder to master.   I suggest making lots of diagrams (object diagrams tend to be more useful here than class diagrams) and spend a lot of time discussing it with your classmates.    And of course, raise any and all questions you have during class and lecture so the instructors can address them.  

Try to understand recursion in terms of it being a local description of a global phenomenon.

The Recursive Way

Recursion works by having a method in one object call the exact same method in another object (which may be itself).   If all the objects are linked in some manner, i.e. all have references to one other object in the collection, and all objects are referenced by some other object, then by the time the first method exits, all the objects will be accessed and processed.

In order to do recursion one needs a collection of objects where:

1. Each object contains at least one property or local variable that is a reference to another object in the collection.
2. All the objects in the collection are referenced by at least one other object.
3. Each object contains the recursive method which has the following properties:
   1. Every object in the collection has the same method with the same signature.    This implies that all the objects must either extend or implement the same superclass or interface.
   2. The method has this basic structure:
      1. Initial processing steps:   What ever needs to be done in this object may be done here.
      2. The "recursive call":  The call to the method of the  same name  in the referenced (next) object.   This call may or may not return a value.   
      3. Final processing steps:   Additional processing for the present object that needs to be done, is done here.   Usually, these steps would involve the return value of the recursive call, since it is not known until this stage. 
      4.  Return from the method:    The return value will usually involve the return value of the recursive call.   This step may be condensed with the the previous one or two to create more compact code.   Code that has no final processing step and simply returns the value of the recursive call is labeled "tail recursive".

Below is an example of generally what is happening in three linked objects during the call to the recursive method of the first object:

One thing to notice about the above sequence is how any given object is forced to wait until all the successive objects have finished before it can finish.    See the state of Object1 and Object 2 in Steps 2 and 3 above.   These are called "pending calls" and often referred to being "stacked" (a reference to the stack implementation of recursion that is used in most modern microprocessers).   Try viewing the above process like one of those New Year's party favors that rolls out then back in when you blow in it.

However, the most important thing to notice is

Recursion processes the entire collection of linked objects through only one method call of only one object in the collection.

If you look back at the movie loop program, you will see that it was done with what was essentially a modified recursive methodology.

The Two Cases of Recursion

You might be asking yourself, "But what if I don't want to process the entire collection?"  or "How can I tell if I am at the last object in the collection"?     Good questions indeed.

Recursion always involves two different cases:

1. The Base Case :  The is the situation encountered when there are no more objects to process.    This is the end-of-the-line for the recursive call and the traversal back up the recursive stack of pending calls will definitely begin here.
2. The Inductive Case :  This is situation encountered when there exists a link to the next object.   A decision often needs to be made here whether or not to terminate the recursive call and roll back up the recursive stack or to keep going deeper into the recursion.

Hmm... we have two different situations that perform the same abstract process (the recursive method), but yet have different implementations....

What should the class (UML) diagram for a recursive process look like?   

To see this, let us exam the "Lisp List", which is a linked list like the circular list, but is linear instead.   See the first lab section on the left. 

After you have completed your work on the Lisp List, you can create your own recursive methods for it in the second lab section on the left.

Warning:   Do not attempt to write your own recursive methods until you fully understand how the example methods work!