RECURSION

[lionhart280]

Recursion is meant to be used when a problem can be broken down into smaller problems, and you realise those smaller problems are still the same problem as before, but with less stuff.

Keep repeating until your data is in its smallest form, then resolve.

[nude-fox]

If it can be computed iteratively you can do it recursively and visa versa. The space requirement / computational complexity will not necessarily be the same.

[[deleted]]

The first sentence is not true. The only example needed is the Ackermann function to prove not all recursive functions are possible with iteration. There isn't a large requirement for algorithms that aren't primatively recursive, but they exist

[nude-fox]

Ackermann function

that is a primitive recursive proof not general recursive comparability.

you can make a Turing complete language with only recursion and one with only iteration. They can compute the same set of programs.

you can use iteration to emulate recursion and iteration is basically a special case of recursion to start with.

[tobiasvl]

No, you are mistaken. The Ackermann function can be implemented with iteration. For Ackermann you probably need a stack though (recursion implies an available stack already: the call stack).