47

Um problema pode ser resolvido e obter o mesmo resultado utilizado um loop ou através de chamadas recursivas a uma função.

Considerando que a linguagem de programação sendo usada possua os dois recursos, como saber quando um é melhor que o outro?

3 Respostas 3

30

A resposta depende muito do contexto.

Situações em que usar recursão

Quando o desempenho for igual ou superior à versão iterativa do código

Há várias situações onde usar recursão é mais eficiente.

Uma delas é quando se sabe de antemão que não haverão muitos níveis de chamada e a versão iterativa gastaria mais processamento e memória com uma pilha de estados.

Outra é quando há a possibilidade de Otimização de Chamada em Cauda (Tail Call Optimization), como já discutido aqui no SOPT em algumas perguntas.

Quando a versão iterativa é complicada demais

Toda implementação recursiva pode ser "convertida" em iterativa de alguma forma. Em último caso, usa-se uma pilha para simular o estado de cada chamada. Veja alguns links do SO em Inglês para uma discussão mais completa.

O problema é que às vezes a solução é tão mais complexa que na prática a versão recursiva tem um melhor custo-benefício. Um exemplo que conheço pessoalmente é o caso que pode ser vista na minha pergunta e resposta sobre a versão iterativa (não recursiva) do algoritmo LCA.

Quanto técnicas naturalmente usadas em recursão puderem ser utilizadas

Algoritmos recursivos naturalmente podem obter vantagens de técnicas de caching e memoization para obter resultados muito mais rápidos.

Situações em que não devemos usar recursão

A recursão como regra geral deve ser evitada principalmente pelos seguintes motivos:

  • Comumente produz código complexo, de mais difícil manutenção e entendimento
  • Pode dar origem a mais um site de perguntas e respostas, i.e., causar um StackOverflow, após estourar o empilhamento máximo da linguagem ou do processador.

Conclusão

Não há uma resposta absoluta, pois há casos onde a solução iterativa é difícil de se obter ou tem desempenho inferior à recursiva. Porém, sempre que possível deve-se optar por uma solução não recursiva.

2
  • 4
    Não se esqueçam de ver este complemento
    – Maniero
    Commented 25/06/2014 às 16:55
  • Acho que há uma forma mais simples de responder: use recursão quando o problema sendo resolvido for recursivo (cálculos de fórmulas recursivas, mergesort, quicksort, destruição de estruturas de árvore, etc) e se, além disso, sua solução usando laços for complexa demais (caso contrário, evite recursão devido ao fato da recursão ter alto custo de memória e processamento). Há casos em que a recursão pode ser implementada sem precisar re-chamar a função mas sim empilhando dados, como é o caso da remoção de árvores.
    – RHER WOLF
    Commented 16/02/2018 às 8:53
14

Concordo com a resposta do utluiz, gostaria somente de dar o seguinte complemento:

Considerando que uma linguagem de programação sendo usada possua os dois recursos...

Possuir os dois recursos não basta, também é importante saber se eles são implementados com eficiência e se são usados extensivamente em programas escritos naquela linguagem.

Quanto à eficiência, metade da resposta já foi dada: a linguagem precisa dar suporte a Otimização de Chamada em Cauda (Tail Call Optimization) para a recursão ser viável na maioria dos casos. A menos que para um problema em particular a solução iterativa também empregue uma pilha, e essa pilha seja tão ou mais ineficiente em consumo de memória que a pilha de chamada, as funções recursivas [ingênuas] serão em geral menos eficientes que as iterativas.

A outra metade refere-se a linguagens que dão suporte a construções iterativas, mas que o modus operandi das mesmas seja recursivo por natureza. Nesse caso, há a possibilidade da versão iterativa do programa ser menos eficiente que a versão recursiva! Exemplo (Prolog; comentários em 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.

Tirando o fato da sintaxe ser feia e verbosa (o que poderia ser facilmente corrigido com um açúcar sintático), o problema desse código é que o uso de assert e retract é relativamente caro em Prolog, de modo que uma solução recursiva [com recursão de cauda] seria bem mais eficiente:

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).

Quanto a ser usado extensivamente, aí entra a questão da uniformidade do código e manutenabilidade. Se a grande maioria dos programas na linguagem X usa iteração, usar recursão quando existe uma alternativa perfeitamente simples, concisa e eficiente que resolva o mesmo problema via iteração, é querer procurar problema:

  1. Quem for pegar o código pra dar manutenção vai ter mais dificuldade de entendê-lo, de modo que você gastará mais tempo "treinando seu substituto";
    • Independentemente de ser um caso de "menor denominador comum" ou não: eu próprio tenho muita experiência com recursão (trabalhei um tempo com Prolog no passado), mas se eu herdasse um código Java ou Python e ele estivesse nesse formato, provavelmente eu o reescreveria na primeira ocasião em que ele apresentasse problemas.
  2. As ferramentas e técnicas de depuração da linguagem provavelmente serão melhores adaptadas para lidar com código iterativo do que com recursivo;
  3. Os relatórios de erros (stack trace por exemplo) tendem a ficar bem grandes, pois também são mais adaptados para lidar com código iterativo;
  4. Idem para ferramentas de profiling (Nota: especulação - não tenho dados concretos/experiência sobre o assunto para servir de base para essa afirmação);
  5. Por essas razões, esse código será um forte candidato a ser reescrito no futuro, acarretando em retrabalho.

Os mesmos argumentos devem valer também para o cenário oposto (usar iteração numa linguagem predominantemente recursiva), mas não tenho experiência suficiente para opinar (no caso de Prolog, há muitas situações em que a iteração é a melhor ferramenta sim, ao contrário da impressão que um iniciante nessa linguagem possa ter - há até um built-in específico para isso...).

6

Sempre que possível evite este recurso. Chamadas recursivas são interessantes e elegantes mais elas gastam mais memoria (porque tem que armazenar as N chamadas recursivas e retornando-as respectivamente) e em plataformas mais limitadas como PIC, você pode estourar o limite do PC se não tomar cuidado (120 chamadas) na família PIC18.

Por outro lado existem problemas nos quais o uso de recursão é comum pois para resolver o problema sem recursão precisaria-se de criar uma pilha para manter a ordem das chamadas como na torre de hanoi ou no mergesort.

Editado:

A resposta estava errada pois todo problema recursivo pode ser escrito na forma de loop (referência).

Dica de leitura: Como remover recursão usando pilha - (inglês)

6
  • 3
    Por outro lado existem problemas que só podem ser resolvidos por recursão Citation needed. Commented 16/06/2014 às 19:41
  • 2
    @Renan, corrigi a resposta estava errada.
    – Mansueli
    Commented 16/06/2014 às 19:50
  • @Renan fiquei curioso, poderia dar um exemplo que só é possível resolver com chamadas recursivas? Commented 16/06/2014 às 20:04
  • 1
    @LeonardoBosquett, Todo problema recursivo pode ser escrito como iterativo (veja a referência para mais detalhes).
    – Mansueli
    Commented 16/06/2014 às 20:08
  • 2
    Eu tenho um exemplo de um problema que só pode ser resolvido com chamada recursiva: como estourar a pilha de execução com uma única rotina? :D Brincadeiras a parte, +1. Commented 16/06/2014 às 20:18

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .