recursion versus iteração

É correto dizer que em toda parte a recursion é usada um loop for poderia ser usado? E se a recursion é geralmente mais lenta, qual é a razão técnica para usá-la na iteração de loop?

E se é sempre possível converter uma recursion em um loop for, existe uma maneira prática de fazer isso?

A recursion é geralmente muito mais lenta porque todas as chamadas de function devem ser armazenadas em uma pilha para permitir o retorno de volta às funções do chamador. Em muitos casos, a memory deve ser alocada e copiada para implementar o isolamento do escopo.

Algumas otimizações, como a otimização da chamada de retorno , tornam as recursões mais rápidas, mas nem sempre são possíveis, e não são implementadas em todos os idiomas.

As principais razões para usar a recursion são

  • que é mais intuitivo em muitos casos quando imita nossa abordagem do problema
  • que algumas estruturas de dados como trees são mais fáceis de explorar usando recursion (ou precisariam de pilhas em qualquer caso)

É claro que toda recursion pode ser modelada como um tipo de loop: é o que a CPU fará no final das contas. E a recursion em si, mais diretamente, significa colocar as chamadas de function e os escopos em uma pilha. Mas alterar seu algoritmo recursivo para um looping pode precisar de muito trabalho e tornar seu código menos sustentável: como para toda otimização, ele deve ser tentado apenas quando algum perfil ou evidência mostrar que é necessário.

É correto dizer que em toda parte a recursion é usada um loop for poderia ser usado?

Sim, porque a recursion na maioria das CPUs é modelada com loops e uma estrutura de dados de pilha.

E se a recursion é geralmente mais lenta, qual é a razão técnica para usá-la?

Não é “geralmente mais lento”: é a recursion aplicada incorretamente que é mais lenta. Além disso, os compiladores modernos são bons em converter algumas recursões em loops sem sequer perguntar.

E se é sempre possível converter uma recursion em um loop for, existe uma maneira prática de fazer isso?

Escrever programas iterativos para algoritmos mais bem compreendidos quando explicados iterativamente; escreva programas recursivos para algoritmos melhor explicados recursivamente.

Por exemplo, pesquisar trees binárias, executar quicksort e analisar expressões em muitas linguagens de programação é frequentemente explicado recursivamente. Estes são melhor codificados recursivamente também. Por outro lado, a computação de fatoriais e o cálculo de números de Fibonacci são muito mais fáceis de explicar em termos de iterações. Usar recursion para eles é como golpear moscas com uma marreta: não é uma boa idéia, mesmo quando a marreta faz um bom trabalho nisso + .


+ Eu peguei emprestada a analogia de marreta da “Discipline of Programming” de Dijkstra.

Pergunta:

E se a recursion é geralmente mais lenta, qual é a razão técnica para usá-la na iteração de loop?

Responda :

Porque em alguns algoritmos é difícil resolvê-lo iterativamente. Tente resolver a pesquisa primeiro em profundidade de forma recursiva e iterativa. Você terá a idéia de que é difícil resolver DFS com iteração.

Outra coisa boa para experimentar: tente escrever Mesclar iterativamente. Isso levará algum tempo.

Pergunta:

É correto dizer que em toda parte a recursion é usada um loop for poderia ser usado?

Responda :

Sim. Este tópico tem uma resposta muito boa para isso.

Pergunta:

E se é sempre possível converter uma recursion em um loop for, existe uma maneira prática de fazer isso?

Responda :

Confie em mim. Tente escrever sua própria versão para resolver iterativamente a pesquisa em profundidade. Você notará que alguns problemas são mais fáceis de resolvê-lo recursivamente.

Dica: A recursion é boa quando você está resolvendo um problema que pode ser resolvido pela técnica de dividir e conquistar .

Além de ser mais lenta, a recursion também pode resultar em erros de estouro de pilha, dependendo da profundidade dela.

Para escrever um método equivalente usando iteração, devemos usar explicitamente uma pilha. O fato de a versão iterativa exigir uma pilha para sua solução indica que o problema é difícil o suficiente para se beneficiar da recursion. Como regra geral, a recursion é mais adequada para problemas que não podem ser resolvidos com uma quantidade fixa de memory e, consequentemente, requerem uma pilha quando resolvidos iterativamente. Dito isto, a recursion e a iteração podem mostrar o mesmo resultado enquanto seguem um padrão diferente. Para decidir qual método funciona melhor é caso a caso e a melhor prática é escolher com base no padrão que o problema segue.

Por exemplo, para encontrar o enésimo número triangular da sequência Triangular: 1 3 6 10 15… Um programa que usa um algoritmo iterativo para encontrar o nésimo número triangular:

Usando um algoritmo iterativo:

 //Triangular.java import java.util.*; class Triangular { public static int iterativeTriangular(int n) { int sum = 0; for (int i = 1; i <= n; i ++) sum += i; return sum; } public static void main(String args[]) { Scanner stdin = new Scanner(System.in); System.out.print("Please enter a number: "); int n = stdin.nextInt(); System.out.println("The " + n + "-th triangular number is: " + iterativeTriangular(n)); } }//enter code here 

Usando um algoritmo recursivo:

 //Triangular.java import java.util.*; class Triangular { public static int recursiveTriangular(int n) { if (n == 1) return 1; return recursiveTriangular(n-1) + n; } public static void main(String args[]) { Scanner stdin = new Scanner(System.in); System.out.print("Please enter a number: "); int n = stdin.nextInt(); System.out.println("The " + n + "-th triangular number is: " + recursiveTriangular(n)); } } 

A maioria das respostas parece pressupor que iterative = for loop . Se o seu loop for irrestrito ( a la C, você pode fazer o que quiser com o contador de loops), então está correto. Se for um loop real (digamos, como em Python ou em linguagens mais funcionais, em que você não pode modificar manualmente o contador de loops), isso não está correto.

Todas as funções (computáveis) podem ser implementadas recursivamente e usando loops while (ou saltos condicionais, que são basicamente a mesma coisa). Se você realmente se restringir a for loops , você obterá apenas um subconjunto dessas funções (as primitivas recursivas, se suas operações elementares forem razoáveis). Concedido, é um subconjunto bastante grande que contém todas as funções que você provavelmente encontrará na prática.

O que é muito mais importante é que muitas funções são muito fáceis de implementar recursivamente e muito difíceis de implementar iterativamente (o gerenciamento manual da sua pilha de chamadas não conta).

Parece que lembro do meu professor de ciências da computação dizer no passado que todos os problemas que têm soluções recursivas também têm soluções iterativas. Ele diz que uma solução recursiva é geralmente mais lenta, mas eles são freqüentemente usados ​​quando são mais fáceis de raciocinar e codificar do que soluções iterativas.

No entanto, no caso de soluções recursivas mais avançadas, não acredito que sempre será possível implementá-las usando um loop for simples.

Sim, como dito por Thanakron Tandavas ,

A recursion é boa quando você está resolvendo um problema que pode ser resolvido pela técnica de dividir e conquistar.

Por exemplo: torres de Hanói

  1. N anéis em tamanho crescente
  2. 3 pólos
  3. Os anéis começam empilhados no poste 1. O objective é mover os anéis para que eles sejam empilhados no poste 3 … Mas
    • Só pode mover um anel de cada vez.
    • Não é possível colocar o anel maior em cima do menor.
  4. A solução iterativa é “poderosa, mas feia”; solução recursiva é “elegante”.

recursion + memorização poderia levar a uma solução mais eficiente comparar com uma abordagem puramente iterativa, por exemplo, verifique isso: http://jsperf.com/fibonacci-memoized-vs-iterative-for-large-n

Resposta curta: o trade off é recursivo é mais rápido e os loops ocupam menos memory em quase todos os casos. No entanto, geralmente há maneiras de alterar o loop for ou a recursion para torná-lo mais rápido