Recursion vs. Stack

Question

I wonder if recursion is the only solution to a problem, then is iteration with stacks the only other solution? I think they're kind of equivalent: If recursion works, then iteration will work for sure, and vice versa.

Also, I'm not sure why recursion is considered inefficient and often causes stack overflows while iteration with stacks does not. Recursion just uses stacks in an automatic way invisible to the user.

Answer 1

Although dancancode's answer talks about different kinds of problems like primitive recursive problems, recursive problems and recursively enumerable problems, IMHO this question is more about straightforward recursion or iteration.

I wonder if recursion is the only solution to a problem, then is iteration with stacks the only other solution?

No, there are a lot of different models of computation. However, the lambda calculus (the basis of recursion) and Turing machines (the basis of iteration) are the most popular models of computation. Another popular model of computation is μ-recursion.

What is a model of computation?

For a long time mathematicians wanted to study the nature of computation. They wanted to know which problems can be computed (i.e. which problems have a solution) and which problems cannot be computed (i.e. which problems have no solution). They also wanted to know the nature of the computation (e.g. how much time does it take to compute the solution relative to its input size, etc.).

However, there was just one problem: “computation” is a very abstract term. How do you reason about something that's not concrete? That's the reason mathematicians needed a model of computation which they could reason about. A model of computation captures the “essence of computation”. That means that if there's a problem which can be computed then there must be an algorithm for computing it in every model of computation.

I think they're kind of equivalent: If recursion works, then iteration will work for sure, and vice versa.

Yes, that's correct. The Church-Turing thesis essentially states that every model of computation is equivalent in power. Hence, everything that you can do using recursion (i.e. the lambda calculus) can also be done using iteration (i.e. a Turing machine).

In fact, most computers in the world are based on the Turing machine. Hence, every computer uses iteration only. Nevertheless, your computer can still execute recursive programs. This is because a compiler translates your recursive program into iterative machine code.

Also, I'm not sure why recursion is considered inefficient and often causes stack overflows while iteration with stacks does not. Recursion just uses stacks in an automatic way invisible to the user.

This is because of the way operating systems handle processes. Most operating systems impose a maximum limit on the size of a stack. On my Linux OS the maximum stack size is 8192 KB which is not a lot. Use ulimit -s to find your default stack size on a POSIX compliant OS. This is the reason why using too much recursion causes a stack overflow.

On the other hand, the size of the heap can be dynamically increased while the process is executing (as long as free space is available). Hence, you don't have to worry about running out of memory when using iteration (even when using an explicit stack).

Furthermore, recursion is generally slower than iteration because calling a function requires a context switch while in iteration you only need to modify the instruction pointer (i.e. jump, possibly conditional).

However, this doesn't mean that iteration is always better than recursion. Recursive programs are usually smaller and easier to understand than iterative programs. In addition, in certain cases the compiler can eliminate context switches altogether via tail call optimization (TCO). This not only makes recursion as fast as iteration but also ensures that the stack size doesn't increase.

Interestingly, all recursive programs can be made tail recursive by translating the program into continuation-passing style (CPS). Thus, CPS and TCO can eliminate the need of an implicit call stack altogether. Several compilers and interpreters for functional programming languages use this ability in novel ways.