5 ms·
> , but my CS professors made it clear that iteration is basically just a special case of recursion. That seems a bit disingenuous, since iteration and general
by Dewie 12y ago
> , but my CS professors made it clear that iteration is basically just a special case of recursion.
That seems a bit disingenuous, since iteration and general recursion are fundamentally equivalent. So you could say that "recursion is just a special case of iteration".
Unless we're talking about specific iterations like iterating over a list, I guess.
- danking00 12y agoI feel that it is a bit disingenuous to claim they are equivalent if the solution to maintaining a call stack is to explicitly maintain a stack structure. Iterating over lists, or integers in a range is pretty straightforward. Iterating over a tree? What does that even mean? I suppose we could take "iterate" to mean a catamorphism. Under that interpretation, structural recursion and "iteration" seem pretty equivalent. Just feels like quite an extension of what "iteration" usually refers to in a language like C.
- Dewie 12y ago> I feel that it is a bit disingenuous to claim they are equivalent if the solution to maintaining a call stack is to explicitly maintain a stack structure. You're funny. Equivalent in a computational sense.
- danking00 12y agoBut by that standard ruby is python is C is assembler. Turing-completeness is a not very interesting standard.
- agumonkey 12y agoGood point. I always felt that iteration was 1-dimensional, when recursion is more fractal / N-dimensional. ps: Also, a lot of programming is often conflated into 1-D. sed, grep, awk are mostly init ; iterate{ [PRED] FN }; exit
- rdc12 12y agoBut with TCO it is no longer needed to maintain a stack structure, so it would probably be a better stated as a tail-call recursive function is equivalent to iteration (assuming TCO)