6

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.

J Freebird
  • 3,664
  • 7
  • 46
  • 81
  • 5
    Recursion is inefficient not because of the implicit stack but because of the [context switching](https://en.wikipedia.org/wiki/Context_switch) overhead. It causes a stack overflow because the amount of stack space allocated to each process is limited and far lesser than the amount of heap space allocated to it. Processes generally need a lot more heap space than stack space. Hence, it's better to use avoid using the stack as much as possible. Recursion can be as fast as iteration if the compiler performs [tail call optimization](http://stackoverflow.com/q/310974/783743). – Aadit M Shah Jan 30 '16 at 03:51
  • Stack overflows occur when the amount of stack memory allocated to a process (at the point of process creation) is exhausted. Every time a call stack is expanded (typically by a method call or in special cases a recursive call), its consumed. – Arunav Sanyal Jan 30 '16 at 03:55
  • 1
    It is not necessarily inefficient, it depends on which language you use. See this question http://stackoverflow.com/questions/2651112/is-recursion-ever-faster-than-looping – dontloo Jan 30 '16 at 03:59
  • @AaditMShah There's no context switching involved in recursion though (unless that's what you call register saving/restoration, stack frame setups and IP jumps that, but then your terminology's unusual and at odds with the link you posted). In either case, it's not a day and night difference. I tested a preorder traversal of a 7node in-cache binary tree: 3.6ns per node with recursion, 2.3ns per node with an explicit stack. – Petr Skocik Jan 04 '19 at 20:17

2 Answers2

11

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.

Community
  • 1
  • 1
Aadit M Shah
  • 72,912
  • 30
  • 168
  • 299
0

There are so-called primitive recursive functions which can be rewritten with a loop. Then there is a class of functions called recursive, which must be defined recursively. A final class is the recursively enumerable functions.

The famous Ackermann function is recursive but not primitive recursive.

There's an excellent video on the subject on the Computerphile youtube channel: The Most Difficult Program to Compute?

Recursion can certainly be efficient. Consider that the glibc implementation of merge sort (msort.c) is recursive.

Note that there is a common compiler optimization for tail recursion which compiles the recursive function into a loop.

dan4thewin
  • 1,134
  • 7
  • 10
  • 1
    Who says that you can't implement the Ackermann function using loops? Here's an implementation of the Ackermann function using a loop in JavaScript: https://jsfiddle.net/mww92ryk/ – Aadit M Shah Jan 30 '16 at 16:17
  • 1
    @AaditMShah `var stack` === recursion. You'd be suprised of the similarities between the language using it's stack and you doing it with a custom one. – Sylwester Jan 30 '16 at 19:43
  • @Sylwester Using a stack does not imply recursion. Recursion implies recursion. Recursion is based on the lambda calculus and the operational semantics of the lambda calculus has no notion of a call stack. The fact that processes in computer systems have a call stack is irrelevant. Recursion is certainly not tied to the stack data structure. The perfect example of this is tail recursive functions. These functions are recursive but they don't need a call stack. Recursion is a way of writing programs and the way I wrote the Ackermann function certainly isn't recursive even though I used a stack. – Aadit M Shah Jan 30 '16 at 20:08
  • @AaditMShah Tail recursive (simple recursion) are iterative processes. Thus they always reduce workload. Simple recursion can be as simple as `function () { return 1;}`. Some languages has only recursion and no other loop forms. I mean recursive processes. Thus reducing lambda calculus is a good example where that would be needed. It really doesn't matter if it's system stack, nested closures, increasing array. You'll see the waiting tasks needed to be performed before result has a tendency to increase and that's perhaps the clue that it's arecursive process and your ackerman function does. – Sylwester Jan 30 '16 at 21:19
  • 1
    @Sylwester I think you're confused between [recursive problems](https://en.wikipedia.org/wiki/Recursive_language) and [recursion](https://en.wikipedia.org/wiki/Recursion_(computer_science)). I agree that the Ackermann function is a recursive function ("recursive" meaning "decidable"). However, the algorithm for the Ackermann function may written either using recursion or iteration. Recursion (based on the lambda calculus) is equivalent in power to iteration (based on the Turing machine). My algorithm doesn't use recursion although the problem is recursive. Question title is Recursion vs Stack. – Aadit M Shah Jan 30 '16 at 21:43
  • @Sylwester The problem that I have with dancancode's answer is that he writes "there is a class of functions called recursive, which must be defined recursively." That's not true. You can define recursive functions iteratively. There is a Turing machine for every recursively-enumerable (i.e. semi-decidable) function and Turing machines are not recursive. They are iterative. Thus, recursion and iteration are equivalent in power. Again, if a problem is recursive or recursively-enumerable then that doesn't mean that it can't have an iterative algorithm. – Aadit M Shah Jan 30 '16 at 21:55
  • @Sylwester Also, try to understand the OP's question. The OP thinks that recursion and iteration are equivalent (which is true). Turing machines are equivalent in power to the lambda calculus. Then the OP asks that if they are equivalent then why is recursion considered inefficient and why does it cause stack overflow errors whilst iteration doesn't suffer from those problems. I think that's a perfectly good question to ask. I don't like dancancode's answer because he mostly talks about classes of problems (which doesn't answer the question directly). – Aadit M Shah Jan 30 '16 at 22:03
  • @Sylwester Finally, tail recursion does not imply that the problem is primitive recursive. You can write the Ackermann function in tail recursive form. Does that make it primitive recursive? No. – Aadit M Shah Jan 30 '16 at 22:07
  • @AaditMShah I have written a Lisp interpreter in Brainf**k. BF is basically a turing machine. You can run recursive functions on the Lisp but how it does it is by growing data structures and a stepping mechanism. All CPUs does it like that so my interpreter does nothing special. I think you have a theoretical view on this and I have a practical one. – Sylwester Jan 30 '16 at 22:40
  • @Sylwester Brainfuck is [Turing complete](https://en.wikipedia.org/wiki/Turing_completeness) but it is not a Turing machine. Also, what's your point? I already know how higher-order functions are interpreted. I've written several interpreters and compilers myself (not in Brainfuck though, that's a terrible esoteric language). – Aadit M Shah Jan 30 '16 at 23:38