É 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?

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.

É 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 ⁺ .

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 .

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

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)); 
   }
}

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

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

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 .

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

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