Hay momentos en los que usar recursión es mejor que usar un bucle, y veces es mejor usar un bucle que usar recursión. Elegir el "correcto" puede ahorrar recursos y / o resultar en menos líneas de código.
¿Hay casos en los que una tarea solo se puede realizar mediante la recursión, en lugar de un bucle?
Sí y no. En última instancia, no hay nada que la recursión pueda calcular que el bucle no puede, pero el bucle requiere mucha más plomería. Por lo tanto, lo único que puede hacer la recursión es que los bucles no pueden hacer que algunas tareas sean muy fáciles.
Lleva caminando un árbol. Caminar un árbol con recursión es estúpido-fácil. Es la cosa más natural del mundo. Caminar un árbol con bucles es mucho menos sencillo. Debes mantener una pila o alguna otra estructura de datos para realizar un seguimiento de lo que has hecho.
A menudo, la solución recursiva a un problema es más bonita. Ese es un término técnico, y importa.
No.
Bajando a los conceptos básicos de muy de los mínimos necesarios para calcular, solo necesita poder realizar un bucle (esto solo no es suficiente, sino es un componente necesario). No importa how .
Cualquier lenguaje de programación que pueda implementar una máquina de Turing, se llama Turing completo . Y hay muchos idiomas que se están completando.
Mi idioma favorito en el camino de "que realmente funciona?" La integridad de Turing es la de FRACTRAN , que es Turing completo . Tiene una estructura de bucle, y puede implementar una máquina de Turing en ella. Por lo tanto, cualquier cosa que sea computable, puede implementarse en un lenguaje que no tenga recursión. Por lo tanto, no hay nada que la recursión pueda ofrecerle en términos de computabilidad que el simple bucle no puede.
Esto realmente se reduce a unos pocos puntos:
Esto no quiere decir que hay algunas clases de problemas en las que se puede pensar más fácilmente con la recursión en lugar de con el bucle, o con el bucle en lugar de con la recursión. Sin embargo, estas herramientas también son igualmente poderosas.
Y si bien llevé esto al extremo 'esolang' (principalmente porque puedes encontrar cosas que están completadas e implementadas de Turing de formas bastante extrañas), esto no significa que los esolangs sean de ninguna manera opcionales. Hay una lista completa de cosas que se completaron accidentalmente , incluyendo Magic the Gathering, Sendmail, MediaWiki y Sistema tipo scala. Muchos de estos están lejos de ser óptimos cuando se trata de hacer algo práctico, simplemente se puede calcular cualquier cosa que sea computable utilizando estas herramientas.
Esta equivalencia puede ser particularmente interesante cuando entras en un tipo particular de recursión conocido como llamada de cola .
Si tiene, digamos, un método factorial escrito como:
int fact(int n) {
return fact(n, 1);
}
int fact(int n, int accum) {
if(n == 0) { return 1; }
if(n == 1) { return accum; }
return fact(n-1, n * accum);
}
Este tipo de recursión se volverá a escribir como un bucle, sin pila. Tales enfoques son a menudo más elegantes y fáciles de entender que el bucle equivalente que se escribe, pero nuevamente, para cada llamada recursiva puede haber un bucle equivalente escrito y para cada bucle puede haber una llamada recursiva.
También hay momentos en los que convertir el bucle simple en una llamada recursiva de cola puede complicarse y más es difícil de entender.
Si quieres adentrarte en la parte teórica, consulta la tesis de la Iglesia en Turing . También puede encontrar que la church-turing-thesis en CS.SE es útil.
¿Hay casos en los que una tarea solo se puede hacer usando la recursión, en lugar de un bucle?
Siempre puede convertir el algoritmo recursivo en un bucle, que usa una estructura de datos de último en entrar, primero en salir (pila AKA) para almacenar el estado temporal, porque la llamada recursiva es exactamente eso, almacenar el estado actual en una pila, continuar con El algoritmo, luego restaurando el estado. La respuesta tan breve es: No, no hay tales casos .
Sin embargo, se puede hacer un argumento para "sí". Tomemos un ejemplo concreto y fácil: fusionar orden. Debe dividir los datos en dos partes, fusionar, ordenar las partes y luego combinarlas. Incluso si no realiza una llamada a la función del lenguaje de programación real para combinar la ordenación con el fin de hacer la ordenación de la fusión en las partes, necesita implementar una funcionalidad que sea idéntica a la de realizar una llamada a la función (empujar a su propia pila, saltar a inicio del bucle con diferentes parámetros de inicio, luego, luego, extraiga el estado de su pila).
¿Es una recursión, si implementa la recursión, hágalo usted mismo, como pasos separados de "estado de inserción" y de "salto al comienzo" y "estado emergente"? Y la respuesta es: No, todavía no se llama recursión, se llama iteración con pila explícita (si desea utilizar la terminología establecida).
Nota, esto también depende de la definición de "tarea". Si la tarea es ordenar, entonces puede hacerlo con muchos algoritmos, muchos de los cuales no necesitan ningún tipo de recursión. Si la tarea es implementar un algoritmo específico, como el ordenamiento por combinación, entonces se aplica la ambigüedad por encima.
Entonces, consideremos la pregunta, ¿hay tareas generales, para las cuales solo hay algoritmos de tipo recursivo? Del comentario de @WizardOfMenlo bajo la pregunta, función Ackermann es un ejemplo simple de eso. Por lo tanto, el concepto de recursión se sostiene por sí solo, incluso si se puede implementar con un programa de computadora diferente (iteración con pila explícita).
Depende de cómo estrictamente definas "recursión".
Si exigimos estrictamente que incluya la pila de llamadas (o cualquier mecanismo para mantener el estado del programa), siempre podemos reemplazarlo con algo que no lo haga. De hecho, los lenguajes que conducen naturalmente al uso intensivo de la recursión tienden a tener compiladores que hacen un uso intensivo de la optimización de la llamada de cola, por lo que lo que escribe es recursivo, pero lo que ejecuta es iterativo.
Pero consideremos un caso en el que hacemos una llamada recursiva y usamos el resultado de una llamada recursiva para esa llamada recursiva.
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
if (m == 0)
return n+1;
if (n == 0)
return Ackermann(m - 1, 1);
else
return Ackermann(m - 1, Ackermann(m, n - 1));
}
Hacer la primera llamada recursiva iterativa es fácil:
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
restart:
if (m == 0)
return n+1;
if (n == 0)
{
m--;
n = 1;
goto restart;
}
else
return Ackermann(m - 1, Ackermann(m, n - 1));
}
Luego podemos limpiar y eliminar goto para evitar velociraptors y la sombra de Dijkstra:
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
while(m != 0)
{
if (n == 0)
{
m--;
n = 1;
}
else
return Ackermann(m - 1, Ackermann(m, n - 1));
}
return n+1;
}
Pero para eliminar las otras llamadas recursivas, tendremos que almacenar los valores de algunas llamadas en una pila:
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
Stack<BigInteger> stack = new Stack<BigInteger>();
stack.Push(m);
while(stack.Count != 0)
{
m = stack.Pop();
if(m == 0)
n = n + 1;
else if(n == 0)
{
stack.Push(m - 1);
n = 1;
}
else
{
stack.Push(m - 1);
stack.Push(m);
--n;
}
}
return n;
}
Ahora, cuando consideramos el código fuente, ciertamente hemos convertido nuestro método recursivo en uno iterativo.
Teniendo en cuenta para qué se ha compilado esto, hemos convertido el código que utiliza la pila de llamadas para implementar la recursión en un código que no lo hace (y al hacerlo, el código convertido que generará una excepción de desbordamiento de pila para valores incluso muy pequeños en el código eso solo tomará un tiempo extremadamente largo para regresar [ver ¿Cómo puedo evitar que mi función Ackerman se desborde en la pila? para algunas optimizaciones adicionales eso lo hace realmente volver para muchas más entradas posibles]).
Teniendo en cuenta cómo se implementa la recursión en general, hemos convertido el código que usa la pila de llamadas en un código que usa una pila diferente para mantener las operaciones pendientes. Por lo tanto, podríamos argumentar que aún es recursivo, cuando se considera en ese nivel bajo.
Y a ese nivel, de hecho no hay otras formas de evitarlo. Entonces, si consideras que ese método es recursivo, entonces hay cosas que no podemos hacer sin él. En general, aunque no etiquetamos dicho código recursivo. El término recursión es útil porque cubre un cierto conjunto de enfoques y nos da una forma de hablar sobre ellos, y ya no estamos usando uno de ellos.
Por supuesto, todo esto supone que tienes una opción. Hay dos idiomas que prohíben las llamadas recursivas, y los idiomas que carecen de las estructuras de bucle necesarias para la iteración.
La respuesta clásica es "no", pero permítame explicarme por qué creo que "sí" es una mejor respuesta.
Antes de continuar, saquemos algo del camino: desde una computabilidad & punto de vista de complejidad:
Bien, ahora, pongamos un pie en la tierra de práctica, manteniendo el otro pie en la tierra de teoría.
La pila de llamadas es una estructura control , mientras que una pila manual es una estructura data . El control y los datos son no conceptos iguales, pero son equivalentes en el sentido de que pueden reducirse entre sí (o "emulados" a través del otro) desde un punto de vista de computabilidad o complejidad.
¿Cuándo podría importar esta distinción? Cuando trabajas con herramientas del mundo real. Aquí hay un ejemplo:
Supongamos que está implementando N-way mergesort . Es posible que tenga un bucle for que atraviesa cada uno de los segmentos N , invoca mergesort por separado y luego combina los resultados.
¿Cómo puedes paralizar esto con OpenMP?
En el reino recursivo, es extremadamente simple:
solo coloque #pragma omp parallel for alrededor de su bucle que va de 1 a N, y listo.
En el reino iterativo, no puedes hacer esto. Tienes que generar hilos manualmente y pasarles los datos apropiados manualmente para que sepan qué hacer.
Por otro lado, hay otras herramientas (como los vectorizadores automáticos, por ejemplo, #pragma vector ) que funcionan con bucles pero son completamente inútiles con la recursión.
Ser de puntos, solo porque puedes probar que los dos paradigmas son matemáticamente equivalentes, eso no significa que sean iguales en la práctica. Un problema que podría ser trivial automatizar en un paradigma (por ejemplo, paralelización de bucle) podría ser mucho más difícil de resolver en el otro paradigma.
Por consiguiente, si necesita una herramienta para resolver un problema, es probable que la herramienta solo funcione con un tipo de enfoque en particular y, en consecuencia, no podrá resolver el problema con un enfoque diferente, incluso si puede demostrar matemáticamente El problema se puede resolver de cualquier manera.
Dejando a un lado el razonamiento teórico, echemos un vistazo a cómo se ven la recursión y los bucles desde el punto de vista de la máquina (hardware o virtual). La recursión es una combinación de flujo de control que permite iniciar la ejecución de algún código y volver a completarse (en una vista simplista cuando se ignoran las señales y excepciones) y de los datos que se pasan a ese otro código (argumentos) y que se devuelven desde es (resultado). Por lo general, no se trata de una administración de memoria explícita, sin embargo, hay una asignación implícita de la memoria stack para guardar las direcciones de retorno, los argumentos, los resultados y los datos locales intermedios.
Un bucle es una combinación de flujo de control y datos locales. Comparando esto con la recursión, podemos ver que la cantidad de datos en este caso es fija. La única forma de romper esta limitación es usar la memoria dinámica (también conocida como heap ) que se puede asignar (y liberar) cuando sea necesario.
Para resumir:
Suponiendo que la parte control flow sea razonablemente poderosa, la única diferencia está en los tipos de memoria disponibles. Por lo tanto, nos quedan 4 casos (el poder de expresividad se indica entre paréntesis):
Si las reglas del juego son un poco más estrictas y la implementación recursiva no está permitida para usar bucles, obtenemos esto en su lugar:
La diferencia clave con el escenario anterior es que la falta de memoria de la pila no permite la recursión sin que los bucles hagan más pasos durante la ejecución que las líneas de código.
Sí. Hay varias tareas comunes que son fáciles de realizar utilizando la recursión pero imposibles con solo los bucles:
Hay una diferencia entre las funciones recursivas y las funciones recursivas primitivas. Las funciones recursivas primitivas son aquellas que se calculan utilizando bucles, donde la cuenta de iteración máxima de cada bucle se calcula antes de que comience la ejecución del bucle. (Y "recursivo" aquí no tiene nada que ver con el uso de la recursión).
Las funciones recursivas primitivas son estrictamente menos potentes que las funciones recursivas. Obtendría el mismo resultado si tomara funciones que usan recursión, donde la profundidad máxima de la recursión debe calcularse de antemano.
Si está programando en c ++ y usa c ++ 11, entonces hay una cosa que debe hacerse usando recursions: las funciones constexpr. Pero el estándar lo limita a 512, como se explica en esta respuesta . No es posible utilizar bucles en este caso, ya que en ese caso la función no puede ser constexpr, pero esto se modifica en c ++ 14.
Estoy de acuerdo con las otras preguntas. No hay nada que puedas hacer con la recursión que no puedas hacer con un bucle.
PERO , en mi opinión, la recursión puede ser muy peligrosa. Primero, para algunos es más difícil entender lo que realmente está sucediendo en el código. En segundo lugar, al menos para C ++ (Java, no estoy seguro), cada paso de recursión tiene un impacto en la memoria porque cada llamada de método provoca la acumulación de memoria y la inicialización del encabezado de los métodos. De esta manera puedes volar tu pila. Simplemente intente la recursión de los números de Fibonacci con un alto valor de entrada.