Mr. Cluey : Special Topics : Recursion...

Recursion

Recursion

If you get it, stop.

Otherwise, see Recursion

Infinite Recursion

See Infinite Recursion

Recursion on the web

There is an excellent example of HTML recursion here.

Using Recursion in QAP

Recursion is frequently helpful when dealing with contructs that have children which resemble the parent. For instance, windows have child windows; directories have sub directories.

Often you will want to visit each item in such a list, and do some thing to it ( checking spelling, opening files, counting links, etc. ) You are going to be doing the same thing over and over, so why not reuse the same function?

Recursion is a very powerful tool, but at the same time, it is extremely easy to abuse. Steve McConnell's Code Complete summarizes the major issues in recursion fairly well.

Here is a fairly straight forward example of recursion

VerifyWindows ( window wCrnt )
{
	// First, verify the current window.
	wCrnt.Verify () ;

	for each wChild in wCrnt.GetChildren()
		VerifyWindows( wChild ) ;
}

Each window in turn first verifies itself, then queues up each of its children to be verified. Thus, this simple statement:

VerifyWindow( wMainWin ) ;

verifies every single window in the application!

Ok, that's a straightforward example. Is it a good one? Maybe. Probably not. Here's what McConnell has to say...

You should consider alternatives to recursion before using it. You can do anything with stacks and iteration that you can do with recursion. Sometimes one approach works better; sometimes the other does. Consider both before you choose either one.

Here is how VerifyWindows could be written using a list.

VerifyWindows( window wCrnt )
{
	list of window lw = { wCrnt } ;
	window w ;
	for each w in lw
	{
		w.Verify() ;
		ListMerge( lw, w.GetChildren() ) ;
	}
}

In this case, we have changed the order that the windows are verified, but that can easily be fixed by treating the list of windows as a stack, removing windows when they have been verified and merging the children at the top of the list.

VerifyWindows( window wCrnt )
{
	CStack theStack ;
	theStack.Push( wCrnt ) ;
	
	window w ;
	while theStack.Pop(w)
	{
		w.Verify() ;
		theStack.PushList( w.GetChildren() ) ;
	}
}

Is one of these better than the other? My rule is that the version which is easiest to understand, the easiest to maintain, or the easiest to generalize is the one that should be used.