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

123

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?

    
pregunta Pikamander2 22.11.2015 - 05:45
fuente

11 respuestas

162

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.

    
respondido por el Scant Roger 22.11.2015 - 07:00
fuente
76

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:

  • Cualquier cosa que sea computable es computable en una máquina de Turing
  • Cualquier idioma que pueda implementar una máquina de Turing (llamada Turing completa) puede computar cualquier cosa que cualquier otro idioma pueda
  • Ya que hay máquinas de Turing en idiomas que carecen de recursión (y hay otras que solo tienen recursión cuando te metes en algunos de los otros esolangs), es necesariamente cierto que no hay nada que se puede hacer con la recursión que no se puede hacer con un bucle (y nada se puede hacer con un bucle que no se puede hacer con la recursión).

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.

    
respondido por el user40980 22.11.2015 - 06:11
fuente
30
  

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

    
respondido por el hyde 22.11.2015 - 14:23
fuente
20

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.

    
respondido por el Jon Hanna 23.11.2015 - 14:13
fuente
9

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:

  • La respuesta es "no" si se le permite tener una pila auxiliar cuando se realiza un bucle.
  • La respuesta es "sí" si no se le permite ningún dato adicional al realizar un bucle.

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.

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

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.

    
respondido por el Mehrdad 24.11.2015 - 12:05
fuente
8

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:

  • Caso de recursión = Flujo de control + Pila (+ Montón)
  • Caso de bucle = Flujo de control + Montón

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

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

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:

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

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.

    
respondido por el Alexander Kogtenkov 22.11.2015 - 11:53
fuente
2

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

  • Causando desbordamientos de pila.
  • Programadores principiantes totalmente confusos.
  • Creando funciones de apariencia rápida que en realidad son O (n ^ n).
respondido por el jpa 24.11.2015 - 07:09
fuente
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 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.

    
respondido por el gnasher729 22.11.2015 - 14:47
fuente
1

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.

    
respondido por el BЈовић 25.11.2015 - 11:28
fuente
0
  • Si la llamada recursiva es la primera o la última declaración (excluyendo la verificación de condición) de una función recursiva, es bastante fácil de traducir en 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 utiliza solo bucles será prácticamente imposible. Se necesitará algo de pila para mantenerse al día con los datos. En la recursión, la propia pila de llamadas funcionará como la pila de datos.
respondido por el Gulshan 27.11.2015 - 07:37
fuente
-6

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.

    
respondido por el Ben1980 22.11.2015 - 10:42
fuente

Lea otras preguntas en las etiquetas