¿Es correcto decir que dondequiera que se use la recursividad se forpodría usar un bucle? Y si la recursividad suele ser más lenta, ¿cuál es la razón técnica para usarla en foriteración de bucle?

Y si siempre es posible convertir una recursividad en un forbucle, ¿existe una regla general para hacerlo?

La recursividad suele ser mucho más lenta porque todas las llamadas a funciones deben almacenarse en una pila para permitir el retorno a las funciones del llamador. En muchos casos, la memoria debe asignarse y copiarse para implementar el aislamiento del alcance.

Algunas optimizaciones, como la optimización de la llamada de cola , hacen que las recursiones sean más rápidas, pero no siempre son posibles y no se implementan en todos los idiomas.

Las principales razones para utilizar la recursividad son

• que es más intuitivo en muchos casos cuando imita nuestro enfoque del problema
• que algunas estructuras de datos como los árboles son más fáciles de explorar usando la recursividad (o necesitarían pilas en cualquier caso)

Por supuesto, cada recursividad se puede modelar como una especie de bucle: eso es lo que finalmente hará la CPU. Y la recursividad en sí, más directamente, significa poner las llamadas de función y los ámbitos en una pila. Pero cambiar su algoritmo recursivo a uno de bucle podría requerir mucho trabajo y hacer que su código sea menos fácil de mantener: como para cada optimización, solo debe intentarse cuando algún perfil o evidencia muestre que es necesario.

¿Es correcto decir que dondequiera que se use la recursividad, se podría usar un bucle for?

Sí, porque la recursividad en la mayoría de las CPU se modela con bucles y una estructura de datos de pila.

Y si la recursividad suele ser más lenta, ¿cuál es la razón técnica para usarla?

No es "normalmente más lento": es la recursividad que se aplica incorrectamente lo que es más lento. Además de eso, los compiladores modernos son buenos para convertir algunas recursiones en bucles sin siquiera preguntar.

Y si siempre es posible convertir una recursividad en un bucle for, ¿existe una regla general para hacerlo?

Escriba programas iterativos para algoritmos que se comprendan mejor cuando se explican de manera iterativa; escribir programas recursivos para algoritmos que se expliquen mejor de forma recursiva.

Por ejemplo, la búsqueda de árboles binarios, la ejecución de ordenación rápida y el análisis de expresiones en muchos lenguajes de programación a menudo se explica de forma recursiva. Estos también se codifican mejor de forma recursiva. Por otro lado, calcular factoriales y calcular números de Fibonacci es mucho más fácil de explicar en términos de iteraciones. Usar la recursividad para ellos es como aplastar moscas con un mazo: no es una buena idea, incluso cuando el mazo hace un buen trabajo ⁺ .

Pregunta:

Y si la recursividad suele ser más lenta, ¿cuál es la razón técnica para usarla para la iteración de bucle?

Responder :

Porque en algunos algoritmos es difícil resolverlo de forma iterativa. Intente resolver la búsqueda en profundidad de forma recursiva e iterativa. Obtendrá la idea de que es simplemente difícil resolver DFS con iteración.

Otra cosa buena para probar: intente escribir Merge sort iterativamente. Te llevará bastante tiempo.

Pregunta:

¿Es correcto decir que dondequiera que se use la recursividad, se podría usar un bucle for?

Responder :

Si. Este hilo tiene una muy buena respuesta para esto.

Pregunta:

Y si siempre es posible convertir una recursividad en un bucle for, ¿existe una regla general para hacerlo?

Responder :

Créeme. Intente escribir su propia versión para resolver la búsqueda en profundidad de forma iterativa. Notarás que algunos problemas son más fáciles de resolver de forma recursiva.

Sugerencia: la recursividad es buena cuando se está resolviendo un problema que se puede resolver mediante la técnica de dividir y conquistar .

Además de ser más lenta, la recursividad también puede resultar en errores de desbordamiento de pila dependiendo de qué tan profundo sea.

Para escribir un método equivalente usando iteración, debemos usar explícitamente una pila. El hecho de que la versión iterativa requiera una pila para su solución indica que el problema es lo suficientemente difícil como para que pueda beneficiarse de la recursividad. Como regla general, la recursividad es más adecuada para problemas que no se pueden resolver con una cantidad fija de memoria y, en consecuencia, requieren una pila cuando se resuelven iterativamente. Dicho esto, la recursividad y la iteración pueden mostrar el mismo resultado mientras siguen un patrón diferente. Decidir qué método funciona mejor es caso por caso y la mejor práctica es elegir en función del patrón que sigue el problema.

Por ejemplo, para encontrar el n-ésimo número triangular de una secuencia triangular: 1 3 6 10 15… Un programa que usa un algoritmo iterativo para encontrar el n-ésimo número triangular:

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

La mayoría de las respuestas parecen asumir que iterative= for loop. Si su bucle for no tiene restricciones ( a la C, puede hacer lo que quiera con su contador de bucles), entonces eso es correcto. Si se trata de un verdadero for bucle (digamos como en Python o la mayoría de los lenguajes funcionales donde no se puede modificar manualmente el contador del bucle), entonces es no correcta.

Todas las funciones (computables) se pueden implementar tanto de forma recursiva como mediante whilebucles (o saltos condicionales, que son básicamente lo mismo). Si realmente se restringe for loops, solo obtendrá un subconjunto de esas funciones (las primitivas recursivas, si sus operaciones elementales son razonables). Por supuesto, es un subconjunto bastante grande que contiene todas las funciones que es probable que encuentre en la práctica.

Lo que es mucho más importante es que muchas funciones son muy fáciles de implementar de forma recursiva y terriblemente difíciles de implementar de forma iterativa (la gestión manual de la pila de llamadas no cuenta).

Sí, como dicho por Thanakron Tandavas ,

La recursividad es buena cuando estás resolviendo un problema que puede resolverse mediante la técnica de divide y vencerás.

Por ejemplo: Towers of Hanoi

1. N anillos en tamaño creciente
2. 3 polos
3. Los anillos comienzan apilados en el poste 1. El objetivo es mover los anillos para que queden apilados en el poste 3 ... Pero
   • Solo se puede mover un anillo a la vez.
   • No se puede poner un anillo más grande encima del más pequeño.
4. La solución iterativa es "poderosa pero fea"; La solución recursiva es "elegante".

Creo recordar que mi profesor de ciencias de la computación dijo en su día que todos los problemas que tienen soluciones recursivas también tienen soluciones iterativas. Él dice que una solución recursiva suele ser más lenta, pero se usan con frecuencia cuando son más fáciles de razonar y codificar que las soluciones iterativas.

Sin embargo, en el caso de soluciones recursivas más avanzadas, no creo que siempre pueda implementarlas usando un forbucle simple .

recursividad + memorización podría conducir a una solución más eficiente en comparación con un enfoque iterativo puro, por ejemplo, verifique esto: http://jsperf.com/fibonacci-memoized-vs-iterative-for-large-n

Respuesta corta: la compensación es que la recursividad es más rápida y los bucles for ocupan menos memoria en casi todos los casos. Sin embargo, generalmente hay formas de cambiar el bucle for o la recursividad para que se ejecute más rápido