JacksonDunstan.com

Recursion is a commonly-used feature of many programming languages, including AS3. It’s useful for everything from trivial examples like computing the Fibonacci sequence all the way up to advanced sorting techniques like Quicksort and tree algorithms. This article is a first in a series all about recursion. Today we’ll see what kinds of limits the Flash Player puts on us as recursion-using AS3 developers.

For the newcomer, recursion is simply when a function calls itself either directly or indirectly:

// Direct recursion
function direct(): void
{
	direct();
}
 
// Indirect recursion
function indirect(): void
{
	other();
}
function other(): void
{
	indirect();
}

This presents a problem, which arises even in these examples: the more recursive calls we make the more likely we are to cause a stack overflow Error to be thrown. Just how many calls can we make? Adobe’s docs don’t say much, but there is a default-script-limits option in MXMLC that theoretically lets us control the maximum stack size. Unfortunately, like with controlling the maximum script running time, we can’t increase the value.

So we’re left to do an empirical test. Below I test a “simple” function that takes up just a little bit of stack space and a “complex” function that takes up much more stack space. I intentionally trigger an infinite recursion, which will throw the stack overflow Error (#1023) and cause the rest of the frame’s ActionScript to be skipped. That’s OK in release versions of Flash Player because there is no code after the recursion, so there’s nothing to skip. I then simply read __recurseLimit on the next frame and see how far we got. (tip: this app will be quite annoying with a debug version of Flash Player since you’ll get crash dialogs)

package
{
	import flash.display.*;
	import flash.events.*;
	import flash.utils.*;
	import flash.text.*;
 
	public class RecursionLimits extends Sprite
	{
		private var __logger:TextField = new TextField();
		private function log(msg:*): void { __logger.appendText(msg + "\n"); }
 
		private var __recurseLimit:int;
 
		public function RecursionLimits()
		{
			__logger.autoSize = TextFieldAutoSize.LEFT;
			addChild(__logger);
 
			addEventListener(Event.ENTER_FRAME, testSimple);
		}
 
		private function testSimple(ev:Event): void
		{
			removeEventListener(Event.ENTER_FRAME, testSimple);
 
			addEventListener(Event.ENTER_FRAME, testComplex);
			recurseSimple();
		}
 
		private function testComplex(ev:Event): void
		{
			removeEventListener(Event.ENTER_FRAME, testComplex);
			log("Simple: " + __recurseLimit);
			__recurseLimit = 0;
 
			addEventListener(Event.ENTER_FRAME, done);
			recurseComplex();
		}
 
		private function done(ev:Event): void
		{
			removeEventListener(Event.ENTER_FRAME, done);
			log("Complex: " + __recurseLimit);
		}
 
		private function recurseSimple(): void
		{
			__recurseLimit++;
			recurseSimple();
		}
 
		private function recurseComplex(): void
		{
			var a:int = Math.random();
			var b:int = Math.random();
			var c:int = Math.random();
			var d:int = Math.random();
			var e:int = Math.random();
			var f:int = Math.random();
			var g:int = Math.random();
			var h:int = Math.random();
			var i:int = Math.random();
			var j:int = Math.random();
 
			__recurseLimit++;
			recurseComplex();
		}
	}
}

Compiled with MXMLC 4.1 and running on the release version of Flash Player plugin 10.1.102.64 for Mac OS X, I get the following:

There are a couple of things to keep in mind here:

• The function call stack starts off with the ENTER_FRAME callback, so it is partly used by the test
• Complex functions clearly take more room on the stack
• “Real world” functions will be even more complex. Expect fewer recursive calls before overflow.

Is this enough stack space for most applications? Definitely. However, you should keep in mind that you only have “a few thousand” functions worth of stack space. If you’re using recursion on a 1000 node (deep) tree or graph, for example, you may very well run into the limits. In that case, you can try simplifying the recursive function or switching to an iterative approach. In any case, it’s good to know your limits.