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?
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?
A resposta depende muito do contexto.
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.
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.
Algoritmos recursivos naturalmente podem obter vantagens de técnicas de caching e memoization para obter resultados muito mais rápidos.
A recursão como regra geral deve ser evitada principalmente pelos seguintes motivos:
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.
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:
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...).
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)
Por outro lado existem problemas que só podem ser resolvidos por recursão
Citation needed.
Commented
16/06/2014 às 19:41