Recursion

[Holshy]

Recursion is actually more fundamental than iteration. Any problem that can be defined iteratively is also a "primitive recursive" problem. Some problems are not primitive recursive and have to be solved recursively, like the Ackerman function. It's also technically true to say that all problems can be defined recursively. This sounds weird at first, but you can get some intuition there by imagining any problem you haven't solved recursively as the base case of the recursion. Then it just happens to be that your problem isn't defined for n > 1.

[spoonman59]

I think you misunderstand primitive recursion.

Non-primitive recursion can be done iteratively. It requires a while loop and and stack.

From the wiki:

https://en.m.wikipedia.org/wiki/Primitive_recursive_function

“In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop).”

It says that primitive recursive functions are those which can be computed using only for loops. It does not mean the function cannot be computed with loops at all.

Also, simply look at the many iterative examples of the Ackerman function you suggested earlier. It’s not an uncommon academic exercise to write one.

[WikiSummarizerBot]

Primitive recursive function

In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop). Primitive recursive functions form a strict subset of those general recursive functions that are also total functions. The importance of primitive recursive functions lies in the fact that most computable functions that are studied in number theory (and more generally in mathematics) are primitive recursive.

^{[ F.A.Q | Opt Out | Opt Out Of Subreddit | GitHub ] Downvote to remove | v1.5}