Repeated operations are handled either by recursion or loops (iteration). One of the fundamental structures of programming is loops, and we programmers tend to think, If I need to repeat an operation, I use a loop. Loops are built-in structures of most languages, and ActionScript 3.0 has multiple options when it comes to loops. ActionScript 3.0 has the standard for (and variations), while, and do statements as well as looping methods for arrays and vectors. So if we need to repeat a set of operations, we have several iterative statements that will get the job done for us.
Why Bother With Recursion?
In most (but certainly not all) situations, iteration is faster than recursion, and so why should we even consider recursion? Recursion is nothing more than a method that can call itself that uses more memory than iteration and fills up the stack quickly. You’ll get a stack overflow with recursion both with big numbers and with infinite loops. Loops can handle big numbers better, and while they eventually blow a gasket with an infinite loop, they take longer to do so because iterations are not stored on the stack.
Despite what some programmers would see as the end of the conversation comparing iteration with recursion, I was able to find two good reasons to consider recursion over iteration.
- The code can be clearer and simpler
- Recursion offers more elegant solutions
With the caveat that the following is not a call to abandon loops, let’s take a look at the reasons you should consider recursion the next time you come across a task that requires repeating operations.
Clear and Simple
Sometimes we come to a problem where we want to lay out all of the options to better see what’s going on. With loops, especially with complex ones that involve nesting, we can quickly find ourselves spinning our wheels. On the other hand with recursion, we can lay out the steps in a series of statements that clearly show the options we have to consider.
For example in the previous post on this blog examining the construction and use of skip lists, the search algorithm uses recursion. In the stripped down version of the search method, we can clearly see the repeated steps taken in the search routine:
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 30 31 32 33 34 | public function searchList(searchKey:uint,layNum:int):int { this.searchKey=searchKey; if (initial) { layNum=4; searchNode=headNode; initial=false; } if (searchNode.contents==searchKey) { trace("success"); return searchNode.contents; } \ if (layNum<0) { trace("Number not found"); return -1; } if (searchNode["skip"+layNum].contents<=searchKey) { searchNode=searchNode["skip"+layNum]; } else { layNum--; } return searchList(this.searchKey,layNum); } |
The steps are clear to see how the search works its way through the skip list to find whether a given value were included:
- If it’s the first time through, begin at the top level in the head node.
- If the search key matches the node contents end the search and return the found contents.
- If the layer is below 0; end the search and inform the user that the value was not found.
- If the next node is greater than or equal to the search key, the search node becomes the next node
- If the next node is less than the search key, move down a layer
- Run function again if nothing is returned
Not only is it easier to work out the algorithm, it’s a lot clearer. You can actually see what’s going on and show another programmer so that they can see as well. (Agile programming anyone?) Where you have very large numbers and a high number of repetitions, you’ll probably want to use a loop, but for working through the initial problem, recursion can be a valuable aid. (One unanticipated advantage of stack overflow is that I found that I had walked into an endless loop sooner than using a loop structure!)
Recursion as an Elegant Solution
On an intuitive level I can see recursion as an elegant solution to most tasks that require repetition; however, I believe that if you come up with an elegant solution with recursion, you can probably duplicate it using a loop.
The rules guiding a recursive solution are simple enough:
- To prevent infinite recursion, a recursive method must include a condition under which no recursive call is made —a base case. (Our example had two base cases—the search item is found or we run out of levels.)
- To prevent infinite recursion a recursive method makes progress toward the base case. (Our example progressively moves through the skip list nodes.)
Those two simple rules provide the elegance one looks for in most programming solutions. The more complex the problem, the more need for recursive solutions in that they reduce the complexity. Recursion leads to simple elegant techniques to solve problems. In the end, they may have to be converted to loops, but overall, I see them important tools in building good solutions.
The Recursion vs. Iteration: Elegance or Speed? by William B. Sanders, unless otherwise expressly stated, is licensed under a Creative Commons Attribution-Share Alike 3.0 United States License.
Bill Sanders
I guess it’s always a good thing to consider alternatives and broaden one’s horizon in general. However, in this case, and if i get your point correctly, there is no other gain than perhaps a cosmetic improvement to the source files in it.
I believe that good, profitable programming comes with consistent good habits and an efficiently performing end product. The latter being especially important nowdays when Flash is under attack for being a CPU hog. In that respect, I urge Flash developers to focus on being accountable, effective and writing code that runs cleanly instead of looking clean. Not that one necessarily excludes the other, but it’s about what you put first I guess.
I’m actually one of the worst programmers I know when it comes to constantly refactoring, restructuring, renaming and prertifying code in general. So I’m appealing to myself here as much as anyone else :)
Hallo Øyvind,
This detour into algorithms is one to consider alternatives to common thinking about programming. This is not just about code being pretty and readable; it’s about thinking through solutions and considering alternatives. In many respects, I’m trying to look at algorithms with the same mind set as we look at design patterns.
Design patterns take longer to create initially, but over time they more than pay for themselves because of their re-usability and the ease with which they can incorporate change. If you cannot effectively read and re-use code, then you’re stuck with re-writing it.
By the same token, readable code need not be inefficient. In fact, if you’re only focused on speed, you may end up losing both speed and readability. That’s because, you’re not thinking about relationships between objects, either between participants, or, as this set of posts has suggested, within classes.
As noted, the post was not a suggestion to abandon iterative solutions (loops), but rather use the advantages of recursion where you can.
Aller forhold,
Bill
In 90% of cases, we choose the loop. The flash runtime is slow.
The remaining 10% cases is where code clarity is key, because we’re expecting the code to be changed often, ALL WHILE it’s not time-critical (relatively low number of iterations, gets called occasionally, is not part of a bigger and time-consuming subroutine.
Hi Archont,
I’m curious how many have ever used recursion. In reading about the two ways of repetition, some have even found that in certain applications that recursion is faster than iteration.
You might note that in the original skip list example, we used iteration (a loop) to generate both the nodes and pointers. I like to think of recursive methods as untanglers in that they clarify the processes. As you and Øyvind say, most of those processes may need to be changed to loops for the optimum speed, but I believe you can save a lot of development time by considering recursion and using it to sort out the optimum process.
Kindest regards,
Bill
I didn’t read your post as a suggestion to abolish iterative constructs. Nor do I consider optimizing for reuse to devoid performance in general.
I should clarify that I’ve read your book back to back and found it very educational. I use singleton, observer, MVC and state patterns daily and I honor them pretty strictly. And much of my code is recycled many times over. So I’m no stranger to the benefits elegant code and design patterns. But most importantly to me is that I spend a great deal of time /thinking/ about code, designs, strategies and reuse. And I consider most of my habits in this respect to be beneficial. I’m not an anti-pattern guy. On the contrary.
What I aim to do here is to appeal to you to put this in the context of daily problem solving. I don’t write long comments to start a polarized for-against kind of debate. I wish to discuss the nuances. In what type of situation would you choose recursion over iteration? Because your post doesn’t make the case for recursion in such a way that I can see a practical reward that would really shadow its flaws.
I do appreciate your efforts to inspire to look elsewhere, if not only to find that you are already doing it right.
Hallo Øyvind,
You’re right; especially about the context of daily problem-solving. You probably remember a while back the post we had on No Time for OOP. As far as making the case for recursion, my point is only to consider it for simplifying a problem. So, in that sense, it is a problem solver that can be used either in its own right or for clearing up a problem that can later be optimized for speed.
Like preparing food and making love; sometimes slower is better!
Oppriktig,
Bill
Recursion can be Saviour at times – actually i do use recursion whenever i deal with data structure related to linked list or xml. The code remains neat and clean to understand too.
I used recursion for generating an array representation of a xml where I just coded a function for the conversion of a single node to an equivalent array and used recursion for the subsequent node and child nodes and even traversing through the attributes.
But I prefer loops if i am able to make out the boundaries/limits that I am going to dealing with !
Recursion vs. Iteration – Heads vs. Tails !
Hi Sharat,
Thanks for that. It sounds very practical and you have the best of both worlds.
Kindest regards,
Bill
I would like to share a good link regarding Recursion !
http://pages.cs.wisc.edu/~vernon/cs367/notes/6.RECURSION.html
The article provides a very neat and clear vision of how the recursion takes place and how the stack is maintained !
Thanks n Regards
sharat achary
Sharat,
Thanks for that link. I had used the same article a good deal for the basis of the post, and it is an excellent summary and explanation of recursion. For some reason I was able to easily find several articles that compared recursion with iteration online; however, this was one of the best.
Kindest regards,
Bill
I agree with Sharat, it’s simply not an either/or thing. Recursion is great for many tasks, but cannot be regarded as a good practice for many other things as simple as iterating through a linked list.
My rule of thumb is to use iteration whenever I can easily maintain the state for a job in the scope of one function. I’d do this not only because of the performance gain (the callback penalty in FP10 debug is around 5-6 milliseconds for 10000 empty function calls on my machine [haven't checked the release player, should be less], think of situations when you cannot exceed 10-16 milliseconds of math for each frame – a target of 60-80 fps for instance), but with recursion you run a couple of additional risks.
On the one hand in the avm2 you can hit stack overflow around the 8000th recursion (as far as I know).
On the other – memory: when you go deep, recursion can be rather mean to the available resources if you exaggerate with the amount of state on each level of depth.
All of those come into play on large trees only, but you can run into trouble when iterating a list too – if you recur on each next node, you’re essentially building up a huge stack. 10000 nodes and you get an exception.
Cheers!
Hi Histro,
I didn’t mention the large trees, and I’m glad you brought them up. Of course, you, Sharat and Øyvind all make sound points when it comes to using recursion or iteration, and you comments are most welcomed.
Next up, I’m working on lazy initialization and the Factory Method and where to best instantiate objects. I hope you and the others who have made these contributions have some insights into memory management and using lazy initialization with ActionScript 3.0.
Kindest regards,
Bill
Really looking forward to reading about lazy initialization!
Much great insight in this comment thread. And that link from Sharat was really interesting!
Now, while further underlining the point that I too agree that this in no way should be a for-against debate, I do have one perspective I wish to offer.
I read a lot about programming. What strikes me, especially when reading litterature that doesn’t deal specifically with AS, is that other languages are often more formal. I mean that not in the syntactical sense, but rather what kind of structural overhead that usually comes with the package. The paradox in it for me is that I love it – the more formality, the better. But there is one crucial difference between AS and the rest: It usually runs in a the browser layer where it has to deal with the overhead already imposed by a single thread plugin environment, which is why I tend to work as if every MS counts. Of course heavy enterframe scripts are different to a method that only runs at movie launch, but my main goal is to have good habits. In that respect, I treat them as being equally important.
Programming philosophy like patterns an algorithms is usually conceived within the context of mature desktop environments, and then applied by programmers with a degree (I’m generalizing here of course). I think that when applying the same principles to Flash, one has to mindful to the fact that they take for granted bigger resources than what Flash Player usually has at its disposal. Not that resource scarceness isn’t an issue in the desktop environment, or that all patterns and algorithms are bad for performance. But it seems in the case of recursion, based on your own post, subsequent comments and the link from Sharat about the dangers and pitfalls of using recursion, I’m thinking maybe it just doesn’t belong…?
Just saying..:)
Hi Øyvind,
You must have read that article differently than I did. I would be very cautious about shutting the door on recursion in Flash/Flex. I used to program in FORTH, and that was using the stack all the time. As far as memory management is concerned, I believe it’s a lot easier to clear the stack than other parts of memory. In fact, I’d like to add more operations that dealt with the stack directly! That might be a future topic!
Med warmest forhold,
Bill
I am surprised that what it seems to me as the main advantage of Recursive over Iteration has not been mentioned yet… Void Safety, to avoid those NIL issues or null, undefined, void, depending the language you are on.
I highly recommend the following two documents, the first is more thoretical and the second more practical.
1. Repairing the one-billion-dollar mistake
http://bertrandmeyer.com/tag/void-safety/
2. Is your code full of if statements? Switch statements? Do you have the same switch statement in various places?
http://misko.hevery.com/2008/12/08/clean-code-talks-inheritance-polymorphism-testing/
Enjoy them.
Miguel.
Hi Miguel,
Thanks you for that! I very much prefer recursion over iteration, and the comments by Bertrand Meyer and Miško Hevery are good arguments for recursion.
Kindest regards,
Bill
What about while loop vs. recursion? They are very similar.
PS. Great book. One of favorites.
Hi Mitch,
Thanks. I’m not sure how the while loop and recursion are similar any more than the other kinds of loops. We’d love to hear an elaboration on your point. There’s a good chance I’m missing something.
Thanks,
Bill