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;
}

Run the test

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

Iteration vs. Recursion Performance Graph

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!