[plt-scheme] guido on tail recursion

2009/4/25 Joe Marshall <jmarshall at alum.mit.edu>:
> Yes.  There are recursive programs that cannot be expressed as iteration.
> In fact, the set of programs that can be expressed with iteration is
> much smaller than the set of programs that can be expressed with
> recursion.  And it appears to be the case that if you can't express a program
> recursively, then you can't compute it at all (through any means!).
>
> So recursion is the most powerful tool we have.

I'm not sure I get what you're saying here, since a theoretical Turing
Machine can be expressed pretty simply as an iteration. Perhaps you
meant an iteration with a fixed set of fixed-size loop variables?

    Henk