Example of Recursion That Can't be Accomplished By While Loop

Question

Are there situations when recursion is necessary, or even strongly preferable to a while loop in javascript or C# (doesn't matter which, usage seems to be the same).

There is a factorial example on MSDN (I removed the irrelevant stuff):

function factorial(num)
{
    var tmp = num;
    while (num-- > 2) {
        tmp *= num;
    }
    return tmp;
}

vs

function factorial(num)
{
     return (num * factorial(num - 1));
}

In short, is there any situation where the second example is preferrable to the first performance wise. Can it EVER accomplish something that the first example can't? If so, what?

Answer 1

Also, recursive algorithms (or implementations) are not inherently slower than iterative ones. In fact, every recursive algorithm can be implemented by an equivalent iterative implementation at the cost of having to keep track some intermediate/temporary values yourself, where the recursive version automatically keeps track of those in the function call stack. - Is recursive code slower than non-recursive code

In short, there is a way to write it iteratively in lieu of a recursive method. Then there comes up questions such as overhead such as in java or python versus the shortcuts that exist in C where your overhead recursion ends up being jumps in the methodology.

In Javascript, recursion is not tail-ended prior to ES2015, so recursion becomes extremely cost-deficient in the long run. Taken from Performance: recursion vs. iteration in Javascript, however after this, Javascript DOES have TER/TCO, so it becomes less costly to invest in recursion. In my opinion, it is a tossup of personal preference between the two in JS. If you can make the recursive functionality and appearance of the code clean and quick, it will perform roughly on par with the iterative version which can become quite heinous to follow and even debug.

In C#, recursion can often be slower than an iterative solution at the cost of readability. However, it again comes down to personal preference. With C# creating overhead and a new stack frame on each "loop/step", it typically is not as performant. In other languages, recursion is as powerful as an iterative solution.

For many languages this is not the case, and recursion is equally or more performant than an iterative version

See: Recursion preferred? for some additional Q/A on why it is preferred in some languages which are not Java, C#, overhead deficient languages.

Answer 2

If the task you can solve with recursion, you can solve it with loops and vice versa. In the recursion the your method's scope creates the same scope again and again.So if your method's size is 1KB in the 10 steps recurion your logic will spend 10KB space.In the loops the spended space will be only 1KB.

There are tasks which you can easily solve by recursion, but it will be hard with loops. One of them is the Hanoi towers

Answer 3

I fully concur with the previous answers: recursion is often convenient for focus. It's great to reduce the problem to a check for completion, plus a simple processing step if not done. Let the OS handle your bookkeeping.

I'm adding the note that there are some functions that are not primitive recursive; the best known (and first discovered) is the Ackermann function. In practical terms, you could implement it with loops and your own stack, but you really, really wouldn't want to.

In even more practical terms, it's very unlikely that you will ever need to implement a function that is not primitive recursive. The Ackerman function is of great theoretical interest, but it's not something we hit in everyday life, even in deep learning or high-performance computing.

Answer 4

The crucial point in your question is the function stack. return (num * factorial(num - 1)); is not in tail position that is, the recursive call factorial(num - 1) is not the last action of the recursive function. The last action is the multiplication with num. So your factorial needs the stack to work. When you eliminate the stack with a tail recursive version factorial(acc * num, num - 1), you need to mimic the stack with an additional argument, namely acc.

Loops themselves are not as expressive as recursion, due to the lack of a stack. That means you can't implement a loop version that is equivalent to your non-tail recursive implementation. Actually your while implementation is equivalent to the tail recursive version of factorial. Tail recursive means that all recursive calls share a stack frame and thus are eliminated - there is no longer a stack. Your tmp is just acc - it mimics the function stack and accumulates the result of the iterations. Try to implement factorial with your while loop but without an additional variable like tmp. It is impossible.

However, the problem with non-tail recursive solutions is that they might blow up the stack, whereas tmp is just stored on the heap.

Here is the complete tail recursive solution:

function fact(acc, num) {
  return num > 1
   ? fact(acc * num, num - 1) // tail recursive case
   : acc; // base case
}

console.log(fact(1, 5));

Conclusion:

Are there situations when recursion is necessary, or even strongly preferable to a while loop

No. Tail recursion and simple loops are equivalent. Non-tail recursion and loops with their own stack are almost equivalent, except that a non tail recursive function stores its intermediate results in the function stack and thus stack overflows can occur. Loops with an own stack store it on the heap and thus don't have this limitation.