Recursion ->
Iteration?
lIs McCarthyÕs transformation
invertible?
lIn some cases, it is possible
to go from recursion to iteration, if the program is tail-recursive.
lIn general, it is not
possible to transform an arbitrary recursive program to iteration, except in a fairly contrived way:
lWe can always implement
recursion using imperative programming and a stack
lIn some sense, this suggests
that recursive programming is strictly more expressively-powerful than iterative programming.