Recursion's one of the cornerstones of computer science. The
fundamental thesis of computer science says that recursion and iteration (and the untyped
λ-calculus) have the same power. People introduced to programming through imperative languages often find the idea of recursion hard, though
there are good arguments that that's really a deficiency in our teaching.
So, what exactly
is recursion then? And what, for that matter, is iteration?
Wikipedia defines
recursion as "a method where the solution to a problem depends on solutions to smaller instances of the same problem". I haven't had major problems with this definition until recently, when I was reading the wonderful
Concepts, Techniques and Models of Computer Programming (CTM), which unsurprisingly defines an
iterative computation as "a loop whose stack size is bounded by a constant". The examples that it gives are far more surprising, though. Here's an iterative computation to find the length of a list in
Oz, the language CTM uses:
fun {IterLength I Ys}
case Ys
of nil then I
[] _|Yr then {IterLength I+1 Yr}
end
end
Programs like this wouldn't be called iterative in a language like C at all! They'd instead all be called
tail recursive. Oz
optimizes tail calls so that they don't cause the stack to blow up.
1
Even more surprisingly, and perhaps a bit confusingly, it then goes ahead and calls iterative computations a
special case of recursive computations, rather than something distinct. It then talks about converting recursive computations to iterative ones (using accumulators and the like), which I take to mean converting
non-iterative computations to iterative ones.
Granted that these definitions are from a declarative point of view, where all state is immutable and thus
for or
while loops don't make sense, but does that then mean that recursion and iteration can only be defined with respect to the language you're writing in? I've never been fully convinced by
Guido van Rossum's arguments against tall call optimization in Python, but considering that the feature can determine whether a given program is iterative or not, the arguments start making a lot more sense.
And what about
tail recursion modulo cons then, as found in languages like Haskell and Oz? Optimizing tail recursion modulo cons allows functions that aren't tail-recursive, but where the only thing left to execute after the call is a data constructor like
cons, to avoid blowing up the stack
2. Consider this definition of the
map function:
fun {Map F Xs}
if Xs==nil then nil
else {F Xs.1}|{Map F Xs.2}
end
end
This function is clearly not tail recursive, and if translated directly to a language like Scheme which optimizes tail calls but not tail recursion modulo cons, this function would cause a stack overflow with a large enough list. However, since the only thing left after the recursive call is the cons operation (denoted by
|), in Oz this function is iterative by the CTM definition
3.
So, then, does it make sense to define iteration as any computation in a given language which only takes
O(1) implicit (stack) space when executed, and recursion as any computation in a given language which references itself? This would mean that the two aren't quite the opposites they're often portrayed to be, and that depending on the language, recursion and iteration could either overlap or be distinct.
And does it make sense to make this explicit while teaching kids how to program?
1 Interestingly, Oz doesn't have a separate optimization for tail calls. That tail calls don't cause the stack to blow up follows naturally from the way Oz executes programs, as became clear to me when I wrote
a self-interpreter for Oz for a school assignment.
2 Again, neither Haskell or Oz have a separate optimization for this. It's a natural, straightforward result of Haskell's laziness and Oz's data-flow variables (everything's a
promise in Oz!).
3 Peter Van Roy, one of the authors of CTM and an Oz developer,
explains how this happens in Oz.
