General questions about recursion

As I understand, good recursive solutions can make complicated problems become easier. They can be more efficient in terms of either time or space.

My question is: this is not free, and the call stack will 开发者_C百科be very deep. It will consume lots of memory. Am I right?

It's hard to precisely pin down the tradeoffs involved with recursion.

At a mathematically abstract level, recursion gives a powerful framework for describing the explicit behavior of a function. For example, we can mathematically define factorial as

x! = 1             if x == 0
x! = x * (x - 1)!  else

Or we could define a more complex function recursively, such as how we might compute "N choose K":

C(n, k) = 1                             if k == 0
C(n, k) = 0                             if k < 0 or if n > k
C(n, k) = C(n - 1, k) + C(n - 1, k - 1) else

When using recursion as an implementation technique, there is no guarantee that you will end up using more memory or producing code that runs more efficiently. Often, recursion uses more space because of the memory required to hold the stack frames, but in some languages this isn't a problem as the compiler can try to optimize away the function calls (see, for example, tail call elimination). In other cases, recursion can use up enormous resources to the point where recursive code can fail to terminate on simple problems.

As for efficiency concerns, often recursive code is substantially less efficient than iterative code. Function calls are expensive, and the naive translation from recursion to code leads to unnecessary duplication of work. For example, the naive Fibonacci implementation

int Fibonacci(int n) {
    if (n <= 1) return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Is horrendously inefficient and is so slow it's never used in practice. Although the code is cleaner, the inefficiency eats away any potential benefits of the recursion.

In other cases, though, recursion can be an amazing time-saver. As an example, mergesort is a very fast sorting algorithm defined by a beautiful recursion:

Mergesort(array, low, high) {
    if (low >= high - 1) return;
    Mergesort(array, low, low + (high - low) / 2);
    Mergesort(array, low + (high - low) / 2, high);
    Merge(array, low, low + (high - low) / 2, high);
}

This code is extremely fast and the corresponding iterative code would likely be slower, harder to read, and harder to understand.

So, in short, recursion is neither a magic cure-all nor a force to be avoided. It helps illuminate the structure of many problems that otherwise might seem difficult or nigh impossible. While it often leads to clearer code, it often does so at the expense of time and memory (though it is not necessarily automatically less efficient; it can be more efficient in many cases). It's definitely worth studying to improve your overall algorithmic thinking and problem-solving skills even if you never write another recursive function in your life.

Hope this helps!

Practically the call stack won't be very deep. Take for example a divide and conquer algorithm like quicksort which divides the problem into two halfs. With a call stack of depth 32 you can sort 4G elements, which probably won't even fit in the memory of an average computer. Memory consumption isn't really a problem, it's a stack and it's free as long as you don't run out of it.. (and with 32 levels you have a lot of data to store there for each level).

You can rewrite practically all resursive processes to iterative ones if you maintain the state on the heap in a stack structure, but it's just complicates the code. The main scenario where you can get real benefits from rewriting is when you have a tail recursive code that doesn't need to maintain state for each recursive call. Note that for some languages (most functional programming languages and C/C++, maybe Java as well) a good compiler can do this for you.

That depends. The problems for which recursion is best suited will be resistant to this problem. A common example would be Mergesort, in which for sorting a list of N items there will be about log2(N) stack frames. So if your stack frame limit is 200, and you have used 50 by the time you call Mergesort, that is still good enough to sort about 2^150 items without a stack overflow. Also, Mergesort does not create a lot of memory for each stack frame, so total memory use for Mergesort should never be significantly more than double the size of the original list.

Also, some languages (Scheme is a good example) use tail-call elimination so that code can be written elegantly using recursion, but then optimized or compiled into an iterative loop. This is one of the ways in which LISP, being a functional language, is still able to compete with C and C++ in terms of execution speed.

There is another technique called Trampolining that can be used to perform seemingly-recursive operations without producing a deep call stack. But unless it is built into a library or even a language-level construct, this technique has a less clear advantage in productivity (in my view).

So while it's hard to argue against a good old for x in xrange(10) loop in many situations, recursion does have its place.

Cons:
 It is hard (especially for inexperienced programmers) to think recursively
 There also exists the problem of stack overflow when using some forms of recursion (head
recursion).
 It is usually less efficient because of having to push and pop recursions on and off the
run-time stack, so it can be slower to run than simple iteration.

But why do we bother to use recursions?

Pros:
 It is easier to code a recursive solution once one is able to identify that solution. The
recursive code is usually smaller, more concise, more elegant, and possibly even easier to
understand, though that depends on one’s thinking style☺
 There are some problems that are very difficult to solve without recursion. Those problems
that require backtracking such as searching a maze for a path to an exit or tree based
operations are best solved recursively.

It's only expensive if your recursion isn't tail recursive and your language doesn't support tail recursion. See the following wikipedia article on tail calls for a discussion on the subject:

http://en.wikipedia.org/wiki/Tail_call

Otherwise, it can make the code far easier to read and easier to test.

It depends on the problem.

If the problem requires recursion, like a depth-first tree walk, the only way you can avoid recursion is to simulate it by writing your own stack. That won't save anything.

If the problem doesn't require recursion, like the usual ho-hum factorial or fibonacci function, what's the point? You're not gaining anything by using it.

It's a pretty small class of problems where you might even have a reasonable choice.