ColdBlue.Net

Time to break away from forms and their interaction with a database, and time to get back into user-defined functions. I want to show you something that you might encounter, and that is the use of recursion with UDF’s.

Using Recursion with User-Defined Functions

Recursion is when we have a function (user-defined function) and inside that function we call the function itself. Sounds confusing doesn’t it? To better understand this, let’s talk about factorials and what they are. Let’s say n is 5, we would write this as 5! which would be the same thing as saying (5 x 4 x 3 x 2 x 1), this would come out to being 120. It is basically whatever the number, n, times all the way to one. This is essentially what a factorial is.

Let’s create a template and name it factorial.cfm, and paste this source code into it:

<cffunction name="Factorial" returntype="numeric" output="yes">
	<cfargument name="n" type="numeric" />
	<cfif arguments.n eq 1>
		<cfreturn 1 />
	<cfelse>
		<i>n</i> is now #arguments.n# <br />
		<cfreturn arguments.n * Factorial(arguments.n-1) />
	</cfif>
</cffunction>

<cfoutput> #Factorial(5)# is 5! </cfoutput>

Let’s go over this example so that you will have a thorough understanding of it. In our last line of code between the <cfoutput> tags we called a UDF that we created, called “Factorial”, and passed an argument of 5 into it. Up in our <cffunction> you can see we added two attributes to it, one specifying the return type, and the other allowing us output (this means basically our function is wrapped around in <cfoutput> tags so that we can call variables via the pound signs). So 5 is passed into our <cfargument> tag, which checks to see if it is numeric since we added that attribute. We have an if-statement that checks to see if the argument n is equal to one, n is 5 so it goes straight to the else-statement. The else-statement prints “n is now 5″, then we hit the <cfreturn> tag that returns 5 times  the Factorial(5-1), which translate into 5 times Factorial(4). Factorial(4), has the argument of 4 which is then passed to the function Factorial(), then we get to 4 times Factorial(4-1)….3 times Factorial(3-1)… 2 times Factorial(2-1)… then our if-statement becomes true.

The if-statement (which checks to see if n is equal to 1) is what is called a base case, it is what stops the recursion process from becoming an infinite loop. Now that n is equal to 1, the <cfreturn> tag returns 1. Halting the function from processing the <cfelse> statement again. Now the Factorial function can answer all the questions that it was trying to return… 5 times Factorial(4) all the way to 2 times Factorial(1), which results into 120.

You might ask yourself what the heck, how did all of this stuff get stored, and then once it hit the initial return statement, the one that returns 1, print the sum of 120? This is where recursion gets tricky, and is a hated topic of computer science. Most tutorials will stop here and not go any further. And you would just go on blind faith that this technique somehow works. In the second <cfreturn>, every iteration of that return statement stores that value into a section of memory called “the stack”.

To briefly go over the stack, let’s think of terms of functions. When you call a function, the computer has to remember the spot where you called that function, then go to that particular function. When it goes to that function there may be other functions inside that function. So it has to remember another spot. It tosses each remembrance on top of each other, which you can now visualize as a stack of papers. Then it goes back and returns the results starting with the top of the stack.

Going back to our example, I am going to go over this entire process with just a simple 3! factorial for a better understanding.

[3 * Factorial(3-1)] – N is now 3, the value of N is now known, but the value of Factorial(3-1) is not known. So the value of 3 is stored into the stack (which is a section of memory).

[2 * Factorial(2-1)] – N is now 2, the value of N is now known, but the value of Factorial(2-1) is not known. So the value of 2 is stored into the stack.

The Factorial function now calls itself with the value of 1, Factorial(1), so now the if-statement kicks in and returns one. Now the value of Factorial(1) is now known, once this occurs it becomes a backwards loop and reverts back to it’s second execution. Pulls up the value 2 from the stack and times it by Factorial(1), which now equals Factorial(2), and pulls up again from the stack, the value of 3 and times that by Factorial(2), which is now 6, and this is the value the function finally returns (since there is nothing left in the stack).

As a note, the stack is limited, and there is only so much that it can hold. So if you do something like this:

<cffunction name="CrashMe" returntype="numeric" output="yes">
	#CrashMe()#
</cffunction>

<cfoutput> #CrashMe()#</cfoutput>

This would make the application server toss an error after spending time processing it. This would keep calling itself non-stop, over and over again, and since the stack is limited, it will crash.

How would you write our Factorial function in a standard index loop (for loop)?

<cffunction name="IndexFactorial" returntype="numeric" output="yes">
    <cfargument name="n" type="numeric" />
    <cfset variables.value = 1 />
    <cfloop index="i" from="1" to="#n#">
        <i>n</i> equals #arguments.n# <br />
        <cfset variables.value = variables.value * #arguments.n# />
        <cfset #arguments.n# = #arguments.n#-1 />
    </cfloop>
    The factorial(<i>n</i>) is equal to:
    <cfreturn variables.value />
</cffunction>

<cfoutput> #IndexFactorial(5)#</cfoutput>

You could have also written this example as a conditional (while) loop. As you can see, the recursive factorial function was more elegant compared to the index loop factorial example. Sometimes it is better to use a recursive function to do work, it just depends.

Let’s go over this example. We called our function, IndexFactorial, with the argument of 5, which is passed to n inside our function. We set a variable named value to 1, then we begin our index loop. The index attribute is set to “i”, our from attribute is set to 1, and our “to” attribute is set to n, which is 5. The loop displays each iteration of n, it also sets the variable “value” to value times n. So variables.value equals 5 (1 times 5). The next line sets the value of n as n-1, which means that n now equals 4. Now we go back to the top of the loop for our second iteration, variables.value is set to “5 times 4″, and n is now set to 3, and these iterations continue on. Once n is equal to zero, the index loop exits out and returns the value of variables.value.

Fibonacci Sequence

One of the classic uses of displaying recursion is via the Fibonacci Sequence.

<cffunction name="Fib" returntype="numeric" output="yes">
    <cfargument name="n" type="numeric" />
    <cfif (arguments.n eq 0) or (arguments.n eq 1)>
        <cfreturn arguments.n />
    <cfelse>
        <cfreturn Fib(arguments.n-1) + Fib(arguments.n-2) />
    </cfif>
</cffunction>

<cfoutput> #Fib(10)#</cfoutput>

How the Fibonacci Sequence works is that a number, in the sequence, is made up of the sum of the two previous numbers. Here are the first ten numbers of the sequence: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]. So the 10th number in this sequence is 55, that number is the sum of 21 + 34.

Recursion can become very complicated, and this tutorial is just an introduction to the topic.

Tags: factorial, fibonacci, recursion, user-defined functions