General questions about recursion

Question

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 be very deep. It will consume lots of memory. Am I right?

Answer 1

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!