This question already has an answer here:

Is there any problem that can be only solved with recursion, and not with iteration? (haven't been able to find anything online).

If there isn't any, is there a reason why?

Thanks in advance!


marked as duplicate by D.W. May 18 at 18:57

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


The Böhm–Jacopini theorem states that everything can be implemented using just IFs and WHILEs. Indeed, your CPU essentially implements an infinite WHILE loop with conditional execution.

Recursion can be simulated iteratively using a stack; this is how recursion is implemented under the hood. Conversely, the same construction as in the theorem shows that everything can be implemented using only tail recursion (which is essentially a WHILE loop). So iteration and recursion are equivalent.

  • $\begingroup$ Many IFs and a single WHILE. $\endgroup$ – gnasher729 May 16 at 21:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.