Is there something that can only be achieved through recursion?

Question

I'm not sure, but I heard about an algorithm that can only be achieved by recursion. Does anyone know of such a thing?

Answer 1

You need to clarify what kind of recursion you are talking about. There are algorithmic recursion and recursion in the implementation. It is true that any recursive algorithm allows a direct non-recursive implementation - this can easily be done using the standard recursion modeling trick with a manual stack.

However, your question only mentions algorithms. If we assume that we are talking about algorithmic recursion, then the answer is yes, there are algorithms that are inherently and inevitably recursive. In the general case, it is impossible to replace a recursive algorithm with a non-recursive one. The simplest way to build an algorithm with integral recursion is to first take the structure of the recursive structure. For example, let's say we only need to traverse the tree with parent connections (and without one-to-parent links). It is impossible to come up with a reasonable non-recursive algorithm to solve this problem.

So, this one example for you: traversing a tree that has only parent-to-child links cannot be performed by a non-recursive algorithm.

Another example of a recursive algorithm is the well-known QuickSort algorithm. QuickSort is always recursive and cannot be turned into a non-recursive algorithm simply because if you succeed, it will no longer be QuickSort. This will be a completely different algorithm. Of course, this sounds like an exercise in pure semantics, but nonetheless it is also worth mentioning.

Answer 2

You can always simulate recursion while keeping your own stack. Then no.

Answer 3

If I remember my algorithms correctly, then recursion cannot be performed, which cannot be done using the stack and loop. However, I have no formal evidence at my fingertips.

Edit: It seems to me that the answer, perhaps, is that the only thing that can be done, recursion that is not feasible with the stack + loop, is stack overflow?

Answer 4

The following compares recursive and non-recursive implementations: http://www.sparknotes.com/cs/recursion/whatisrecursion/section1.html

Excerpts:

Given that recursion is generally less efficient, why do we use it? There are two situations where recursion is the best solution:

• The problem is much more clearly solved with the help of recursion: there are many problems where the recursive solution is more clear, clean and understandable. As long as efficiency is not the primary concern, or if the effectiveness of different solutions is comparable, then you should use a recursive solution.
• Some problems are much easier to solve with recursion: there are some problems that do not have a simple iterative solution. Here you should use recursion. The Hanoi Tower problem is an example of a problem where an iterative solution will be very complex. We will cover the Hanoi Towers in the next section of this guide.

Answer 5

Are you just looking for a practical example of recursion? Recently, my friends and I implemented the Haar Wavelet function (as an exercise to start learning Ruby), which seemed to require recursion. Doesn't anyone implement it without recursion?

I would suggest that every time you don't know the depth of the stack you iterate, recursion is the logical way. Of course, this may be feasible with some hacked loops, but is this good code?