General Recursion Questions

Question

As I understand it, good recursive solutions can complicate complex problems. They may be more effective in terms of time or space.

My question is: this is not free, and the call stack will be very deep. It will consume a lot of memory. I'm right?

Answer 1

It is difficult to pinpoint the trade-offs associated with recursion.

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

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

Or we could define a more complex function recursively, for example, how we could calculate "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 

Using recursion as an implementation method does not guarantee that you will end up using more memory or code that works more efficiently. Often, recursion uses more space due to the memory required to store stack frames, but in some languages ​​this is not a problem, since the compiler may try to optimize function calls (see, for example, eliminating tail calls). In other cases, recursion can use huge resources until the recursive code cannot complete with simple problems.

Regarding performance issues, often recursive code is significantly less efficient than iterative code. Functional challenges are expensive, and a naive translation from recursion to code leads to unnecessary duplication of work. For example, a naive Fibonacci implementation

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

It is wonderfully inefficient and so slow that it has never been used in practice. Although the code is cleaner, inefficiency takes away any potential benefits of recursion.

In other cases, recursion can be an amazing time saver. As an example, mergesort is a very fast sorting algorithm defined by 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 very fast, and the corresponding iterative code is likely to be slower, harder to read, and harder to understand.

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

Hope this helps!

Answer 2

In practice, the call stack will not be very deep. Take, for example, a separation and subjugation algorithm such as quicksort that divides the problem into two halves. With a 32-inch call stack, you can sort 4G items that probably won't even fit into the memory of the average computer. Memory consumption is not really a problem, it is a stack and it is free until you have exhausted it. (And with 32 levels, you have a lot of data to store there for each level).

You can rewrite almost all recursive processes to iterative ones if you save the state on the heap in the stack structure, but it just complicates the code. The main scenario in which you can get the real benefits of rewriting is when you have a tail recursive code that does not require state preservation for each recursive call. Note that for some languages ​​(most functional programming languages ​​and C / C ++, possibly Java also) a good compiler can do this for you.

Answer 3

It depends. Problems for which recursion is best suited will be resistant to this problem. A typical example would be Mergesort, in which there will be about log2 (N) frames in the stack to sort the list of N items. Therefore, if your stack frame size is 200, and you used 50 at the time you called Mergesort, it is still enough to sort about 2 ^ 150 elements without. In addition, Mergesort does not create a lot of memory for each frame of the stack, so the use of shared memory for Mergesort should never be significantly more than twice the size of the original list.

In addition, some languages ​​(a diagram is a good example) use tail removal so that the 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, which is a functional language, can still compete with C and C ++ in terms of execution speed.

There is another method called Trampolining that can be used to perform seemingly recursive operations without creating a stack of deep calls. But if it is not built into the library or even the design at the language level, this method has a less obvious performance advantage (in my opinion).

Therefore, when it is difficult at all costs to object to the old old for x in xrange(10) loop, recursion has its place.

Answer 4

 Cons: It is hard (especially for inexperienced programmers) to think recursively There also exists the problem of Qaru 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 are we trying to use recursion?

 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. 

Answer 5

It is only expensive if your recursion is not recursive and your language does not support tail recursion. See the following wikipedia article on tails for a discussion on this subject:

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

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

Answer 6

It depends on the problem.

If a problem requires recursion, such as a tree-like tree structure, the only way to avoid recursion is to simulate it by writing your own stack. It will not save anything.

If the problem does not require recursion, for example, the usual factual function of factorial or fibonacci, what point? You are not gaining anything using it.

This is a pretty small class of problems where you might even have a reasonable choice.