recursão versus iteração

109

É correto dizer que em todos os lugares onde a recursão é usada, um forloop pode ser usado? E se a recursão costuma ser mais lenta, qual é a razão técnica para usá-la em vez da foriteração do loop?

E se sempre for possível converter uma recursão em um forloop, existe uma maneira de fazer isso?

Breako Breako
fonte
3
recursionvs iteration? iteration = for loopEu acho que.
gongzhitaao
4
O blog de Tom Moertel tem quatro excelentes postagens sobre a conversão de código recursivo em código iterativo: blog.moertel.com/tags/recursion.html
cjohnson318

Respostas:

146

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

Algumas otimizações, como a otimização de chamada final , 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 recursão são

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

É claro que toda recursão pode ser modelada como uma espécie de loop: é isso que a CPU fará. E a recursão em si, mais diretamente, significa colocar as chamadas de função e escopos em uma pilha. Mas mudar seu algoritmo recursivo para um loop pode exigir muito trabalho e tornar seu código menos sustentável: como para toda otimização, ela só deve ser tentada quando algum perfil ou evidência mostrar que é necessário.

Denys Séguret
fonte
10
Para adicionar a isso, a recursão está intimamente relacionada ao termo de redução que desempenha um papel central em muitos algoritmos e no CS em geral.
SomeWittyUsername
3
Você pode me fornecer um exemplo em que a recursão torna o código mais sustentável? Na minha experiência, é sempre o contrário. Obrigado
Yeikel
@Yeikel Escreva uma função f(n)que retorna o enésimo número de Fibonacci .
Matt
54

É correto dizer que em todos os lugares a recursão é usada um loop for pode ser usado?

Sim, porque a recursão na maioria das CPUs é modelada com loops e uma estrutura de dados em pilha.

E se a recursão costuma ser mais lenta, qual é a razão técnica para usá-la?

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

E se sempre for possível converter uma recursão em um loop for, existe uma maneira de fazer isso?

Escreva programas iterativos para algoritmos melhor compreendidos quando explicados iterativamente; escrever programas recursivos para algoritmos melhor explicados recursivamente.

Por exemplo, pesquisar árvores binárias, executar quicksort e analisar expressões em muitas linguagens de programação geralmente é explicado recursivamente. Esses são melhor codificados recursivamente também. Por outro lado, computar fatoriais e calcular números de Fibonacci são muito mais fáceis de explicar em termos de iterações. Usar a recursão para eles é como matar moscas com uma marreta: não é uma boa ideia, mesmo quando a marreta faz um trabalho realmente bom + .


+ Eu peguei emprestado a analogia da marreta da "Disciplina de Programação" de Dijkstra.

dasblinkenlight
fonte
7
A recursão é geralmente mais cara (mais lenta / mais memória), por causa da criação de quadros de pilha e tal. A diferença pode ser pequena quando aplicada corretamente para um problema suficientemente complexo, mas ainda é mais caro. Existem possíveis exceções, como otimização de recursão de cauda.
Bernhard Barker
Não tenho certeza sobre um único loop for em todos os casos. Considere uma recursão mais complexa ou uma recursão com mais de uma variável
SomeWittyUsername
@dasblinkenlight Pode ser teoricamente possível reduzir vários loops para um único, mas não tenho certeza sobre isso.
SomeWittyUsername
@icepack Sim, é possível. Pode não ser bonito, mas é possível.
Bernhard Barker
Não tenho certeza se concordo com sua primeira declaração. As próprias CPUs não modelam a recursão, são as instruções que estão sendo executadas na CPU que modelam a recursão. em segundo lugar, uma estrutura de loop não tem (necessariamente) um conjunto de dados que cresce e diminui dinamicamente, onde um algoritmo recursivo geralmente irá para cada nível de profundidade que a recursão deve passar.
trumpetlicks
28

Questão:

E se a recursão costuma ser mais lenta, qual é a razão técnica para usá-la para iteração de loop?

Responda :

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

Outra boa coisa a se experimentar: tente escrever a classificação de mesclagem de forma iterativa. Isso levará algum tempo.

Questão:

É correto dizer que em todos os lugares a recursão é usada um loop for pode ser usado?

Responda :

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

Questão:

E se sempre for possível converter uma recursão em um loop for, existe uma maneira de fazer isso?

Responda :

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

Dica: a recursão é boa quando você está resolvendo um problema que pode ser resolvido com a técnica de dividir para conquistar .

Thanakron Tandavas
fonte
3
Agradeço a tentativa de fornecer uma resposta confiável e tenho certeza de que o autor é inteligente, mas "confie em mim" não é uma resposta útil a uma pergunta significativa cuja resposta não seja imediatamente óbvia. Existem algoritmos muito simples para fazer uma pesquisa iterativa em profundidade. Veja o exemplo na parte inferior desta página para uma descrição de um algoritmo em pseudocódigo: csl.mtu.edu/cs2321/www/newLectures/26_Depth_First_Search.html
jdelman
3

Além de ser mais lenta, a recursão também pode resultar em erros de estouro de pilha, dependendo de sua profundidade.

G. Steigert
fonte
3

Para escrever um método equivalente usando iteração, devemos usar explicitamente uma pilha. O fato de que a versão iterativa requer uma pilha para sua solução indica que o problema é difícil o suficiente para que ele possa se beneficiar da recursão. Como regra geral, a recursão é mais adequada para problemas que não podem ser resolvidos com uma quantidade fixa de memória e, conseqüentemente, requerem uma pilha quando resolvidos iterativamente. Dito isso, a recursão e a iteração podem mostrar o mesmo resultado, embora sigam padrões diferentes. Para decidir qual método funciona melhor, é necessário decidir 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 ené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)); 
   }
}
Shirin
fonte
1

A maioria das respostas parece assumir que iterative= for loop. Se o seu loop for irrestrito ( a la C, você pode fazer o que quiser com o contador de loop), então está correto. Se é um verdadeiro for loop (dizer como em Python ou a maioria das linguagens funcionais, onde você não pode modificar manualmente o contador de loop), então é não correta.

Todas as funções (computáveis) podem ser implementadas recursivamente e usando whileloops (ou saltos condicionais, que são basicamente a mesma coisa). Se você realmente se restringir a for loops, obterá apenas um subconjunto dessas funções (as recursivas primitivas, 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 terrivelmente difíceis de implementar iterativamente (gerenciar manualmente sua pilha de chamadas não conta).

Jbeuh
fonte
1

Sim, como disse por Thanakron Tandavas ,

A recursão é boa quando você está resolvendo um problema que pode ser resolvido pela técnica de dividir para 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 na pole 1. O objetivo é mover os anéis de forma que eles sejam empilhados na pole 3 ... Mas
    • Só pode mover um anel de cada vez.
    • Não é possível colocar um anel maior em cima do menor.
  4. A solução iterativa é “poderosa, mas feia”; solução recursiva é “elegante”.
Ramesh Mukkera
fonte
Um exemplo interessante. Acho que você conhece o artigo de MC Er "As torres de Hanói e os números binários". Também tratado em um vídeo fantástico de 3brown1blue.
Andrestand
0

Parece que me lembro do meu professor de ciência da computação dizer 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 elas são frequentemente usadas quando são mais fáceis de raciocinar e codificar do que soluções iterativas.

Porém, no caso de soluções recursivas mais avançadas, não acredito que sempre será capaz de implementá-las usando um forloop simples .

Rio Vivian
fonte
Sempre é possível converter um algoritmo recursivo em um iterativo (usando pilhas). Você pode não acabar com um loop particularmente simples, mas é possível.
Bernhard Barker,
-4

recursão + memorização pode levar a uma solução mais eficiente em comparação com uma abordagem iterativa pura, por exemplo, verifique isto: http://jsperf.com/fibonacci-memoized-vs-iterative-for-large-n

Reza Afzalan
fonte
3
Qualquer código recursivo pode ser convertido em código iterativo funcionalmente idêntico usando pilhas. A diferença que você está mostrando é a diferença entre duas abordagens para resolver o mesmo problema, não a diferença entre recursão e iteração.
Bernhard Barker,
-6

Resposta curta: a desvantagem é que a recursão é mais rápida e os loops for ocupam menos memória em quase todos os casos. No entanto, geralmente há maneiras de alterar o loop for ou recursão para fazê-lo funcionar mais rápido

Jessica Shu
fonte