## Recursion vs. Iteration

Function calls in Flash are notoriously slow. Recursive algorithms require lots of function calls by definition. So are iterative versions faster? Today’s article explores whether or not it’s worth converting your recursive algorithm into an iterative one.

The performance app in this article uses a recursive and an iterative algorithm to traverse a simple binary tree. Here’s how the `Node`

class looks:

class Node { public var val:int; public var left:Node; public var right:Node; }

Both algorithms simply sum the `val`

field in each `Node`

. Here’s the recursive version:

private function recursion(node:Node): int { var sum:int = node.val; if (node.left) { sum += recursion(node.left); } if (node.right) { sum += recursion(node.right); } return sum; }

The recursive version is very simple and straightforward if you’ve used recursion before. The iterative version is rather more complex:

private function iteration(node:Node): int { var stack:Vector.<Node> = new <Node>[node]; var stackSize:int = 1; var sum:int; do { node = stack[--stackSize]; sum += node.val; if (node.left) { stack[stackSize++] = node.left; } if (node.right) { stack[stackSize++] = node.right; } } while (stackSize > 0); return sum; }

A `Vector`

is used to keep a stack of `Node`

instances that need to be handled. This essentially fakes the function call stack.

Now for the full test app source code:

package { import flash.display.*; import flash.utils.*; import flash.text.*; public class IterationVsRecursion extends Sprite { private var logger:TextField = new TextField(); private function row(...cols): void { logger.appendText(cols.join(",") + "\n"); } public function IterationVsRecursion() { stage.align = StageAlign.TOP_LEFT; stage.scaleMode = StageScaleMode.NO_SCALE; logger.autoSize = TextFieldAutoSize.LEFT; addChild(logger); init(); } private function init(): void { var beforeTime:int; var afterTime:int; var iterationResult:int; var recursionResult:int; beforeTime = getTimer(); var tree:Array = makeTree(20); var root:Node = tree[0]; var sum:int = tree[1]; afterTime = getTimer(); row("Building Time", (afterTime-beforeTime)); row(); row("Mode", "Time"); beforeTime = getTimer(); iterationResult = iteration(root); afterTime = getTimer(); row("Iteration", (afterTime-beforeTime)); beforeTime = getTimer(); recursionResult = recursion(root); afterTime = getTimer(); row("Recursion", (afterTime-beforeTime)); row(); row("Actual Sum", sum); row("Iteration Result", iterationResult); row("Recursion Result", recursionResult); } private function makeTree(depth:int, root:Node=null, curDepth:int=0): Array { if (!root) { root = new Node(); } if (curDepth >= depth) { return [root,0]; } root.val = curDepth; var sum:int = root.val; root.left = new Node(); var tree:Array = makeTree(depth, root.left, curDepth+1); sum += tree[1]; root.right = new Node(); tree = makeTree(depth, root.right, curDepth+1); sum += tree[1]; return [root, sum] } private function iteration(node:Node): int { var stack:Vector.<Node> = new <Node>[node]; var stackSize:int = 1; var sum:int; do { node = stack[--stackSize]; sum += node.val; if (node.left) { stack[stackSize++] = node.left; } if (node.right) { stack[stackSize++] = node.right; } } while (stackSize > 0); return sum; } private function recursion(node:Node): int { var sum:int = node.val; if (node.left) { sum += recursion(node.left); } if (node.right) { sum += recursion(node.right); } return sum; } } } class Node { public var val:int; public var left:Node; public var right:Node; }

I ran this test in the following environment:

- Release version of Flash Player 12.0.0.77
- 2.3 Ghz Intel Core i7-3615QM
- Mac OS X 10.9.1
- Google Chrome 33.0.1750.152
- ASC 2.0.0 build 354071 (
`-debug=false -verbose-stacktraces=false -inline -optimize=true`

)

And here are the results I got:

Mode | Time |
---|---|

Iteration | 44 |

Recursion | 18 |

As you can see from the results, faking recursion with iteration ends up taking about 3x longer than simply using recursion. The algorithm is also longer and arguably less readable and more complex.

However, there is one advantage: if your tree was very deep there would not be the possibility of a stack overflow due to too many recursive function calls. ~~By default, you can only have 256 function calls in your stack with Flash~~, so this limit could definitely be hit by certain trees. In that case, it’d be worth paying the performance penalty to avoid an `Error`

being thrown. Otherwise, stick with recursion.

Spot a bug? Have a question or suggestion? Post a comment!

#1 by

henke37on March 24th, 2014 ·Are you sure about the function call limit? I think it was only for as 2 code.

#2 by

henke37on March 24th, 2014 ·function fun(d:uint):uint {

if(d) {

return d-1;

}

return 0;

}

fun(1000);

No crash here, so it seems that my recollection was correct.

#3 by Kabuto on March 24th, 2014 ·

That doesn’t seem to be a recursive function. “fun(1000)” would just return 999 on its first call to fun.

If you change “return d-1;” to “return fun(d-1);”, which I think is what you meant, you’ll probably get a stack overflow error if you call fun with an argument of anything over 5285. Jackson actually already wrote an article about how the limits to recursion in AS3 work (http://jacksondunstan.com/articles/949), but you’re definitely right that 256 was only the limit in AS2.

#4 by jackson on March 24th, 2014 ·

Thank you all for pointing out this mistake. I’ve updated the article to remove the reference to the 256 function stack limit and link to the article going into more detail on the actual stack limits.

#5 by

dijiydon March 24th, 2014 ·The limits have been covered by this very blog before:

http://jacksondunstan.com/articles/949

It’s not a fixed number

#6 by ChessMax on March 24th, 2014 ·

You have a very strange results, I must say. And thank you for the article!

My results:

Mode,Time

Iteration,46

Recursion,84

#7 by jackson on March 24th, 2014 ·

Interesting. Could you post your year environment?

#8 by ChessMax on March 25th, 2014 ·

Intel core i5-3330, 3,2GHz, 8 Gb RAM, windows 7, x64, Chrome 33 (and other browsers too), FP 12

#9 by

Merlinon March 27th, 2014 ·Intel Core i5-2400, 3.1 GHz, 12 Gb RAM, Windows 7 x64.

—

Google Chrome, FP 13,0,0,80 from link http://files.jacksondunstan.com/articles/2546/IterationVsRecursion.swf

Building Time,1282

Mode,Time

Iteration,48

Recursion,88

Actual Sum,18874370

Iteration Result,18874370

Recursion Result,18874370

—

Standalone player 12.0.0.44 compiler AIR 3.0.9

Building Time,1277

Mode,Time

Iteration,46

Recursion,93

Actual Sum,18874370

Iteration Result,18874370

Recursion Result,18874370

—

If use inline:

[Inline]

final private function recursion(node:Node): int

I got the result: Recursion,37

#10 by

Eduardon May 6th, 2014 ·Intel Core i7-2600K 3.5Ghz 16 gb RAM win 7 x64

Google Chrome, FP 13,0,0,206

Iteration,40

Recursion,16

#11 by

PERUMALon November 18th, 2019 ·Pentium(R) dualcore CPU 2.2Ghz,2GB RAM,32 bit OS windows-7

Building Time,1532

Mode,Time

Iteration,94

Recursion,31

Actual Sum,18874370

Iteration Result,18874370

Recursion Result,18874370