Finance Developer (IL) Next Step Systems US-IL-Chicago Post A Job | Post A Resume

Before I begin, a disclaimer: I realize that this is somewhat of an obscure topic. Your computer science majors should know what recursion is, but I doubt that many non-comp. sci. majors do. Furthermore, I will be showing an example of recursion on Microsoft's TreeView control, a control many ASP developers are not familiar with (unless they're VB developers as well), although, just so you know, you can use the TreeView Control as an ActiveX control on your web pages. This article will first discuss the basics of recursion and why it is powerful. Next, a simple, classic recursion problem will be demonstrated (finding factorials), and then I will show you how to visit all nodes in a TreeView Control.

What is Recursion?
I'm glad you asked. Recursion is repeatedly calling the same function to provide some meaningful output; at least that's what a computer scientist will tell you. A more mathematical definition of recursion is plugging in some start values into a function, getting the function's results, and reapplying them to the orginal function. Recursive functions often have odd sounding explanations. A factorial can be explaned in recursive terms. (In case you don't know, the factorial of n, written n!, is n*(n-1)*(n-2)*...*(n-(n-1)). So, 5! (pronounced five factorial) is equal to 5*4*3*2*1, or 120.

A factorial can be defined recursively as follows:

Start out with some natural number N (in our example, 5)
The factorial of N is N * the factorial of N-1.

So, if we let N be 5, then 5! is 5*4!. Now, we "recurse", letting N be 4. So 4! is 4*3!. So 5! = 5*4*3!. (I know most are probably lost now. We started out with 5 factorial, and then let 5 factorial equal 5*4 factorial. We then let 5 factorial equal 5*4*3 factorial, by repeatedly applying the recursive definition of factorial.) So, 3! is 3*2!, 2! is 2*1!, 1! is 1*0!, and 0! is defined to equal 1. So,

5! = 5*4! = 5*4*3! = 5*4*3*2! = 5*4*3*2*1! = 5*4*3*2*1*0! = 5*4*3*2*1*1

which, lo an behold, equals 120. We applied the recursive definition of a factorial to go from 5! to 120.

Now you may be wondering how in the world you write code to do this. Well, you simply write a function that will call itself. Here is the factorial function in VBScript:

function factorial(N)
  if N = 0 then
	factorial = 1
	exit function
  end if
  
  factorial = N * factorial(N-1)
end function

If you were to do:
Response.Write factorial(5)

Your output would be: 120. The above function has all of the same rules that our mathematical recursive definition of a factorial did. We define 0! to equal 1, and we define factorial N (where N > 0), to be N * factorial(N-1). All recursive functions must have an exit condition, that is a state when it does not recurse upon itself. Our exit condition in this example is when N=0. If you do not have an exit condition, you're recursive function will recurse forever until you run out of stack space. To make a long story short, you'll receive some nasty error about lack of memory, or stack overflow.

You're probably wondering what is really happening in the code. You can see if you trace the flow of the function through. It can be difficult at times, but you must be able to do this to fully understand recursion.

When the factorial function is first called with, say, N = 5, here is what happens:

FUNCTION:
Does N = 0? No
Function Return Value = 5 * FACTORIAL(4)

At this time, the function factorial is called again, with N = 4.

FUNCTION:
Does N = 0? No
Function Return Value = 4 * FACTORIAL(3)

At this time, the function factorial is called again, with N = 3.

FUNCTION:
Does N = 0? No
Function Return Value = 3 * FACTORIAL(2)

At this time, the function factorial is called again, with N = 2.

FUNCTION:
Does N = 0? No
Function Return Value = 2 * FACTORIAL(1)

At this time, the function factorial is called again, with N = 1.

FUNCTION:
Does N = 0? No
Function Return Value = 1 * FACTORIAL(0)

At this time, the function factorial is called again, with N = 0.

FUNCTION:
Does N = 0? Yes
Function Return Value = 1

Now, we have to trace our way back up! See, the factorial function was called six times. At any function level call, all function level calls above still exist! So, when we have N = 2, the function instances where N = 3, 4, and 5 are still waiting for their return values.

So, the function call where N = 1 gets retraced first, once the final guy returns 0. So, the function call where N = 1 returns 1*1, or 1. The next higher function call, where N = 2, returns 2 * 1 (1, because that's what the function call where N = 1 returned). You just keep working up the chain.

Where N = 2, 2*1, or 2 was returned
Where N = 3, 3*2, or 6 was returned
Where N = 4, 4*6, or 24 was returned
Where N = 5, 5*24, or 120 was returned

And since N = 5 was the first function call (hence the last one to be recalled), the value 120 is returned.

I hope you are still with me. Recursion is a tricky subject, but an important and powerful one. I will now show how to recurse through ALL the children in a TreeView structure.

A TreeView Control is a hierarchy. There are an undetermined number of levels in the hierarchy, and each node in the hierarchy can have zero or more children on the next lower level of the hierarchy. Microsoft provides an example script of how to list all of the children of a particular node at http://msdn.microsoft.com/library/devprods/vs6/vb/html/vbprochildrenx.htm. However, if you want to visit every single node, then you need to use recursion (well, technically you don't need to, but it's an easy way to make sure to visit every node).

Without further ado, here's the script:

sub TraverseTree(strKey)
	Dim iIndex

	if parent.frames(0).tv.Nodes(strKey).Children > 0 then
		'We have children, we need to iterate through our children
		iIndex = parent.frames(0).tv.Nodes(strKey).Child.Index
		TraverseTree(parent.frames(0).tv.Nodes(iIndex).Key)		
		
		While iIndex <> parent.frames(0).tv.Nodes(strKey).Child.LastSibling.Index
			iIndex = parent.frames(0).tv.Nodes(iIndex).Next.Index
			TraverseTree(parent.frames(0).tv.Nodes(iIndex).Key)		
		Wend
	end if		

	'Here is where you will want to put whatever processing you want done
	'on each and every node.
end sub

This function is called by passing in the Key of the node that you want to start at. It won't neccessarily visit all of the nodes in the tree, but will visit all of the children of the node's Key you pass in (including the passed in node as well). To reiterate, Microsoft's script will visit all of the direct children of a given node; the above script will visit ALL descendants of a given node (including the given node).

Well, I hope I didn't confuse too many of you, and I hope you found this to be an interesting topic! I know I do! :)

Happy Programming!

Windows Internet Technology | ASP.NET [1.x] [2.0] | ASPMessageboard.com | ASPFAQs.com | Advertise | Feedback | Author an Article