Is there anything which can only be achieved by recursion?

Question

I am not sure but I had heard of an algorithm which can only be achieved by recursion. Does anyone know of such thing?

Answer 1

If I remember my algorithms correctly, there is nothing doable by recursion that cannot be done with a stack and a loop. I don't have the formal proof here at my fingertips, however.

Edit: it occurs to me that the answer, possibly, is that the only thing doable by recursion that is not doable with a stack+loop, is a stack overflow?

Answer 2

You can always simulate recursion by keeping your own stack. So no.

Answer 3

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

Excerpt:

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

1. The problem is much more clearly solved using recursion: there are many problems where the recursive solution is clearer, cleaner, and much more understandable. As long as the efficiency is not the primary concern, or if the efficiencies of the various solutions are comparable, then you should use the recursive solution.
2. Some problems are much easier to solve through recursion: there are some problems which do not have an easy iterative solution. Here you should use recursion. The Towers of Hanoi problem is an example of a problem where an iterative solution would be very difficult. We'll look at Towers of Hanoi in a later section of this guide.

Answer 4

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. Unless anybody has an implementation of it without recursion?

I would imagine any time one doesn't know the depth of the stack one is iterating over, recursion is the logical way to go. Sure, it may be doable with some hacked up loops, but is that good code?

Answer 5

You need to clarify what kind of recursion you are talking about. There's algorithmic recursion and there's recursion in the implementation. It is true that any recursive algorithm allows for a straightforward non-recursive implementation - one can easily do it by using the standard trick of simulating the recursion with manual stack.

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

So, that's one example for you: traversal of a tree, which has only parent-to-child links cannot be performed by a non-recursive algorithm.

Another example of an inherently recursive algorithm is the well-known QuickSort algorithm. QuickSort is always recursive, and it cannot be turned into a non-recursive algorithm simply because if you succeed in doing this it will no longer be QuickSort anymore. It will be a completely different algorithm. Granted, this sounds as an exercise in pure semantics, but nevertheless that's also something that is worth mentioning.