Difference between the terms Recursion and Iteration?

[Chillheimer]

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

Or is it the same thing?

[kram1032]

To my knowledge, all iterations are a type of recursion, but not all recursions are iterations.

Iteration is, that you have a function and you do

In case of recursion, you can do more general stuff, like defining a function on one point based on other points of that same function.

A typical example would be fibonacci numbers:

Code:

f(0)=0
f(1)=1
f(n+2)=f(n)+f(n+1)

This is not an iteration, but it is a recursion.

Meanwhile

Code:

f(z)=z^2+c
f(f(f(...)))

is an iteration (and a recursion)

The same code could be written recursively:

Code:

z(0,c)=c
z(n,c)=z(n-1,c)^2+c

[youhn]

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).

[cKleinhuis]

so, let me intercept here

iteration is the concept of a repeated application
recursion is the concept of defining a function through itself

they share similarities, from the standpoint of a computer scientist iterative solutions are far more efficient

in escape time fractals we use the "iteration" concept, by repeating the same operation over and over

the recursive concept is used in fractals widely, the sierpinski triangle is such an example. it starts out with a triangle and repeatedly calls itself on the generated triangles

a tree is another recursive example

[hobold]

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.

[jehovajah]

These kinds of confusions occur particularly in languages that do not have self reflexive active and passive verb denotations.

Most Romance languages do as well as German, but English not so much. Greek actually abounds in these verb structures and they are employed very distinctively in certain formal developmrnts( dialectic/ logic) and instinctively in shorthand and definitional practices.

Recursion is perhaps a latinisation of the Greek derived Iteration, both are based on the Olympian race model, where the athlete is expected to run the course again snd again to achieve the goal or result.

What Mathematicians and logicians use the concept for has been clearly expressed above, but my opinion is to take these definitions with a pinch of salt to digest them, or snuff to blow your sinuses out with them ! Terms will always etymologically morph over time and today iteration is the favoured word over recursion, much to the annoyance of these special interest groups!

Do not allow some professor to make you feel stupid because you said iteration instead of recursion. Just ask them to define what they mean, and see how they too struggle!

Yes we need conventions, and we need agreement, but what we do not need is browbeating and coercion, driving many gifted minds away from engaging creatively with the spaciometric nature of all around us in an iterative way.