When to use recursion and when to use loops?

39

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

asked by anonymous 16.06.2014 / 19:13

3 answers

25

The answer depends heavily on context.

Situations in which to use recursion

When 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 these is when you know in advance that there will not be many call levels and the iterative version would spend more processing and memory with a stack of states.

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

When the iterative version is too complicated

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

The problem is that sometimes the solution is so more complex that in practice the recursive version has a better cost-benefit. An example that 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 Naturally Used Techniques in Recursion Can Be Used

Recursive algorithms can naturally take advantage of caching and memoization techniques to get 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, hard-coding, and understanding code
  • It can lead to another question and answer site, i.e. causing a StackOverflow, after bursting the maximum stacking of the language or the processor.

Conclusion

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

    
16.06.2014 / 20:14
12

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

  

Considering that a programming language being used has both features ...

Having both features is 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: language needs to support Tail Call Optimization for recursion to be feasible in most cases. Unless for a particular problem the iterative solution also employs a stack, and that stack is as or more inefficient in memory consumption than the calling stack, the [naive] recursive functions will in general less efficient than iterative.

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

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.

Taking the fact that the syntax is ugly and verbose (which could easily be fixed with a syntactic sugar >), the problem with this code is that the use of assert and retract is relatively expensive in Prolog, so a recursive solution [with recursion of the tail] 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 issue of code uniformity and maintainability. If the vast majority of programs in language X use iteration, using recursion when there is a perfectly simple, concise, and efficient alternative that solves the same problem via iteration, we want to look for a problem:

  • Whoever gets the code for maintenance will find it harder to understand, so you'll spend more time "training your surrogate";
    • Whether it's a "lower common denominator" case or not: I myself have a lot of experience with recursion (I worked with Prolog in the past) but if I inherited a Java or Python code and he was in that format, I would probably rewrite it the first time he presented problems.
  • Language debugging tools and techniques are probably best suited to handle iterative rather than recursive code;
  • Stack errors for example) tend to get quite large, as they are also better suited to handle iterative code;
  • Idem for profiling tools speculation - I have no concrete data / experience on the subject to serve as a basis for this statement);
  • For these reasons, this code will be a strong candidate to be rewritten in the future, leading to rework.
  • The same arguments should also apply to the opposite scenario (use iteration in a predominantly recursive language), but I do not have enough experience to express my opinion (in the case of Prolog, there are many situations in which the iteration is the best tool yes, unlike the impression that a beginner in that language might have - there's even a built-in specific to this ... ).

        
    19.06.2014 / 11:31
    5

    Whenever possible avoid this feature . Recursive calls are interesting and elegant, but they spend more memory (because they have to store the N recursive calls and return them respectively) and on more limited platforms like PIC, you can pop the PC limit if you do not take care (120 calls) in the PIC18 family.

    On the other hand there are problems in which the use of recursion is common because to solve the problem without recursion it would be necessary to create a stack to keep the order of the calls as in torre de hanoi or 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)

        
    16.06.2014 / 19:21