Week 13 - Chapter 14 - Recursion

A Little More OOP Theory

You thought we were done with OOP theory, well you were wrong! :-) I wanted to make sure to mention this at some point in the class, and this week, being a light one, is as good as any.

There are three and only three relationships that objects can have:

The following code snippet illustrates each case:

	class Truck extends Vehicle
	{
		Engine eng;
		GasTank tank;

		...

		int fillUpTank (Gas g)
		{
			...
		}

		int repairEngine (Tools t)
		{
			...
		}

		...
	}

Truck has an is-a relationship with Vehicle, because it is a descendant.

Truck's relationship with Engine and GasTank is has-a because they are properties of Truck.

Truk has a uses relationship with Gas and Tools because it takes them as parameters to its methods.

Note: If you ever use a more "pure" OO language (like Java or Ada), these are the only relationships your objects can share, since no code can exist outside of a class namespace.

Recursion Theory

Definition A recursive function is a function which calls itself.

The idea of recursion is to reduce a complex problem to a smaller instance of itself. Once the problem has been reduced to the simplest instance possible, we then solve that simple case and we're done.

Requirements for Recursion

(p. 591-592) In order for a recursive function to work properly, there are three requirements.

Look at the tiny IF block about a third of the way down page 592 for a stripped-down example of how a recursive function should look.

Winding / Unwinding

There are two phases to a recursive call:

The following code snippet illustrates where these phases occur in code:

	void recursive_proc(String arg)
	{
		// This is the winding phase
		some_code(arg);
		...

		// This is the exit condition
		if (arg.length == 0)
			return;

		// This is the recursive call
		recursive_proc(arg.substring(1));

		// This is the unwinding phase
		some_other_code(arg);
		...
	}

Recursion Errors

Infinite Recursion occurs when you don't implement an exit condition, or don't implement it correctly.

(p. 596) Stack Overflow is the most common exception encountered when dealing with recursive programs. Each time you call a function (recursive or otherwise), a hunk of memory called the stack frame is allocated on the program stack for storing the function's parameters and local variables. As you can imagine, recursive functions push a lot of frames onto the stack. A stack overflow exception will be raised if you don't have a propper exit condition in place (a side effect of infinite recursion), or there are simply too many calls in the winding phase for the available memory in the machine.

Other Types of Recursion

There are a few more involved forms of recursion.

Indirect Recursion

A function f1 calls f2 which calls f3 which calls f1. This kind of recursion is more complex and potentially more hazard-prone. Fortunately, you will rarely need to use it. Some complex data structures (such as N-way trees) might require that you use indirect recursion.

Tail Recursion

A function is said to be tail recursive if the recursive call is made as part of the return statement and the call is not part of an expression.

We should make functions tail recursive when possible because most compilers can optomize for them. When the recursive call happens, the program does not need to push another fram onto the stack. Instead, the compiler simply replaces the last stack frame with the results of the current stack frame. This makes it possible to recurse very deeply.

Maybe we'll do an example of tail recursion in class.

Recursion vs. Iteration

It is worth noting that every recursive function can be implemented in an iterative fashion instead (i.e. a for loop). For some situations however, recursion is a more elegant approach. An example of a case where iteration might be preferred would be traversing a singly-linked list. For an example of a problem which can be solved with either recursion or iteration, see the Factorial examples on page 598-600.

Recursion Examples

There are numerous situations that lend themselves to recursion. Many math functions can be solved with recursion. Some examples:

Ada Stuff

Recursion is performed in Ada as it is in any other procedural language. There are no special keywords or constructs that you need to learn here.

Assignment 11

Write a program containing a recursive procedure that finds and prints all the factors of a Natural number. This program will be amazingly short.

Hints: The recursive procedure will require two arguments, both Naturals. You may want to make an additional "driver" procedure that just takes one argument and then calls the recursive function. You don't have to do this, it's up to you.

Due Date

This assignment is due on December 5th, 2001, the night of the Final Exam!

Oh yeah, Happy Turkey Day.