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!


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.

| cite | improve this answer | |
  • $\begingroup$ Many IFs and a single WHILE. $\endgroup$ – gnasher729 May 16 '19 at 21:48

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