CODEWITHSUNDEEP
algorithmrecursioniteration
K''
K''

Reputation: 5238

Recursion Vs Iteration

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)

Upvotes: 5

Views: 2868

Answers (3)

Óscar López
Óscar López

Reputation: 236150

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.

Upvotes: 7

Anthony
Anthony

Reputation: 496

A recursion should be used when a loop is not needed, but the method must repeat itself in a certain case. For example, zipping a folder. If there is a subfolder, it should call itself (recursive). Recursion could substitute iterations if you wanted to, but it's not recommended. Most people just use iterations and only use recursions when they are needed.

Upvotes: 0

Oleksi
Oleksi

Reputation: 13097

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.

Upvotes: 3

Related Questions