Francis Cheng: Proper Tail Calls and Recursion

Today I'm going to talk about the proposed Proper Tail Calls (PTC) feature and recursion. I'm going to show you how PTC can significantly reduce stack usage for functions with recursive calls in tail position. If you recall, I mentioned in my previous post that Proper Tail Calls is also called Proper Tail Recursion. This is because PTC has a significant effect on certain types of recursive functions. In case you're unfamiliar with recursion, a recursive function is a function that calls itself. For example, we could use a recursive function to calculate the factorial of a number, which means multiplying a number by every integer between that number and zero, as in 3! = 3 x 2 x 1 = 6.

Here's an ActionScript function that calculates factorials:

function factorial (num:int): Number {
	if (num <= 1) {
		return 1;
	}
	else {
		return num * factorial(num-1);
	}
}

So let's call factorial() with an argument of 3 and walk through the code execution. The parameter num is assigned a value of 3, which means we skip down to the else{} statement because 3 is greater than 1. In the else{} statement, we call factorial() again, but this time with the argument value 2. When the new call happens, the runtime suspends execution of the original call to factorial() and pushes the original call onto the stack because we'll need it later. Next, we walk through the second call to factorial(), but with the value 2. We get similar results, factorial() gets called a third time, but this time with an argument value of 1.

At this point we've not yet returned from any function, so all of these functions are still active and piled onto the stack, with our initial call at the bottom of the stack. With the call to factorial(1), however, we finally enter the if{} statement and simply return the value 1. This means that the call to factorial(1) can be discarded and we emerge back inside the else{} statement in the previous call to the factorial function, factorial(2). This return trip back down the stack is where values are returned and the calculations occur:

factorial(1) returns the value 1 
factorial(2) returns the value 2 * 1
factorial(3) returns the value 3 * 2

Notice that the recursive call to factorial() is not in tail position because the last thing the function does is multiply num by the return value of factorial(num-1). So PTC would not affect the execution of factorial() as it is written above. To get the benefits of PTC, we would need to refactor the code so that the recursive call to factorial() is in tail position. One way to do that would be to use a helper function that handles the recursion:

function factorialEx (num:int):Number {
	return factorialIterator(1, 1, num); 
}

function factorialIterator(counter:int, subTotal:Number, maxCount:int) {
	if (counter == maxCount) {
		return subTotal * counter;
	}
	else {
		return factorialIterator (counter + 1,
					  subTotal * counter,
					  maxCount)
	}
}

PTC will apply to factorialIterator() because the recursive call to factorialIterator() is in tail position. The factorialEx() function takes a very different approach in that it uses a counter to track progress so that it doesn't have to fill up the stack with a large number of suspended function calls. A call to factorialEx() sets in motion a series of tail calls that keeps stack usage constant. Stepping through, a call to factorialEx(3) results in a tail call to factorialIterator(), which results in recursive tail calls until the counter is equal to 3. The subTotal parameter stores the running total throughout this process.

The difference between these two techniques is more pronounced if you consider larger factorials. If you want to calculate 40 factorial, the original factorial() function will result in extensive stack usage that will require memory enough to hold 40 deferred function calls. On the other hand, if PTC is added to the language, the factorialEx() function will grow the stack by no more than one function. Currently, however, ActionScript exhibits the same extensive stack-usage behavior for both factorial() and factorialEx().

You may be thinking that 40 or so functions on the stack are not a big deal, and we can't feed numbers to factorial() much bigger than that before we exceed the capacity of the Number type to hold the answer. I agree that this isn't a great example of the benefit of PTC, but it was useful as a simple way to explain the differences between these recursive functions. There are other examples, such as calculating Fibonacci numbers, that better show the benefits of PTC. You could write a non-tail-recursive Fibonacci function that calls itself for every addition operation. There you would run into ActionScript's recursion limit when feeding in numbers that call for more than a thousand calculations. That would mean a thousand suspended functions stored on the stack, which would contrast sharply with a tail-recursive implementation that would grow the stack by exactly one function.

Here are links to some of the materials I used in my research for this post:

Comments

Thanks for this information. While PTC may not be in Actionscript yet I could definately see the benefits to this in many areas when it does. It also just opens my mind to a new way to programmatically solve a problem.

I look forward to reading more on this topic as you write it.

Posted by: Daryl Ducharme | January 30, 2008 11:43 AM

excellent info..
the next code works too with PTC?

fact (int n){
return factTail(n,1);
}

factTail(int n, int res){
if (n=1 or n=0) return res;
else return factTail (n-1,n*res);
}

Posted by: raymond cidad | February 11, 2008 9:05 AM

Hi Raymond,

Yes, your technique would also work, and is more concise than mine (though it's not ActionScript syntax). Thanks for sharing!

Posted by: Francis Cheng | February 11, 2008 11:26 AM

Francis,
Your factorial() implementation is much, much nicer. leaving around function declarations like factTail(n, res) for others to pick up and become confused by is not a good idea.
If you want your's to appear more concise, write it like this:

function factorial (n:int):Number {
	if (n <= 1)
		return 1;
	return n * factorial(n - 1);
}

Posted by: Matt | April 9, 2008 10:27 AM

woops, silly me for not reading the article.

Posted by: Matt | April 9, 2008 10:34 AM

Francis Cheng

ActionScript, ECMAScript and the Flash Platform

Proper Tail Calls and Recursion

Comments

Post a comment