4 ms·

I might be misunderstanding, but I don't think every algorithm can be expressed through iteration. I believe the Ackerman function is an example of an algorithm

I might be misunderstanding, but I don't think every algorithm can be expressed through iteration. I believe the Ackerman function is an example of an algorithm that can only be computed through recursion[0]. [0]: https://en.wikipedia.org/wiki/Ackermann_function https://en.wikipedia.org/wiki/Ackermann_function

qsort 6y ago
No offense but you are absolutely misunderstanding. The Ackermann function (or rather, the family of functions with similar behavior globally known as 'ackermann') is an example of a general recursive (i.e. computable) function that is not primitive recursive. The proof that this is the case is a classical result that's part of the usual computer science curriculum, the idea being that the asymptotic growth of Ackermann is greater than the asymptotic growth of any primitive recursive function. However, it's easy to see that you can write any recursive function iteratively; it's sufficient to allocate memory for a stack-like structure, and wrap the function body in a while loop. Recursive calls are pushes onto the stack, and returns are pops from the stack. This is exactly how compilers are able to turn recursive calls into ASM. Notice that there is no guarantee that, in general, the function will ever exit the while loop. This is inherent; it is in fact the recursive variant of the halting problem.
dooglius 6y ago
https://rosettacode.org/wiki/Ackermann_function#Stackless_iterative_solution_with_multiple_precision.2C_fast https://rosettacode.org/wiki/Ackermann_function#Stackless_it...
thethirdone 6y ago
Every recursive algorithm can be expressed without recursion. You do not need recursion to simulate a Turing machine and Turing machines can compute every total recursive function. Generally, it is easy to turn a recursive algorithm into a loop and a stack. Simulating a CPU and running compiled code is one example of running recursive programs while only using a loop. I wrote a version of the Ackermann function in Brainfuck (a language with only while loops), but sadly I don't know where I left the program.
deleted 6y ago
[deleted]

qsort 6y ago

No offense but you are absolutely misunderstanding. The Ackermann function (or rather, the family of functions with similar behavior globally known as 'ackermann') is an example of a general recursive (i.e. computable) function that is not primitive recursive. The proof that this is the case is a classical result that's part of the usual computer science curriculum, the idea being that the asymptotic growth of Ackermann is greater than the asymptotic growth of any primitive recursive function. However, it's easy to see that you can write any recursive function iteratively; it's sufficient to allocate memory for a stack-like structure, and wrap the function body in a while loop. Recursive calls are pushes onto the stack, and returns are pops from the stack. This is exactly how compilers are able to turn recursive calls into ASM. Notice that there is no guarantee that, in general, the function will ever exit the while loop. This is inherent; it is in fact the recursive variant of the halting problem.

dooglius 6y ago

https://rosettacode.org/wiki/Ackermann_function#Stackless_iterative_solution_with_multiple_precision.2C_fast https://rosettacode.org/wiki/Ackermann_function#Stackless_it...

thethirdone 6y ago

Every recursive algorithm can be expressed without recursion. You do not need recursion to simulate a Turing machine and Turing machines can compute every total recursive function. Generally, it is easy to turn a recursive algorithm into a loop and a stack. Simulating a CPU and running compiled code is one example of running recursive programs while only using a loop. I wrote a version of the Ackermann function in Brainfuck (a language with only while loops), but sadly I don't know where I left the program.

deleted 6y ago

[deleted]