An example of a recursion that cannot be looped

Question

Are there situations where recursion is necessary or even very preferable for a while loop in javascript or C # (no matter which one seems to be the same).

There is a factorial MSDN example (I removed unnecessary things):

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 a situation where the second example is preferable to the first execution. Can NEVER achieve what the first example cannot do? If yes, then?

Answer 1

In addition, recursive algorithms (or implementations) are not inherently slower than iterative ones. In fact, each recursive algorithm can be implemented by an equivalent iterative implementation due to tracking some intermediate / temporary values ​​on its own, where the recursive version automatically tracks the stack of function calls. - Recursive code is slower than non-recursive code

In short, there is a way to write it iteratively instead of a recursive method. Then there are questions such as overhead, for example, in java or python, as well as shortcuts that exist in C, where your overhead recursion ends with a transition to the methodology.

In Javascript, recursion does not end until ES2015, so in the end, recursion becomes extremely cost-inefficient. Taken from Performance: recursion versus iteration in Javascript , however after that Javascript has TER / TCO, therefore it becomes less expensive to invest in recursion. In my opinion, this is a fake of personal preferences between them in JS. If you can make the recursive functionality and appearance of the code clean and fast, it will run roughly on par with the iterative version, which can become quite disgusting for tracking and even debugging.

In C #, recursion can often be slower than an iterative solution due to readability. However, this again comes down to personal preference. With C # creating overhead and a new stack stack at each "cycle / step", it is usually not so efficient. In other languages, recursion is as efficient as an iterative solution.

For many languages, this is not the case, and recursion is the same or more efficient than the iterative version

See: Recursion preferred? for some additional questions / answers about why it is preferable in some languages ​​that are not Java languages, C # is not enough.

Answer 2

If the problem you can solve with recursion , you can solve it with loops and vice versa. In recursion, the scope of your method creates the same scope over and over again. Therefore, if your method size is 1KB in repeating steps 10 , your logic will waste 10KB space. In the loop, the space will be only 1KB .

There are tasks that you can easily solve by recursion, but with loops it will be difficult. One of them is the tower of Hanoi

Answer 3

I completely agree with the previous answers: recursion is often convenient for focus. It is great to reduce the problem to a check to complete, plus a simple processing step if this is not done. Let the OS process your financial statements.

I add a note that there are some functions that are not primitive recursive; the most famous (and first discovered) Ackermann function. In practice, you can implement it with loops and your own stack, but you really would not want to.

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

Answer 4

The most important point in your question is the function stack. return (num * factorial(num - 1)); is not in the tail position, i.e. the recursive call of factorial(num - 1) not the last action of the recursive function. The last action is multiplying by num . Therefore, your factorial should work on the stack. When you delete a stack with a tail recursive version of factorial(acc * num, num - 1) , you need to map the stack to an additional argument, namely acc .

Loops themselves are not as expressive as recursion due to the lack of a stack. This means that you cannot implement a loop version that is equivalent to your non-recursive implementation without a tail. Actually, the while implementation is equivalent to the tail recursive version of factorial . A recursive tail means that all recursive calls share the stack frame and therefore are excluded - there is no longer a stack. Your tmp just acc - it simulates a stack of functions and accumulates the result of iterations. Try implementing factorial with a while , but without an additional variable like tmp . It's impossible.

However, the problem with irregular recursive solutions is that they can explode the stack, while tmp just stored on the heap.

Here is a 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)); 

Output:

Are there situations where recursion is necessary or even very preferable for a while loop

No. Tail recursion and simple loops are equivalent. Recursion without a tail and a loop with its own stack are almost equivalent, except that a non-tail recursive function saves its intermediate results in a function stack and, thus, a stack overflow can occur. Loops with their own stack store it on the heap and therefore do not have this limitation.