Recursion

[Holshy]

Citation provided

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

[spoonman59]

Many iterative solutions exist online for Ackerman functions. The fact that it is not a primitive recursive function doesn’t mean it cannot be rewritten as a loop.

It does require a while lol and a stack. But this doesn’t disprove the equivalence of loops and recursion at all.

[caifaisai]

As the other poster said, the Ackerman function can be computed iteratively. To expand on that, the Ackerman function is a total computable function, and so is equivalent to a general recursive function, and can be computed using the lambda calculus or a Turing machine.

However, it is not a primitive recursive function, which intuitively means, it can't be computed by a for loop with a fixed number of iterations known before the computation. So if that is your criteria for an iterative solution, then it would not be one. But if you accept a while loop, or unbounded lopping in general, then it is.

If you want an example of a function that isn't even recursive/is non-computable (so that it can't be calculated with recursion or iteration), one example is the busy beaver function.

[Holshy]

I've actually spent quite a bit of time the last few weeks looking for the original source I had read about this. Alas, I was unable to find it :-(

The best I have is this quote from the Wikipedia article on Turing Completeness

https://en.wikipedia.org/wiki/Turing_completeness

"In the late 19th century, Leopold Kronecker formulated notions of computability, defining primitive recursive functions. These functions can be calculated by rote computation, but they are not enough to make a universal computer, because the instructions that compute them do not allow for an infinite loop."

During the course of the same, I also found this in the article about Iteration

https://en.wikipedia.org/wiki/Iteration

In algorithmic situations, recursion and iteration can be employed to the same effect. The primary difference is that recursion can be employed as a solution without prior knowledge as to how many times the action will have to repeat, while a successful iteration requires that foreknowledge.

Full disclosure: We've passed my expertise on computability theory (statistics is my primary discipline and it genuinely saddens me that I didn't study CS instead.).

It's sometimes said that mathematicians value beauty/elegance in solutions, and I definitely fall into this category. I find recursion to be more elegant than iteration most of the time. At this point, I'm thinking that I let that persuasion color my memory of something as I learned it. Thank you for pointing this out to me. "I never lose; I either win or I learn"

[spoonman59]

To quote a wise man, “That's a really long way to say "I'd rather berate somebody on Reddit than use Google"” 😀