Continuing from last week’s article on recursion limits, today we’ll talk about recursion speed. Is there a penalty for making recursive calls? Does it increase as the recursion gets deeper and deeper? Read on to find out.

Converting a recursive algorithm to an iterative approach often speeds it up as function calls are quite slow in AS3. That’s not our concern today. Today we’ll look at making the same number of function calls iteratively as we would do recursively. For example, we’ll compare the speed of function F calling itself 100 times to the speed of calling function F 100 times from a loop in another function. Here’s a snippet from the performance test showing how these “loops” are accomplished:

// recursive "loop"
function recurseTo(to:int, cur:int): void
{
	if (cur < to)
	{
		recurseTo(to, cur+1);
	}
}
recurseTo(100);
 
// iterative loop
function foo(): void {}
for (var j:int = 0; j < 100; ++j)
{
	foo();
}

Each “loop” will result in 100 function calls.

The following test works like this:

  1. The recursion limits technique is used to find how many recursions deep recurseTo can go.
  2. The two “loops” from above are used with progressively more function calls.
  3. To avoid an Error being thrown, the test stops when the recursion limit is reached

Here is the performance test:

package
{
	import flash.display.*;
	import flash.events.*;
	import flash.utils.*;
	import flash.text.*;
 
	public class RecursionSpeed extends Sprite
	{
		private var __logger:TextField = new TextField();
		private function log(msg:*): void { __logger.appendText(msg + "\n"); }
		private function logResult(calls:int, iterative:int, recursive:int): void
		{
			log(padInt(calls, 5) + " | " + padInt(iterative, 9) + " | " + padInt(recursive, 9));
		}
		private function padInt(val:int, chars:int): String
		{
			var str:String = val.toString();
			for (var pad:int = chars - str.length; pad > 0; --pad)
			{
				str += " ";
			}
			return str;
		}
 
		private var __recurseLimit:int;
		private var __curCallCount:int;
 
		public function RecursionSpeed()
		{
			__logger.autoSize = TextFieldAutoSize.LEFT;
			__logger.defaultTextFormat = new TextFormat("_typewriter", 10);
			addChild(__logger);
			log("Calls | Iterative | Recursive");
 
			stage.frameRate = 1000;
			addEventListener(Event.ENTER_FRAME, testCallLimit);
		}
 
		private function testCallLimit(ev:Event): void
		{
			try
			{
				recurseTo(__curCallCount, 0);
				__curCallCount+=10;
			}
			catch(err:Error)
			{
				__recurseLimit = __curCallCount;
				__curCallCount = 0;
 
				removeEventListener(Event.ENTER_FRAME, testCallLimit);
				addEventListener(Event.ENTER_FRAME, testCallSpeed);
			}		
		}
 
		private function testCallSpeed(ev:Event): void
		{
			const REPS:int = 1000;
			var i:int;
			var beforeTime:int;
			var afterTime:int;
			const curCallCount:int = __curCallCount;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				recurseTo(curCallCount, 0);
			}
			afterTime = getTimer();
			var recursiveTime:int = afterTime - beforeTime;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (var j:int = 0; j < curCallCount; ++j)
				{
					foo();
				}
			}
			afterTime = getTimer();
			logResult(curCallCount, (afterTime-beforeTime), recursiveTime);
 
			__curCallCount += 200;
			if (__curCallCount > __recurseLimit)
			{
				removeEventListener(Event.ENTER_FRAME, testCallSpeed);
				stage.frameRate = 12;
				log("Recursion limit: " + __recurseLimit);
			}
		}
 
		private function recurseTo(to:int, cur:int): void
		{
			if (cur < to)
			{
				recurseTo(to, cur+1);
			}
		}
 
		private function foo(): void {}
	}
}

With Flash Player 10.1.102.64 (release plugin, release build) on a 2.4 Ghz Intel Core i5 running Mac OS X 10.6, I get the following results:

Calls Iterative Recursive
0 0 0
200 2 3
400 3 6
600 3 5
800 4 7
1000 5 10
1200 6 13
1400 7 15
1600 8 16
1800 9 19
2000 10 21
2200 11 23
2400 12 25
2600 13 27
2800 14 30
3000 16 32
3200 17 35
3400 17 37
3600 18 39
3800 19 42
4000 21 44
4200 22 45
4400 23 49
4600 24 51
4800 25 53
5000 27 56
5200 27 59
5400 28 62
5600 28 65
5800 30 67
6000 31 70

It can be hard to tell the trend from such a wall of numbers, so here’s a chart showing performance as function calls increase:

Results Graph

As you can see, the iterative approach beats the recursive approach even with small numbers of function calls. This shows recursion to be expensive not just because it involves a lot of function calls, but for some other reason as well. You would therefore be wise to avoid recursion in performance-critical areas even if your alternate approach involves just as many function calls. This is especially true for very deep recursion, as the CPU hit becomes quite great after just a thousand function calls or so, even with a function that’s empty except for the “loop” function call. On a lower-end machine or a mobile device, this could easily cause frame rate to drop.