When to use recursion and when to use loops?

Question

A problem can be solved and get the same result used a loop or through recursive calls to a function.

Whereas the programming language being used has both features, how to know when one is better than the other?

Answer 1

The answer depends a lot on the context.

Situations where recursion is used

When the performance is equal to or greater than the iterative version of the code

There are several situations where using recursion is more efficient.

One of them is when it is known beforehand that there will not be many call levels and the iterative version would take more processing and memory with a stack of states.

Another is when there is the possibility of Tail Call Optimization (Tail Call Optimization), as already discussed here at SOPT in some questions.

When the iterative version is too complicated

Any recursive implementation can be "converted" to iterative in some way. In the latter case, a stack is used to simulate the state of each call. See some links of the OS in English for a more complete discussion.

The problem is that sometimes the solution is so much more complex that in practice the recursive version has a better cost-benefit. An example I know personally is the case that can be seen in my question and answer on the iterative (non-recursive) version of the LCA algorithm.

How many techniques naturally used in recursion can be used

Recursive algorithms can naturally take advantage of caching and memoization for much faster results.

Situations where we should not use recursion

Recursion as a general rule should be avoided mainly for the following reasons:

• Commonly produces complex code, more difficult to maintain and understand
• Can give rise to one more question and answer site, i.e., cause a Stackoverflow, after popping the maximum language or processor stacking.

Completion

There is no absolute answer, as there are cases where the iterative solution is difficult to obtain or performs less than recursive. However, where possible, a non-recurring solution should be chosen.

Answer 2

I agree with the answer of utluiz, I would just like to add the following:

Whereas a programming language being used has both features...

Possess the two resources are not enough, it is also important to know if they are implemented efficiently and if they are used extensively in programs written in that language.

As for efficiency, half of the answer has already been given: the language needs to support Tail Call Optimization (Tail Call Optimization) for recursion to be viable in most cases. Unless for a particular problem the iterative solution also employ a stack, and that stack is as or more inefficient in memory consumption as the call stack, [naive] recursive functions will generally be less efficient than iterative ones.

The other half refers to languages that support iterative constructs, but which modus operandi is recursive by nature. In this case, the iterative version of the program may be less efficient that the recursive version! Example (Prolog; Javascript comments):

soma(Inicio, Fim, Return) :-    %  function soma(Inicio, Fim) {
    dynamic(x/1),               %      var x;
    assertz(x(0)),              %      x = 0;
    between(Inicio, Fim, N),    %      for ( var N = Inicio ; N <= Fim ; N++ ) {
        retract(x(X)),          %          var X = x; x = undefined;
        X1 is X + N,            %          var X1 = X + N;
        assertz(x(X1)),         %          var x = X1;
        fail;                   %      }
    x(Return),                  %      return x;
    abolish(x/1).               %  }   // acabou o escopo de x

?- soma(1, 10, Resultado).
Resultado = 55.

Apart from the fact that the syntax is ugly and verbose (which could easily be corrected with a syntactic sugar), the problem of this code is that the use of assert and retract is relatively expensive in Prolog, so a recursive solution [with tail recursion] would be much more efficient:

soma(Inicio, Fim, Return) :- soma(Inicio, Fim, Fim, Return). /* Resultado Parcial = Fim */

soma(Inicio, Inicio, RParcial, RParcial).  /* Se o início for igual ao fim, retorne o Res. Parcial */
soma(Inicio, Fim, RParcial, Return) :-
    RParcial1 is RParcial + Inicio,        
    Proximo is Inicio + 1,
    soma(Proximo, Fim, RParcial1, Return).

As for being used extensively, there comes the question of uniformity of code and maintainability. If the vast majority of programs in the X language use iteration, use recursion when there is a perfectly simple, concise and efficient alternative that solves the same problem via iteration, it is wanting to look for problem:

1. Whoever takes the code for maintenance will have more difficulty understanding it, so you will spend more time "training your replacement";
   • Whether it is a case of "lowest common denominator" or not: I myself have a lot of recursion experience (I worked with Prolog for a while in the past), but if I inherited a Java or Python code and it was in that format, I would probably rewrite it the first time it presented problems.
2. Language debugging tools and techniques are likely to be better adapted to handle iterative code than recursive;
3. The reports of errors (stack trace for example) tend to get quite large as they are also more adapted to handle iterative code;
4. Idem for tools for Profiling (Note: speculation - I do not have concrete data/experience on the subject as a basis for this statement);
5. For these reasons, this code will be a strong candidate to be rewritten in the future, leading to reworking.

The same arguments must apply also to the opposite scenario (use iteration in a predominantly recursive language), but I don’t have enough experience to give an opinion (in the case of Prolog, there are many situations where iteration is the best tool yes, unlike the impression a beginner in this language might have - there is even one built-in specific to that...).

Answer 3

Where possible avoid this feature. Recursive calls are interesting and elegant plus they spend more memory (Because you have to store the N recursive calls and return them respectively) and on more limited platforms like PIC, you can exceed the PC limit if you don’t take care (120 calls) in the PIC18 family.

On the other hand there are problems in which recursion is common because to solve the problem without recursion would need to create a stack to maintain the order of the calls as in torre de hanoi or in the mergesort.

Edited:

The answer was wrong because every recursive problem can be written in loop form (reference).

Reading tip: How to remove recursion using stack - (English)