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?
A Simple Recursive Function
While the Fibonacci is fun and shows that a recursive function is possible in ActionScript 3.0, it doesn’t really show too much about the inner workings of the recursive method. So I put together a simple class with a recursive structure.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | // Simple Recursion package { import flash.display.Sprite; public class Simple extends Sprite { public function Simple() { trace("End value: "+recursive(10)); } private function recursive(n:uint):uint { if(n<=1) return n +100; else trace("Trace:"+recursive(n-1)); return n; } } } |
Keeping in mind that every trace() of the function fires the function, we need to be judicious in where we place our trace statements. In the recursive function, recursively named, recursive, the return in the first condition adds 100 to values of less than or equal to one. (I could not concatenate a string because the return must be an unsigned integer.) The class generates the following output:
Trace:101
Trace:2
Trace:3
Trace:4
Trace:5
Trace:6
Trace:7
Trace:8
Trace:9
End value: 10
As you can see, the first return value is 1 plus 100. After the first value, the next is 2, and so forth until 9, and then the terminal output occurs as 10, the value of the initial function argument.
This little excursion into recursion is another side trip on the way to a ground up Prototype design pattern that I’m still working on. I’ve looked at a lot of examples from different languages; unfortunately, they have certain built-in features for cloning or abstract classes lacking in ActionScript 3.0—or ECMAScript 264, ref 4. However, like all of the other patterns, eventually this one will get wrestled to the ground.
The An ActionScript 3.0 Recursion Excursion by William B. Sanders, unless otherwise expressly stated, is licensed under a Creative Commons Attribution-Share Alike 3.0 United States License.
Bill Sanders
nice article,
anyway, recursion is very dangerous with Flash platform because all script is executed per frame, so if you do deep recursion you can get your flash stucked… that’s why flash limit of 256 levels of recursion
also, important thing is that any recursion can be transformed to iteration function, which needs a little bit more writing but it’s very nice programming problem
hi mrSteel,
recursion may be dangerous in term of animation but sometimes you need id… so the answer would be that if you need your result right now just do it this way, otherwise you could use a timer or an enter frame listener so the animation can go smoothly during the recursive function call
nice article btw
Mr Steel and Gropapa,
Thank you for your comments. I had not considered the impact of a recursive function on the timeline. One of the main reasons I prefer to subclass to the Sprite class and not the MovieClip class is that the former has no timeline. The nice thing about Flash/Flex with ActionScript 3.0 is that you can choose to use the Timeline or not.
Would either of you be interested in providing an example of where a recursive function runs into problems with the Timeline? Or how you might use a recursive function with a timer?
Thank you both for your insights,
Bill
yep, solution can be to use a recursion with a timer :)
level : 1112 1.10858999763490e+232
[Fault] exception, information=undefined
Fault, fibonacci() at Recursion.as:24
it’s pretty good looking how it was before fp10, I think even 9 had lower limits
so yep recursion is great thing, should be used carefully but in flash you don’t need hardcore recusion, and with simple one you can gain a lot
goin from recursion to iteration is important step in learning programming anyway, at least it helped me a lot on complex algebra problems
Hey Alex,
Thanks for taking the time on that. Love those Fibonacci sequences!
Kindest regards,
Bill
nice article, but let me point out two things:
the fibonacci example above is the (no diss intended) naive way as it takes exponential time to compute as each recursion needs to calculate the whole sequence of numbers before it -recursively- (in the statement return fibo(r-1) + fibo(r-2); )
not nice ;)
Fibonacci is a case of a problem that can be handled generically with dynamic programming (or memoization), in which you would store the previous calculated output (for fibonacci, this can easily be done in an array to avoid recomputation. Making this change lets the calculation execute in lineair time !!!
Also, as the numbers grow exponentially, values grow very fast.
fibo(45) is actually the largest number that can be represented by a 32 bit integer!
Hi,
I really think this issue boils down to design. When an application is designed from the base up, constraints are found and implemented into the design.
I work with recursive functions quite a bit, Flash 5 -> now. When you run into problems with this is when you are creating a call stack that involves other methods being called indirectly from a recursive method.
IE dispatchEvent() is dangerous in a recursive method.
Once you get experience with the limits of the engine that runs your code (IE Flash Player), you know intuitively where the red line is and don’t even attempt some things (switch from defense to offense).
A lot of the time a recursive function can be refactored into a batch or other related pattern.
Experience gives forward vision and allows an abstract view before any emergency in code throws a stack overflow.
Mike
Hi Rolf,
The point you make is certainly valid and it’s probably one I should have included. However, the Fibonacci is used to illustrate how recursion works, and while it is not the most efficient way to generate a Fibonacci sequence, it reveals the nature of the recursive function.
Of course you are quite right, though, that a recursive function is not the best way to generate a Fibonacci value. It’s just a fun way to show recursion.
Thanks for your insightful comment,
Bill
Hi Michael,
Refactoring a recursive function sounds interesting. We’d love to see an example of how you do that in ActionScript 3.0.
Thanks,
Bill
what is wrong here i beginer please help me
Hi Davit,
What’s this supposed to do and what does it have to do with recursion? Or design patterns? What library elements do your have?
Thanks,
Bill
Hi i want to write game lines and I want to employ recursion when we want to move ball from one place to another place;I want to create a recursive function where we must keep neighbor bars of bar where we want to move the ball, I haven’t any library elements. What advisory you give,and can you say what’s wrong here? Thank you very much and I am apologize for my bad English
Hi Davit,
First of all, no need to apologize for your English—it’s much better than my Russian.
You have so much code here that it’s hard to untangle. Here’s what I’d suggest:
Create a series of 1 ball (or square) with 1 recursion. Start with something simple that works to generate your objects (or array elements).
Right now, you have several classes that you have not defined in the code you sent. square is a class, but I have no idea what is in it.
So, first back up into a workable recursive algorithm (one that was used in the example or from elsewhere.) Then, with a simple recursive algorithm, one thing (a ball or square). Then add from that point.
If you can, put them into a design pattern so that you can re-use the code.
Kindest regards,
Bill
I’m not an expert in actionscript… I think recursion is much more powerfull then looping with a for or a while statement. (even thought most of times less efficient). But with recursion you can treat recursive structures in a breeze, like binary trees (not very used in actioscript, i know..) or doing a floodfill algorithm. Recursion allows going throught ramifications while looping is a linear operation…
By the way, In my university, I learned recursion before loops too.. :D (Haskell first where recursion is a must before C)
Hi Joxnas,
I tend to agree with you. In talking with the chair of the Computer Science Dept. at my university, he said the same thing. The stack overflow issues must be considered, but if you implement a recursive operation correctly, you’re not going to have that problem anyway.
Oddly, I’ve been having difficult time articulating why I like recursion more than loops other than they seem to better reveal what’s going on and I like the way they use the stack. So all of your points are well-taken.
Kindest regards,
Bill