Recursive functions are so 2009. All the cool kids are now scrambling to convert those legacy recursive functions into stack based iteration. Why would you ever need this, you ask? Maybe you’ve heard of my friend “StackOverflowError”, he likes to hang out on the JVM. Or maybe you’re a browser kinda guy and you’ve seen your alert messages say “Stack Overflow”. Or worst case (like me), you’re supporting IE6 and you finally figured out that the “Browser shows a blank screen” defect you can’t reproduce is IE’s way of overflowing (oh yes it really is). Well, stack based iteration is a way to leave your nice recursive function the way it is, yet still avoid the overflow errors. You just have to keep track of the function stack frames yourself by adding a little boilerplate around your method (and even that can be cleaned up fairly easily).
So here is the tale of taking the road now commonly traveled. Learning to program imperatively, writing some beautiful recursive functions, and then ripping it out again because of platform limitations. There and Back Again – A Developer’s Tale of Recursion. The code below is Groovy, but could easily be most any popular language.
Let’s start at the beginning, with a simple function that reverses a string:
assert reverse('forward') == 'drawrof'
And the way most of us learned to write the function in the first place, using iteration and an imperative style:
String reverse(String source) {
def dest = new StringBuffer()
((source.length() - 1)..0).each { i ->
dest << source[i]
}
dest.toString()
}
If it weren’t for the curious popularity of printing out greetings to the console, this might very well be the canonical intro example in most text book. The code keeps a counter starting at the maximum offset of the string and steps backwards by one appending the offest byte of the string back into the StringBuffer. The dest variable is mutated every step of the way and hopefully ends up with the correct value.
Enter recursion. It’s new. It’s different. It’s so much simpler. Can I complete new tasks that I couldn’t before? No, but as Steve Yegge said, “There is in fact one thing you can do using recursion that you can’t do using iteration, namely: You can use it to weed out stupid fugging interview candidates.” Check out the new coolness:
String reverse(String source) {
if (source.length() < 2) return source
String lastChar = source[-1]
String allButLastChar = source[0..-2]
lastChar + reverse(allButLastChar)
}
It’s declarative. The reverse of a zero or one length string is itself. Otherwise it’s the last char plus the reverse() of the rest of the string. It’s immutable. There are no mutations anywhere in this code. It’s independent of types (even though I did specify the input and output types). And it’s beautiful in a way.
And it shouldn’t be used on the JVM and in any browser Javascript that I know of. Even for recursions of one or two, some versions of IE actually detect code that looks like this and preemptively throw an exception even when there is no real Stack Overflow error.
I’ve now had several occasions to have to revert recursive functions back to iteration (both my own code and that of others). You don’t have to go all the way back to step one. You can keep your algorithm and emulate stack frames yourself. It’s a basic recipe:
1. Create a Stack datatype to store method parameters (LinkedList works nicely)
2. Add the original method parameters to the stack
3. Create storage for your output (here a StringBuffer)
4. While the stack still has elements… pop the head off your stack and run your basic algorithm. Where recursion was needed, do not call yourself, instead just push the new parameters back onto the head of the stack so the next iteration will execute it. Your stack will grow and shrink as your algorithm runs, just like your call stack would have.
String reverse(String source) {
def stack = [] as LinkedList
stack.push source
def result = new StringBuffer()
while (!stack.isEmpty()) {
source = stack.pop()
if (source.length() < 2) {
result << source
} else {
result << source[-1]
stack.push source[0..-2]
}
}
result.toString()
}
Is this better than the original iterative version? Certainly not for this trivial example. The stack management obscures the simplicity and intent of the function. But maybe this approach is better for your complex example, where your algorithm really is expressed more clearly using recursion. And I believe that we could remove this boilerplate in Groovy with a little metaprogramming (a task for a different night).
And what do do when your method has multiple parameters? Just make the stack be a stack holding arrays, and each entry in the array is a parameter value. With Groovy and multiple assignments this is quite simple. Here is a cute little anagram finder that requires two parameters. See how they are pushed and popped in pairs:
List findAnagrams(String prefix, String word) {
def stack = [] as LinkedList
stack.push([prefix, word])
def result = []
while (stack) {
(prefix, word) = stack.pop()
if(word.length() <= 1) {
result.add(prefix + word)
} else {
(0..(word.length()-1)).each { i ->
String cur = word[i]
String before = word.substring(0, i)
String after = word.substring(i + 1)
stack.push([prefix + cur, before + after])
}
}
}
result
}
assert findAnagrams('', 'cat') == ['tac', 'tca', 'atc', 'act', 'cta', 'cat']
So what’s it all come down to? What is the best way to write this code? The first iterative version is plain and boring, the recursive version is sexy but dangerous, and the stack version is too complex for such a simple task.
I submit that the code should be written like this:
String reverse(String source) {
new StringBuffer(source).reverse().toString()
}
Effective Java Tip #47 – Know and use the libraries. Behold the wonders of the JDK.
