Monthly Archive for October, 2008

Recursion is one of those things I’ve been thinking about lately because of the recursive classes in the Prototype pattern. However, recursion isn’t something that I think about much, but at the OOPSLA conference in Nashville that is just now wrapping up, it came up in as a favored method over loops. A professor from Cornell University was making a presentation at one of the sessions I attended, and he noted that they introduce students to recursion before introducing loops , getting enthusiastic approval from some in the audience. Because I’ve been beating my head against the Prototype pattern, this was more than a little interesting. What’s so special about recursions?

Another Loop?

In some respects, recursion is just another looping structure, but programmers tend to think about them differently, and I thought I’d see what I could find from some of the big brains at OOPSLA. I talked with Dr. Axel Schreiner about recursion and got all I could ever imagine anyone would want to about them. However, like many, he considered recursion to be a loop structure and didn’t seem to be particularly excited whether loops or recursive structures were employed. For Axel, recursion and looping were a matter of looking at repeated actions in different ways.

Defined, a recursion is a method (or function) that can call itself. That doesn’t sound like a loop, but it does have a repeating element in that a recursive function repeats a process by the simple fact of calling itself. The most common examples of recursion is a factorial, but Fibonacci sequences and Towers of Hanoi are other common examples used to illustrate recursion. Since Fibonacci sequences are one of those just plain cool math structures, I thought I’d start with a Fibonacci sequence.

A Fibonacci Example

A Fibonacci sequence is one where each number in a sequence is made up of the sum of the previous two in the sequence. The sequence begins with 0 and 1:

0 1 1 2 3 5 8 13 21

Rather than using a loop to generate the sequence, the recursive function in the following example takes a parameter (r) and returns the next value in the sequence after r. The following class calls the recursive function via a trace() statement. (I was using Flex, but Flash works fine for the same function.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/*Fibonacci  generated in a recursive function*/
package
{
	import flash.display.Sprite;
 
	public class FibRecursion extends Sprite
	{
		public function FibRecursion()
		{
			trace(fibo(8));
		}
 
		private function fibo(r:uint):uint
		{
			if(r==0)
			{
				return 0;
			}
			else if (r==1)
			{
				return 1;
			}
			else
			{
				return fibo(r-1) + fibo(r-2);
			}
		}
	}
}

The recursion occurs in the third return statement. That is, part of the fibo() function calls itself. As you will see, the output is,

21

The question is, what’s going on inside the cursive function?

Continue reading ‘An ActionScript 3.0 Recursion Excursion’