¿Hay algo que se pueda hacer con recursión que no se pueda hacer con bucles?

126

Hay momentos en que usar la recursión es mejor que usar un bucle, y momentos en los que usar un bucle es mejor que usar la recursión. Elegir el "correcto" puede ahorrar recursos y / o generar menos líneas de código.

¿Hay casos en los que una tarea solo se puede hacer usando recursividad, en lugar de un bucle?

Pikamander2
fuente
13
Lo dudo seriamente. La recursión es un bucle glorificado.
Carreras de ligereza en órbita
66
Al ver las direcciones divergentes en las que van las respuestas (y después de haberme fallado a la hora de proporcionar una mejor), puede hacer que cualquiera intente responder un favor si proporciona un poco más de antecedentes y qué tipo de respuesta está buscando. ¿Desea una prueba teórica para máquinas hipotéticas (con almacenamiento y tiempo de ejecución ilimitados)? ¿O ejemplos prácticos? (Donde "sería ridículamente complicado" podría calificar como "no se puede hacer"). ¿O algo diferente?
5gon12eder
8
@LightnessRacesinOrbit Para mi oído no nativo de habla inglesa, "La recursión es un bucle glorificado" suena a lo que te refieres: "También podrías usar una construcción de bucle en lugar de una llamada recursiva en cualquier lugar, y el concepto realmente no merece su propio nombre" . Quizás interprete mal el modismo de "algo glorificado", entonces.
hyde
13
¿Qué pasa con la función de Ackermann? en.wikipedia.org/wiki/Ackermann_function , no particularmente útil pero imposible de hacer a través de bucles. (También puede consultar este video youtube.com/watch?v=i7sm9dzFtEI por Computerphile)
WizardOfMenlo
8
@WizardOfMenlo, el código de inicio es una implementación de la solución ERRE (que también es una solución interactiva ... con una pila). Un enfoque iterativo con una pila puede emular una llamada recursiva. En cualquier programación que sea adecuadamente poderosa, una construcción en bucle se puede usar para emular a otra. La máquina registradora con las instrucciones INC (r), JZDEC (r, z)puede implementar una máquina de Turing. No tiene 'recursividad', eso es un salto si cero más DECremento. Si la función de Ackermann es computable (lo es), esa máquina de registro puede hacerlo.

Respuestas:

164

Si y no. En última instancia, no hay nada que la recursión pueda calcular que el bucle no pueda, pero el bucle requiere mucha más fontanería. Por lo tanto, lo único que puede hacer la recursión que los bucles no pueden hacer es que algunas tareas sean muy fáciles.

Toma caminando un árbol. Caminar por un árbol con recursión es una estupidez fácil. Es lo más natural del mundo. Caminar un árbol con bucles es mucho menos sencillo. Debe mantener una pila u otra estructura de datos para realizar un seguimiento de lo que ha hecho.

A menudo, la solución recursiva a un problema es más bonita. Ese es un término técnico, y es importante.

Roger escaso
fuente
120
Básicamente, hacer bucles en lugar de recurrencia significa manejar manualmente la pila.
Silviu Burcea
15
... la pila (s) . La siguiente situación puede preferir tener más de una pila. Considere una función recursiva Aque encuentra algo en un árbol. Cada Avez que encuentra esa cosa, lanza otra función recursiva Bque encuentra una cosa relacionada en el subárbol en la posición donde fue lanzada A. Una vez que Bfinaliza la recursión, regresa Ay la última continúa su propia recursión. Uno puede declarar una pila para Ay una para B, o poner la Bpila dentro del Abucle. Si uno insiste en usar una sola pila, las cosas se ponen realmente complicadas.
rwong
35
Therefore, the one thing recursion can do that loops can't is make some tasks super easy. Y lo único que pueden hacer los bucles que la recursividad no puede hacer es que algunas tareas sean súper fáciles. ¿Has visto las cosas feas e poco intuitivas que tienes que hacer para transformar la mayoría de los problemas naturalmente iterativos de una recursión ingenua a una recursiva de cola para que no exploten?
Mason Wheeler
10
@MasonWheeler El 99% del tiempo, esas "cosas" pueden encapsularse mejor dentro de un operador de recursión como mapo fold(de hecho, si elige considerarlas primitivas, creo que puede usar fold/ unfoldcomo una tercera alternativa a los bucles o recursividad). A menos que esté escribiendo código de biblioteca, no hay tantos casos en los que deba preocuparse por la implementación de la iteración, en lugar de la tarea que se supone que debe realizar; en la práctica, eso significa que los bucles explícitos y la recursividad explícita son igualmente pobres abstracciones que deben evitarse en el nivel superior.
Leushenko
77
Puede comparar dos cadenas comparando recursivamente las subcadenas, pero solo comparando cada carácter, uno por uno, hasta que obtenga una falta de coincidencia, es probable que funcione mejor y sea más claro para el lector.
Steven Burnap
78

No.

Manos a los mismos fundamentos de los mínimos necesarios con el fin de calcular, sólo tiene que ser capaz de bucle (esto por sí solo no es suficiente, sino que es un componente necesario). No importa cómo .

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 "eso realmente funciona"? La integridad de Turing es la de FRACTRAN , que es completa de Turing . 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 recursividad. Por lo tanto, no hay nada que la recursividad pueda brindarle en términos de computabilidad que un bucle simple no pueda.

Esto realmente se reduce a unos pocos puntos:

  • Cualquier cosa que sea computable es computable en una máquina Turing
  • Cualquier lenguaje que pueda implementar una máquina de Turing (llamado Turing completo) puede calcular cualquier cosa que cualquier otro idioma pueda
  • Dado que hay máquinas de Turing en idiomas que carecen de recursividad (y hay otras que solo tienen recursividad cuando ingresas a algunos de los otros esolangs), es necesariamente cierto que no hay nada que puedas hacer con la recursión que no puedas hacer con un loop (y nada que puedas hacer con un loop que no puedas hacer con recursión).

Esto no quiere decir que hay algunas clases de problemas que pueden pensarse más fácilmente con recursión en lugar de con bucle, o con bucle en lugar de con recursión. Sin embargo, estas herramientas también son igualmente poderosas.

Y aunque llevé esto al extremo de 'esolang' (principalmente porque puedes encontrar cosas que están completadas e implementadas de manera bastante extraña), esto no significa que los esolangs sean de ninguna manera opcionales. Hay una lista completa de cosas que se completan accidentalmente, incluidas las plantillas Magic the Gathering, Sendmail, MediaWiki y el sistema de tipo Scala. Muchos de estos están lejos de ser óptimos cuando se trata de hacer algo práctico, es solo que puedes calcular cualquier cosa que sea computable usando estas herramientas.


Esta equivalencia puede ser particularmente interesante cuando ingresas 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 reescribirá como un bucle; no se utilizará ninguna pila. Dichos enfoques suelen ser más elegantes y fáciles de entender que el bucle equivalente que se está escribiendo, pero nuevamente, para cada llamada recursiva puede haber un bucle equivalente escrito y para cada bucle puede haber una llamada recursiva escrita.

También hay momentos en los que la conversión del bucle simple en una llamada recursiva puede ser complicada y más difícil de entender.


Si desea entrar en el lado de la teoría, vea la tesis de Church Turing . También puede encontrar útil la tesis de la iglesia-turing en CS.SE.

Comunidad
fuente
29
La integridad de Turing se arroja demasiado como importa. Muchas cosas son Turing Complete ( como Magic the Gathering ), pero eso no significa que sea lo mismo que algo más que Turing Complete. Al menos no a un nivel que importe. No quiero caminar un árbol con Magic the Gathering.
Escaso Roger
77
Una vez que puede reducir un problema a "esto tiene el mismo poder que una máquina de Turing", es suficiente para llegar allí. Las máquinas de Turing son un obstáculo bastante bajo, pero es todo lo que se necesita. No hay nada que un bucle pueda hacer que la recursión no pueda hacer, ni viceversa.
44
La afirmación hecha en esta respuesta es, por supuesto, correcta, pero me atrevo a decir que el argumento no es realmente convincente. Las máquinas de Turing no tienen un concepto directo de recursión, por lo que decir "puedes simular una máquina de Turing sin recursión" realmente no prueba nada. Lo que tendría que mostrar para probar la afirmación es que las máquinas de Turing pueden simular la recursividad. Si no muestra esto, debe suponer fielmente que la hipótesis de Church-Turing también es válida para la recurrencia (lo que hace), pero el OP lo cuestionó.
5gon12eder
10
La pregunta del OP es "puede", no "mejor", o "más eficientemente" o algún otro calificador. "Turing completo" significa que todo lo que se puede hacer con recursión también se puede hacer con un bucle. Si esa es la mejor manera de hacerlo en cualquier implementación de lenguaje en particular es una pregunta completamente diferente.
Steven Burnap
77
"Can" no es lo mismo que "best". Cuando confundes "no mejor" con "no puedo", te paralizas porque no importa de qué manera hagas algo, casi siempre hay una mejor manera.
Steven Burnap
31

¿Hay casos en los que una tarea solo se puede hacer usando recursividad, en lugar de un bucle?

Siempre puede convertir el algoritmo recursivo en un bucle, que utiliza 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, proceder con el algoritmo, luego restaurando el estado. Entonces la respuesta corta es: No, no hay tales casos .

Sin embargo, se puede hacer un argumento para "sí". Tomemos un ejemplo concreto y fácil: ordenar por fusión. Debe dividir los datos en dos partes, combinar las partes y luego combinarlas. Incluso si no realiza una llamada a la función del lenguaje de programación real para fusionar la ordenación con el fin de fusionar la ordenación en las partes, debe implementar una funcionalidad que sea idéntica a hacer una llamada a la función (empuje el estado a su propia pila, salte a inicio del ciclo con diferentes parámetros de inicio, luego saque el estado de su pila).

¿Es recursiva, si implementa la recursividad, llame usted mismo, como pasos separados de "estado de empuje" y "salto al principio" y "estado emergente"? Y la respuesta a eso es: No, todavía no se llama recursividad, se llama iteración con pila explícita (si desea utilizar la terminología establecida).


Tenga en cuenta que esto también depende de la definición de "tarea". Si la tarea es ordenar, 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 ordenar por fusión, entonces se aplica la ambigüedad anterior.

Entonces, consideremos la pregunta, ¿hay tareas generales, para las cuales solo hay algoritmos de recursión? Del comentario de @WizardOfMenlo bajo la pregunta, la función de Ackermann es un ejemplo simple de eso. Por lo tanto, el concepto de recursión es independiente, incluso si se puede implementar con una construcción de programa de computadora diferente (iteración con pila explícita).

Hyde
fuente
2
Cuando se trata de un ensamblaje para un procesador sin pila, estas dos técnicas de repente se convierten en una.
Joshua
@Joshua De hecho! Es una cuestión de nivel de abstracción. Si vas un nivel o dos más abajo, son solo puertas lógicas.
hyde
2
Eso no es del todo correcto. Para emular la recursividad con la iteración, necesita una pila donde sea posible el acceso aleatorio. Una sola pila sin acceso aleatorio más una cantidad finita de memoria directamente accesible sería un PDA, que no está completo de Turing.
Gilles
@Gilles Publicación anterior, pero ¿por qué se necesita una pila de acceso aleatorio? Además, ¿no son todas las computadoras reales incluso menos que las PDA, ya que solo tienen una cantidad finita de memoria directamente accesible y no tienen ninguna pila (excepto al usar esa memoria)? Esto no parece una abstracción muy práctica, si dice "no podemos hacer recursión en la realidad".
Hyde
20

Depende de cuán estrictamente defina "recursividad".

Si estrictamente requerimos que involucre la pila de llamadas (o cualquier mecanismo para mantener el estado del programa que se use), entonces siempre podemos reemplazarlo por algo que no lo haga. De hecho, los lenguajes que conducen naturalmente al uso intensivo de la recursividad tienden a tener compiladores que hacen un uso intensivo de la optimización de las llamadas 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 que la primera llamada recursiva sea 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 quitar el gotopara alejar a los velociraptores 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, hemos convertido el código que usa 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 arrojará una excepción de desbordamiento de la pila incluso para valores bastante pequeños en el código que simplemente tomar un tiempo insoportablemente largo para regresar [consulte ¿Cómo puedo evitar que mi función Ackerman desborde la pila? para obtener más optimizaciones que hacen que realmente regrese para muchas más entradas posibles]).

Teniendo en cuenta cómo se implementa generalmente la recursividad, hemos convertido el código que usa la pila de llamadas en código que usa una pila diferente para contener las operaciones pendientes. Por lo tanto, podríamos argumentar que todavía es recursivo, cuando se considera en ese nivel bajo.

Y a ese nivel, de hecho no hay otras formas de evitarlo. Entonces, si considera que ese método es recursivo, entonces hay cosas que no podemos hacer sin él. Generalmente, aunque no etiquetamos dicho código de forma recursiva. El término recursividad es útil porque cubre un cierto conjunto de enfoques y nos da una manera 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 iterar.

Jon Hanna
fuente
Solo es posible reemplazar la pila de llamadas con algo equivalente si la pila de llamadas está acotada o si uno tiene acceso a una memoria no acotada fuera de la pila de llamadas. Hay una clase significativa de problemas que pueden resolverse mediante autómatas de inserción que tienen una pila de llamadas ilimitada pero de lo contrario solo pueden tener un número finito de estados.
supercat
Esta es la mejor respuesta, quizás la única respuesta correcta. Incluso el segundo ejemplo sigue siendo recursivo, y en este nivel, la respuesta a la pregunta original es no . Con una definición más amplia de recursión, la recursividad para la función de Ackermann es imposible de evitar.
gerrit
@gerrit y con un más estrecho, lo evita. En última instancia, se reduce a los bordes de lo que hacemos o no aplicamos esta etiqueta útil que utilizamos para cierto código.
Jon Hanna
1
Se unió al sitio para votar esto. La función de Ackermann / es / recursiva en la naturaleza. Implementar una estructura recursiva con un bucle y una pila no lo convierte en una solución iterativa, solo ha movido la recursividad al espacio de usuario.
Aaron McMillin
9

La respuesta clásica es "no", pero permítanme explicar por qué creo que "sí" es una mejor respuesta.


Antes de continuar, eliminemos algo: desde el punto de vista de la computabilidad y la complejidad:

  • La respuesta es "no" si se le permite tener una pila auxiliar durante el bucle.
  • La respuesta es "sí" si no se le permite ningún dato adicional durante el bucle.

Bien, ahora, pongamos un pie en tierra de práctica, manteniendo el otro pie en tierra de teoría.


La pila de llamadas es una estructura de control , mientras que una pila manual es una estructura de datos . El control y los datos no son conceptos iguales, pero son equivalentes en el sentido de que pueden reducirse entre sí (o "emularse" entre sí) desde el punto de vista de la computabilidad o la complejidad.

¿Cuándo podría importar esta distinción? Cuando trabajas con herramientas del mundo real. Aquí hay un ejemplo:

Digamos que estás implementando N-way mergesort. Es posible que tenga un forbucle que atraviesa cada uno de los Nsegmentos, los llama mergesortpor separado y luego combina los resultados.

¿Cómo podría paralelizar esto con OpenMP?

En el ámbito recursivo, es muy sencillo: sólo hay que poner #pragma omp parallel foralrededor de su bucle que va de 1 a N, y ya está. En el reino iterativo, no puedes hacer esto. Debe 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 recursividad.

El punto es que solo porque puede 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 para automatizar en un paradigma (por ejemplo, la paralelización de bucles) podría ser mucho más difícil de resolver en el otro paradigma.

es decir: las herramientas para un paradigma no se traducen automáticamente a otros paradigmas.

En consecuencia, si necesita una herramienta para resolver un problema, es probable que la herramienta solo funcione con un tipo particular de enfoque y, en consecuencia, no podrá resolver el problema con un enfoque diferente, incluso si puede demostrar matemáticamente que el problema puede ser resuelto de cualquier manera.

Mehrdad
fuente
Incluso más allá de eso, tenga en cuenta que el conjunto de problemas que se pueden resolver con un autómata pushdown es mayor que el conjunto que se puede resolver con un autómata finito (ya sea determinista o no) pero más pequeño que el conjunto que se puede resolver con un Máquina de Turing.
supercat
8

Dejando a un lado el razonamiento teórico, echemos un vistazo a cómo se ven la recursividad 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 regresar al finalizar (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 de es (resultado) Por lo general, no se trata de una gestión explícita de la memoria; sin embargo, existe una asignación implícita de la memoria de la pila para guardar direcciones de retorno, argumentos, resultados y 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 memoria dinámica (también conocida como montón ) que se puede asignar (y liberar) cuando sea necesario.

Para resumir:

  • Caso de recursión = flujo de control + apilamiento (+ montón)
  • Caso de bucle = flujo de control + montón

Suponiendo que la parte de flujo de control es razonablemente potente, la única diferencia está en los tipos de memoria disponibles. Entonces, nos quedan 4 casos (el poder de expresividad aparece entre paréntesis):

  1. Sin pila, sin montón: la recursividad y las estructuras dinámicas son imposibles. (recursividad = bucle)
  2. Pila, sin montón: la recursión está bien, las estructuras dinámicas son imposibles. (recursividad> bucle)
  3. Sin pila, montón: la recursión es imposible, las estructuras dinámicas están bien. (recursividad = bucle)
  4. Pila, montón: la recursividad y las estructuras dinámicas están bien. (recursividad = bucle)

Si las reglas del juego son un poco más estrictas y no se permite la implementación recursiva para usar bucles, obtenemos esto en su lugar:

  1. Sin pila, sin montón: la recursividad y las estructuras dinámicas son imposibles. (recursividad <loop)
  2. Pila, sin montón: la recursión está bien, las estructuras dinámicas son imposibles. (recursividad> bucle)
  3. Sin pila, montón: la recursión es imposible, las estructuras dinámicas están bien. (recursividad <loop)
  4. Pila, montón: la recursividad y las estructuras dinámicas están bien. (recursividad = bucle)

La diferencia clave con el escenario anterior es que la falta de memoria de pila no permite la recursividad sin bucles para realizar más pasos durante la ejecución que las líneas de código.

Alexander Kogtenkov
fuente
2

Si. Hay varias tareas comunes que son fáciles de realizar utilizando la recursión pero imposibles con solo bucles:

  • Causando desbordamientos de pila.
  • Programadores principiantes totalmente confusos.
  • Crear funciones de aspecto rápido que en realidad son O (n ^ n).
jpa
fuente
3
Por favor, estos son realmente fáciles con bucles, los veo todo el tiempo. Diablos, con un poco de esfuerzo ni siquiera necesitas los bucles. Incluso si la recursividad es más fácil.
AviD
1
en realidad, A (0, n) = n + 1; A (m, 0) = A (m-1,1) si m> 0; A (m, n) = A (m-1, A (m, n-1)) si m> 0, n> 0 crece incluso un poco más rápido que O (n ^ n) (para m = n) :)
John Donn
1
@ JohnDonn Más que un poco, es super exponencial. para n = 3 n ^ n ^ n para n = 4 n ^ n ^ n ^ n ^ n y así sucesivamente. n al n poder n veces.
Aaron McMillin
1

Hay una diferencia entre las funciones recursivas y las funciones recursivas primitivas. Las funciones recursivas primitivas son aquellas que se calculan utilizando bucles, donde el recuento máximo de iteraciones 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 recursividad).

Las funciones recursivas primitivas son estrictamente menos potentes que las funciones recursivas. Obtendría el mismo resultado si tomara funciones que utilizan la recursividad, donde la profundidad máxima de la recursión debe calcularse de antemano.

gnasher729
fuente
3
No estoy seguro de cómo se aplica esto a la pregunta anterior. ¿Puedes por favor aclarar esa conexión?
Yakk
1
Reemplazar el impreciso "bucle" con la distinción importante entre "bucle con recuento de iteraciones limitado" y "bucle con recuento de iteraciones ilimitado", que pensé que todos sabrían de CS 101.
gnasher729
claro, pero aún no se aplica a la pregunta. La pregunta es sobre bucles y recursividad, no recursividad primitiva y recursividad. Imagínese si alguien pregunta sobre las diferencias de C / C ++, y usted responde sobre la diferencia entre K&R C y Ansi C. Seguro que eso hace las cosas más precisas, pero no responde la pregunta.
Yakk
1

Si está programando en c ++ y usa c ++ 11, entonces hay una cosa que debe hacerse usando recursiones: las funciones constexpr. Pero el estándar limita esto a 512, como se explica en esta respuesta . El uso de bucles en este caso no es posible, ya que en ese caso la función no puede ser constexpr, pero esto se cambia en c ++ 14.

BЈовић
fuente
0
  • Si la llamada recursiva es la primera o la última declaración (excluyendo la comprobación de condición) de una función recursiva, es bastante fácil traducirla a una estructura de bucle.
  • Pero si la función hace otras cosas antes y después de la llamada recursiva , sería engorroso convertirla en bucles.
  • Si la función tiene múltiples llamadas recursivas, la conversión a código que usa solo bucles será prácticamente imposible. Se necesitará una pila para mantenerse al día con los datos. En la recursividad, la pila de llamadas en sí funcionará como la pila de datos.
Gulshan
fuente
Tree walking tiene múltiples llamadas recursivas (una para cada niño), pero se transforma trivialmente en un bucle utilizando una pila explícita. Los analizadores, por otro lado, a menudo son molestos de transformar.
CodesInChaos
@CodesInChaos Editado.
Gulshan
-6

Estoy de acuerdo con las otras preguntas. No hay nada que pueda hacer con la recursividad que no pueda 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 al 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 recursividad de los números de Fibonacci con un valor de entrada alto.

Ben1980
fuente
2
Una implementación recursiva ingenua de números de Fibonacci con recursión se ejecutará "fuera de tiempo" antes de que se quede sin espacio de pila. Supongo que hay otros problemas que son mejores para este ejemplo. Además, para muchos problemas, una versión de bucle tiene el mismo impacto en la memoria que una recursiva, solo en el montón en lugar de la pila (si su lenguaje de programación los distingue).
Paŭlo Ebermann
66
El bucle también puede ser "muy peligroso" si simplemente olvida incrementar la variable del bucle ...
h22
2
Entonces, de hecho, producir deliberadamente un desbordamiento de pila es una tarea que se vuelve muy complicada sin usar la recursividad.
5gon12eder
@ 5gon12eder que nos lleva a ¿Qué métodos existen para evitar un desbordamiento de pila en un algoritmo recursivo? - escribir para involucrar TCO, o Memoisation puede ser útil. Los enfoques iterativos versus recursivos también son interesantes, ya que tratan con dos enfoques recursivos diferentes para Fibonacci.
1
La mayoría de las veces, si obtiene un desbordamiento de pila en la recursividad, habría tenido un bloqueo en la versión iterativa. Al menos los primeros lanzamientos con un rastro de pila.
Jon Hanna