Unlooping the re-loops
“You can do anything with stacks and iteration that you can do with recursion.” — Steve McConnell, Code Complete
For almost as long as we’ve been talking about recursion, and especially recently because of our recent project, the question has been on my mind: Why recursion, when, like Steve McConnell says, loops (and stacks – and I presume queues) can do the same thing? I mean of course, recursion is fantastic simply because of the self-reference, but a little less philosophically, what’s so great about recursion anyway?
Well, it’s obvious why recursion beats a for loop any day: not only does a for loop require a specific range of items or indices to look at, but you can’t break out of a for loop before the end of that range (nicely – I maintain that break is nearly as bad as goto – cf. https://xkcd.com/292/).
But, you may then ask, what about while loops? They continue on condition of an expression, just like recursive programs do, and even if recursive functions can take multiple arguments, while loops can simply store data outside of the loop – no function calls needed.
But I think the important points here are space and clarity. For programs that need to build a progressively larger dataset (like our assignment’s DFS and BFS PuzzleNode builders), recursion makes each function call – each child – be operated on separately from the rest of its family, and all extraneous data is discarded once that recursive call returns out. A while loop storing data outside of the loop doesn’t have this luxury. And, perhaps even more crucially, a recursive function can simply be easier to understand, especially for programs that have clearly defined modules that function independently, and only their results are assembled. Programmers are humans too, so if it’s easier – why not go for it? After all, like I said from day one: laziness is key!