Converting Recursion into Into Iteration [duplicate]

Question

This question already has an answer here:

While reading Code Complete second edition, I came across this line:

You can do anything with stacks and iteration that you can do with recursion.

Is this true? or there are functions, that must be implemented recursively, and can't be done otherwise ?

Yuval Filmus · Accepted Answer · 2017-10-23 13:57:29Z

1

Your CPU uses stacks and iteration to run any program, including programs based on recursion.

If you are unsure how this works, I suggest picking up an appropriate textbook.

answered Oct 23 '17 at 13:57

Yuval Filmus

209k15 gold badges203 silver badges370 bronze badges

$\begingroup$ I'm talking at a higher level, for example, can the C language be used to implement any recursive function, in an iterative way? because recursive functions, though sometimes they look simple an elegant, they might eat a lot of memory stack, and might cause a stack overflow. $\endgroup$ – Bite Bytes Oct 23 '17 at 14:01
$\begingroup$ Recursive functions are implemented on actual hardware using a stack. You can't escape this. $\endgroup$ – Yuval Filmus Oct 23 '17 at 14:02
$\begingroup$ Also, actual computers can also run out of heap space. When we say that stacks and iteration can simulate recursion, we consider an idealized computer. $\endgroup$ – Yuval Filmus Oct 23 '17 at 14:06

add a comment |

marked as duplicate by D.W.♦ Oct 23 '17 at 14:03