Recursion Vs Iteration

Question

I believe that all the problems that have iterative logic can be solved using iterations, but can we solve any problem using recursion? Can recursion always substitute iteration? Please provide a proof to your answer if you can. Also assume that we have an infinite stack or we run the program on a Turing machine. I don't care if this proof is a theoretical proof. (that's why I mentioned the Turing Machine)

Answer 1

Yes, recursion can always substitute iteration, this has been discussed before. Quoting from the linked post:

Because you can build a Turing complete language using strictly iterative structures and a Turning complete language using only recursive structures, then the two are therefore equivalent.

Explaining a bit: we know that any computable problem can be solved by a Turing machine. And it's possible to construct a programming language A without recursion, that is equivalent to a Turing machine. Similarly, it's possible to build a programming language B without iteration, equal in computational power to a Turing machine.

Therefore, if both A and B are Turing-complete we can conclude that for any iterative program there must exist an equivalent recursive program, and vice versa. This is a theoretical result, in the sense that it doesn't give you any hints on how to derive one recursive program from an arbitrary iterative program, or vice versa.

Answer 2

Yes. There is a type of recursion called tail recursion, which is directly translatable to iteration. One can be converted to the other without any problem. Thus, all iterative solutions can be converted into recursive solutions.

In fact, many compilers can detect that you are doing tail recursion, and then convert it into for-loop type code for efficiency.