1
$\begingroup$

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 ?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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$ Commented Oct 23, 2017 at 14:01
  • $\begingroup$ Recursive functions are implemented on actual hardware using a stack. You can't escape this. $\endgroup$ Commented Oct 23, 2017 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$ Commented Oct 23, 2017 at 14:06

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.