Why use recursion?

Question

I am wondering, why do people use recursion? In most of my learning experience, I've found it to be much more inefficient that iterative methods, so why do people use it? Is it because you can simply write a shorter method? Is it used in real-world programming outside the classroom setting (or learning purposes)? If it is, please provide a good example if you can, I'm very curious.

Thanks in advance for your help! I really appreciate it!

Relevant reads: http://stackoverflow.com/questions/2185532/why-should-recursion-be-preferred-over-iteration?rq=1 http://stackoverflow.com/questions/2651112/is-recursion-ever-faster-than-looping?rq=1 — reto, Dec 02 '13 at 15:47

score 4 · Answer 1 · answered Dec 02 '13 at 15:47

4

If you have a tree data structure and you want to walk over it in depth-first order, recursion is the only way to do it.

If you want to write a parser for a typical language having context-free rules, like every programming language in existence, a recursive-descent parser is a simple and natural way to do it. There is no iterative way to do it with limited storage.

answered Dec 02 '13 at 15:47

Mike Dunlavey

40,059
14
91
135

8

Recursion isn't the only way - it is just the simplest, most natural way of solving the problem. However, an iterative approach using a stack will also work. – Trenin Dec 02 '13 at 15:49
4

@Trenin: An iterative way using a stack *is* recursion. – Mike Dunlavey Dec 02 '13 at 15:49
1

@MikeDunlavey - If it is using just a regular stack data structure, and not the call stack, then I would not call that recursion. – mbeckish Dec 02 '13 at 15:55
There's a term for algotithms that use an explicit stack, rather than implicitly using the system's call stack. They're called "data-recursive". – cHao Dec 02 '13 at 15:59
@mbeckish: If you write a recursive function in any language, the compiler turns it into a non-recursive instruction stream that makes use of a stack. That's what recursion is. See also [*trampoline-style code*](http://en.wikipedia.org/wiki/Trampoline_(computing)). – Mike Dunlavey Dec 02 '13 at 16:00
3

@MikeDunlavey: True recursion implicitly uses the call stack. Data-recursion explicitly uses its own stack. There's a difference, particularly in languages that don't do real recursion well -- most of them could do data-recursion all day. – cHao Dec 02 '13 at 16:01
@cHao: You're right. We're splitting hairs. There's a subtle difference between a formal stack and an explicit stack as in, say, Fortran 77. The explicit stack has a finite size, while the formal stack does not, at least in the language. Of course, in any real implementation, every stack is finite. – Mike Dunlavey Dec 02 '13 at 16:05
1

You don't even *need* a stack, though. It's the most natural solution, but not the only one. Imagine a doubly-linked list, where each node has an `expanded` flag. Start out with the list just containing the root. As you run through the list, if you see a node that hasn't been expanded yet, and it has any children, insert the children before the current node, set the current node's `expanded` flag, and move the iterator back so that the children will be the next nodes processed. Otherwise, process that node and move the iterator forward. – cHao Dec 02 '13 at 16:28
@cHao Usually common to use singly linked lists for this and it's called a [spaghetti stack](http://en.wikipedia.org/wiki/Spaghetti_stack). It's used in dynamic languages like Scheme, Smalltalk and Rust. – Sylwester Dec 02 '13 at 16:38
@cHao: There are infinitely many ways to realize stacks, where a stack is any conceptually unlimited data structure which can (at least) support `push` and `pop` operations to store and access information on a last-in-first-out basis. It's not just a simple array with a stack pointer. – Mike Dunlavey Dec 02 '13 at 17:02
@MikeDunlavey: `push` doesn't insert into the middle. If it does, that steps way outside the definition of a stack. That's part of why i mentioned doubly-linked lists; you don't need to pop, and at the end, your list can contain all of the nodes in the order you want to process them. – cHao Dec 02 '13 at 17:20
So really, it is used when iteration is simply unavailable? As @Nathan remarked, there are even some language that don't have iteration (which I have no idea why they would not!) – Billy Thorton Dec 03 '13 at 00:45
@BillyThorton: It depends on the problem being solved. If the problem you have requires a depth-first walk of a tree, you cannot do it without recursion. So if you are doing it in a language that does not have recursive functions, you fake it, in trampoline-style, as cHao was saying. Recursion as a language feature first appeared, to my knowledge, in Algol (maybe Lisp). Then later, computers were equipped with stacks, so compiling recursive functions was made easier. If you want to see a computer done before this, look up IBM 360 or 7094. – Mike Dunlavey Dec 03 '13 at 02:44

score 2 · Answer 2 · answered Dec 02 '13 at 15:47

Well, for one thing, it's used in functional programming languages (like Haskell), which don't really have iteration, and they are optimized for recursion. Also, for some problems (like working with binary trees), recursions is a very natural and clean solution.

Why use recursion?

2 Answers2