END OF AN ERA, FRACTALFORUMS.COM IS CONTINUED ON FRACTALFORUMS.ORG

Hi!
I'm a little confused again..   
What is the difference between "iteration" and "recursion"?

Or is it the same thing?

I've always viewed iteration slightly more active, as part of a process (often with a goal). While I would use recursion to describe things "that just happen". I'd also like to add the word "repetition", which in some cases can be used in the same way as recursion. But you wouldn't use repetition instead of iteration very much. Iteration keeps the process the same, not necessarily the result of each iteration. Repetition and recursion have a wider meaning, it does not really matter if the result is the same every time after each step (or not).

In everyday computer science jargon "iteration" is a more specific subset of "recursion", namely "end recursion". Both imply a repetition of part of a program.

Typically, a recursive function ("function" here in the sense of a subroutine that takes parameters and returns a result) calls itself as part of the sequence of its instructions. There must be cases where it doesn't call itself (otherwise the process could never end), and there may be several "recursive calls" anywhere in the function body.

An "end recursive" function calls itself at most once, and that call is the final instruction in its body. This means the final instruction could as well be replaced by an unconditional jump to the start of the function. That's exactly what a loop does.


There is a more abstract use of the term "recursive" in logic, and in complexity theory. The logicians found out that any arbitrary algorithm, no matter how complicated, can be formulated such that all program code is enclosed within a single outer loop. Initially they even thought that for any arbitrary algorithm, the number of iterations could be bounded ahead of time. So they named that class of algorithms "recursive", and had other names for simpler subsets of algorithms.

Only later it turned out that there are algorithms where no upper bound on outer iterations can be established ahead of time. So nowadays we call the original class of algorithms "primitive recursive", and the more general one (with a necessary runtime check for loop termination) "mu recursive" (I mean the greek letter mu).


So, to make the confusion complete: usually "recursion" is a superset of "iteration". But in logic, all kinds of repetition can be enclosed in a single iterative loop, and the logicians call that loop a recursion.