¿Es un ciclo while intrínsecamente una recursión?

Me preguntaba si un ciclo while es intrínsecamente una recursión.

Creo que se debe a que un ciclo while puede verse como una función que se llama al final. Si no es recursividad, ¿cuál es la diferencia?

Los bucles son en gran medida no recursivos. De hecho, son el principal ejemplo del mecanismo opuesto : la iteración .

El punto de recurrencia es que un elemento de procesamiento llama a otra instancia de sí mismo. El mecanismo de control de bucle simplemente salta de nuevo al punto donde comenzó.

Saltar alrededor del código y llamar a otro bloque de código son operaciones diferentes. Por ejemplo, cuando saltas al inicio del bucle, la variable de control del bucle todavía tiene el mismo valor que tenía antes del salto. Pero si llama a otra instancia de la rutina en la que se encuentra, entonces la nueva instancia tiene copias nuevas y no relacionadas de todas sus variables. Efectivamente, una variable puede tener un valor en el primer nivel de procesamiento y otro valor en un nivel inferior.

Esta capacidad es crucial para que funcionen muchos algoritmos recursivos, y es por eso que no puede emular la recursión a través de la iteración sin también administrar una pila de cuadros llamados que realiza un seguimiento de todos esos valores.

Decir que X es intrínsecamente Y solo tiene sentido si tiene en mente algún sistema (formal) en el que está expresando X. Si define la semántica de whileen términos del cálculo lambda, puede mencionar la recursividad *; si lo define en términos de una máquina de registro, probablemente no lo hará.

En cualquier caso, la gente probablemente no lo entenderá si llama a una función recursiva solo porque contiene un ciclo while.

* Aunque tal vez solo indirectamente, por ejemplo, si lo define en términos de fold.

Esto depende de tu punto de vista.

Si observa la teoría de la computabilidad , la iteración y la recursividad son igualmente expresivas . Lo que esto significa es que puede escribir una función que calcule algo, y no importa si lo hace de forma recursiva o iterativa, podrá elegir ambos enfoques. No hay nada que pueda calcular de forma recursiva que no pueda calcular de forma iterativa y viceversa (aunque el funcionamiento interno del programa puede ser diferente).

Muchos lenguajes de programación no tratan la recursividad y la iteración de la misma manera, y por una buena razón. Por lo general , la recursión significa que el lenguaje / compilador maneja la pila de llamadas, y la iteración significa que puede que tenga que hacer el manejo de la pila usted mismo.

Sin embargo, hay lenguajes , especialmente lenguajes funcionales, en los que cosas como los bucles (por, mientras) son en realidad solo azúcar sintáctico para la recursión y se implementan detrás de escena de esa manera. Esto a menudo es deseable en lenguajes funcionales, porque de lo contrario no tienen el concepto de bucle, y agregarlo haría su cálculo más complejo, por una pequeña razón práctica.

Entonces no, no son intrínsecamente iguales . Son igualmente expresivos , lo que significa que no puedes calcular algo de forma iterativa que no puedes calcular de forma recursiva y viceversa, pero eso es todo, en el caso general (según la tesis de Church-Turing).

Tenga en cuenta que estamos hablando de programas recursivos aquí. Existen otras formas de recursión, por ejemplo, en estructuras de datos (por ejemplo, árboles).

Si lo miras desde el punto de vista de la implementación , la recursividad y la iteración no son lo mismo. La recursión crea un nuevo marco de pila para cada llamada. Cada paso de la recursión es autónomo, obteniendo los argumentos para el cálculo de la persona que llama (sí mismo).

Los bucles, por otro lado, no crean marcos de llamadas. Para ellos, el contexto no se conserva en cada paso. Para el ciclo, el programa simplemente salta de regreso al inicio del ciclo hasta que la condición del ciclo falla.

Es muy importante saberlo, ya que puede hacer diferencias bastante radicales en el mundo real. Para la recursividad, se debe guardar todo el contexto en cada llamada. Para la iteración, tiene un control preciso sobre qué variables están en la memoria y qué se guarda donde.

Si lo mira de esa manera, verá rápidamente que para la mayoría de los idiomas, la iteración y la recursión son fundamentalmente diferentes y tienen propiedades diferentes. Dependiendo de la situación, algunas de las propiedades son más deseables que otras.

La recursión puede hacer que los programas sean más simples y fáciles de probar y probar . La conversión de una recursión a iteración generalmente hace que el código sea más complejo, lo que aumenta la probabilidad de falla. Por otro lado, la conversión a iteración y la reducción de la cantidad de marcos de la pila de llamadas pueden ahorrar la memoria que tanto se necesita.

La diferencia es la pila implícita y la semántica.

Un ciclo while que "se llama a sí mismo al final" no tiene una pila para rastrear cuando se hace. Su última iteración establece qué estado será cuando termine.

Sin embargo, la recursión no puede hacerse sin esta pila implícita que recuerda el estado del trabajo realizado anteriormente.

Es cierto que puede resolver cualquier problema de recursión con iteración si le da acceso a una pila explícitamente. Pero hacerlo de esa manera no es lo mismo.

La diferencia semántica tiene que ver con el hecho de que mirar el código recursivo transmite una idea de una manera completamente diferente al código iterativo. El código iterativo hace las cosas paso a paso. Acepta cualquier estado que haya venido antes y solo funciona para crear el siguiente estado.

El código recursivo divide un problema en fractales. Esta pequeña parte se parece a esa gran parte, por lo que podemos hacer solo esta parte y esa parte de la misma manera. Es una forma diferente de pensar sobre los problemas. Es muy poderoso y lleva tiempo acostumbrarse. Se puede decir mucho en pocas líneas. Simplemente no puede sacar eso de un ciclo while incluso si tiene acceso a una pila.

Todo depende de su uso intrínseco del término . En el nivel del lenguaje de programación, son sintáctica y semánticamente diferentes, y tienen un rendimiento y uso de memoria bastante diferentes. Pero si profundiza lo suficiente en la teoría, se pueden definir en términos mutuos y, por lo tanto, es "lo mismo" en algún sentido teórico.

La verdadera pregunta es: ¿cuándo tiene sentido distinguir entre iteración (bucles) y recursividad, y cuándo es útil pensar que son las mismas cosas? La respuesta es que cuando realmente se programa (en lugar de escribir pruebas matemáticas) es importante distinguir entre iteración y recursividad.

La recursión crea un nuevo marco de pila, es decir, un nuevo conjunto de variables locales para cada llamada. Esto tiene gastos generales y ocupa espacio en la pila, lo que significa que una recursión lo suficientemente profunda puede desbordar la pila, lo que hace que el programa se bloquee. La iteración, por otro lado, solo modifica las variables existentes, por lo que generalmente es más rápida y solo ocupa una cantidad constante de memoria. ¡Esta es una distinción muy importante para un desarrollador!

En lenguajes con recursividad de cola de llamada (típicamente lenguajes funcionales), el compilador puede optimizar las llamadas recursivas de tal manera que solo ocupen una cantidad constante de memoria. En esos idiomas, la distinción importante no es la iteración frente a la recursión, sino la versión sin recuento de la cola de recursión y la recursión de la cola de cola.

En pocas palabras: debe ser capaz de notar la diferencia, de lo contrario su programa se bloqueará.

whilelos bucles son una forma de recursión, ver, por ejemplo, la respuesta aceptada a esta pregunta . Corresponden al operador μ en la teoría de la computabilidad (ver, por ejemplo, aquí ).

Todas las variaciones de forbucles que iteran en un rango de números, una colección finita, una matriz, etc., corresponden a la recursividad primitiva, ver, por ejemplo, aquí y aquí . Tenga en cuenta que los forbucles de C, C ++, Java, etc., son en realidad azúcar sintáctica para un whilebucle y, por lo tanto, no corresponde a la recursividad primitiva. El forbucle Pascal es un ejemplo de recursividad primitiva.

Una diferencia importante es que la recursividad primitiva siempre termina, mientras que la recursión generalizada ( whilebucles) puede no terminar.

EDITAR

Algunas aclaraciones con respecto a los comentarios y otras respuestas. "La recursión ocurre cuando una cosa se define en términos de sí misma o de su tipo". (ver wikipedia ). Asi que,

¿Es un ciclo while intrínsecamente una recursión?

Ya que puedes definir un whileciclo en términos de sí mismo

while p do c := if p then (c; while p do c))

entonces, sí , un whilebucle es una forma de recursión. Las funciones recursivas son otra forma de recursión (otro ejemplo de definición recursiva). Las listas y los árboles son otras formas de recursión.

Otra pregunta que es implícitamente asumida por muchas respuestas y comentarios es

¿Son equivalentes los bucles while y las funciones recursivas?

La respuesta a esta pregunta es no : un whilebucle corresponde a una función recursiva de cola, donde las variables a las que accede el bucle corresponden a los argumentos de la función recursiva implícita, pero, como otros han señalado, las funciones no recursivas de cola no puede ser modelado por un whilebucle sin usar una pila adicional.

Entonces, el hecho de que "un whilebucle es una forma de recursión" no contradice el hecho de que "algunas funciones recursivas no pueden expresarse mediante un whilebucle".

Una llamada de cola (o llamada recursiva de cola) se implementa exactamente como un "goto con argumentos" (sin presionar ningún marco de llamada adicional en la pila de llamadas ) y en algunos lenguajes funcionales (especialmente Ocaml) es la forma habitual de bucle.

Por lo tanto, un ciclo while (en idiomas que los tienen) puede verse como que termina con una llamada de cola a su cuerpo (o su prueba de cabeza).

Del mismo modo, las llamadas recursivas ordinarias (sin cola) se pueden simular mediante bucles (utilizando alguna pila).

Lea también sobre las continuaciones y el estilo de paso de continuación .

Entonces "recursión" e "iteración" son profundamente equivalentes.

Es cierto que tanto los bucles while recursivos como los ilimitados son equivalentes en términos de expresividad computacional. Es decir, cualquier programa escrito recursivamente puede reescribirse en un programa equivalente utilizando bucles en su lugar, y viceversa. Ambos enfoques son completos , es decir, se pueden usar para calcular cualquier función computable.

La diferencia fundamental en términos de programación es que la recursividad le permite hacer uso de los datos que se almacenan en la pila de llamadas. Para ilustrar esto, suponga que desea imprimir elementos de una lista enlazada individualmente utilizando un bucle o una recursión. Usaré C para el código de ejemplo:

 typedef struct List List;
 struct List
 {
     List* next;
     int element;
 };

 void print_list_loop(List* l)
 {
     List* it = l;
     while(it != NULL)
     {
          printf("Element: %d\n", it->element);
          it = it->next;
     }
 }

 void print_list_rec(List* l)
 {
      if(l == NULL) return;
      printf("Element: %d\n", l->element);
      print_list_rec(l->next);
 }

Simple, verdad? Ahora hagamos una pequeña modificación: imprima la lista en el orden inverso.

Para la variante recursiva, esta es una modificación casi trivial a la función original:

void print_list_reverse_rec(List* l)
{
    if (l == NULL) return;
    print_list_reverse_rec(l->next);
    printf("Element: %d\n", l->element);
}

Sin embargo, para la función de bucle, tenemos un problema. Nuestra lista está vinculada individualmente y, por lo tanto, solo se puede recorrer hacia adelante. Pero como estamos imprimiendo al revés, tenemos que comenzar a imprimir el último elemento. Una vez que llegamos al último elemento, ya no podemos volver al penúltimo elemento.

Por lo tanto, tenemos que realizar una gran cantidad de recorridos de regreso, o tenemos que construir una estructura de datos auxiliar que haga un seguimiento de los elementos visitados y desde la cual podamos imprimir de manera eficiente.

¿Por qué no tenemos este problema con la recursividad? Porque en la recursión ya tenemos una estructura de datos auxiliar: la pila de llamadas de función.

Dado que la recursividad nos permite volver a la invocación previa de la llamada recursiva, con todas las variables locales y el estado de esa llamada aún intactos, ganamos cierta flexibilidad que sería tedioso modelar en el caso iterativo.

Los bucles son una forma especial de recursión para lograr una tarea específica (principalmente iteración). Se puede implementar un bucle en un estilo recursivo con el mismo rendimiento [1] en varios idiomas. y en el SICP [2], puede ver que los bucles se describen como "azúcar fantástico". En la mayoría de los lenguajes de programación imperativos, los bloques for y while utilizan el mismo alcance que su función principal. Sin embargo, en la mayoría de los lenguajes de programación funcionales no existen ni bucles for ni while porque no hay necesidad de ellos.

La razón por la que los lenguajes imperativos tienen bucles for / while es que están manejando estados al mutarlos. Pero en realidad, si observa desde una perspectiva diferente, si piensa en un bloque while como una función en sí misma, tomar un parámetro, procesarlo y devolver un nuevo estado, que también podría ser la llamada de la misma función con diferentes parámetros, usted Puede pensar en el bucle como una recursión.

El mundo también podría definirse como mutable o inmutable. si definimos el mundo como un conjunto de reglas, y llamamos a una función final que toma todas las reglas, y el estado actual como parámetros, y devuelve el nuevo estado de acuerdo con estos parámetros que tiene la misma funcionalidad (generar el siguiente estado en el mismo manera), también podríamos decir que es una recursión y un bucle.

en el siguiente ejemplo, la vida es la función que toma dos parámetros "reglas" y "estado", y se construirá un nuevo estado en la próxima marca de tiempo.

life rules state = life rules new_state
    where new_state = construct_state_in_time rules state

[1]: la optimización de llamadas de cola es una optimización común en lenguajes de programación funcionales para usar la pila de funciones existente en llamadas recursivas en lugar de crear una nueva.

[2]: Estructura e interpretación de programas de computadora, MIT. https://mitpress.mit.edu/books/structure-and-interpretation-computer-programs

Un ciclo while es diferente de la recursividad.

Cuando se llama a una función, ocurre lo siguiente:

1. Se agrega un marco de pila a la pila.

2. El puntero de código se mueve al comienzo de la función.

Cuando un ciclo while está al final, ocurre lo siguiente:

1. Una condición pregunta si algo es cierto.

2. Si es así, el código salta a un punto.

En general, el ciclo while es similar al siguiente pseudocódigo:

 if (x)

 {

      Jump_to(y);

 }

Lo más importante de todo es que la recursividad y los bucles tienen diferentes representaciones de código de ensamblaje y representaciones de código de máquina. Esto significa que no son lo mismo. Pueden tener los mismos resultados, pero el código de máquina diferente demuestra que no son 100% lo mismo.

Solo la iteración es insuficiente para ser generalmente equivalente a la recursión, pero la iteración con una pila es generalmente equivalente. Cualquier función recursiva puede reprogramarse como un bucle iterativo con una pila, y viceversa. Sin embargo, esto no significa que sea práctico, y en cualquier situación particular, una u otra forma puede tener claros beneficios sobre la otra versión.

No estoy seguro de por qué esto es controvertido. La recursión y la iteración con una pila son el mismo proceso computacional. Son el mismo "fenómeno", por así decirlo.

Lo único en lo que puedo pensar es que cuando los veo como "herramientas de programación", estoy de acuerdo en que no debes pensar en ellos como lo mismo. Son equivalentes "matemáticamente" o "computacionalmente" (nuevamente iteración con una pila , no iteración en general), pero eso no significa que deba abordar los problemas con la idea de que cualquiera de los dos lo hará. Desde el punto de vista de la implementación / resolución de problemas, algunos problemas pueden funcionar mejor de una forma u otra, y su trabajo como programador es decidir correctamente cuál es el más adecuado.

Para aclarar, la respuesta a la pregunta ¿Es un ciclo while intrínsecamente una recursión? es un no definitivo , o al menos "no, a menos que tenga una pila también".