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

37

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?

adios
fuente
13
Puede convertir la recursión a iteración y viceversa, sí. Eso no significa que sean iguales, solo tienen las mismas capacidades. Hay momentos en que la recursividad es más natural y hay momentos en que la iteración es más natural.
Polygnome
18
@MooingDuck Puede probar por inducción que cualquier recursión puede escribirse como iteración y viceversa. Sí, se verá muy diferente, pero igual puedes hacerlo.
Polygnome
66
¿Qué significa intrínsecamente igual aquí? En la programación, el uso de la recursión significa algo específico, que es diferente de la iteración (bucles). En CS, cuando te acercas al lado matemático teórico de las cosas, estas cosas comienzan a significar cosas un poco diferentes.
hyde
3
@MooingDuck La conversión de recursiva a iterativa es bastante trivial. Solo tiene una pila de parámetros de llamadas a funciones y una pila de resultados para las llamadas a funciones. Reemplaza las llamadas recursivas agregando los parámetros a la pila de llamadas. Seguro que hay todo el manejo de la pila que rompe un poco la estructura del algoritmo, pero una vez que entiendes esto, es bastante fácil ver que el código hace lo mismo. Básicamente, está escribiendo explícitamente la pila de llamadas que está implícita en las definiciones recursivas.
Bakuriu

Respuestas:

116

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.

Kilian Foth
fuente
10
@Giorgio Eso puede ser cierto, pero es un comentario sobre un reclamo que la respuesta no hizo. "Arbitrariamente" no está presente en esta respuesta y cambiaría significativamente el significado.
hvd
12
@hvd En principio, la recursión de cola es una recursión completa como cualquier otra. Los compiladores inteligentes pueden optimizar la parte real de "crear un nuevo marco de pila" para que el código generado sea muy similar a un bucle, pero los conceptos de los que estamos hablando se aplican al nivel del código fuente. Considero que la forma que tiene un algoritmo como código fuente es lo importante, por lo que todavía lo llamaría recursividad
Kilian Foth el
15
@Giorgio "esto es exactamente lo que hace la recursividad: llamarse a sí mismo con nuevos argumentos", excepto la llamada. Y los argumentos.
hobbs
12
@Giorgio Estás utilizando diferentes definiciones de palabras que la mayoría aquí. Las palabras, ya sabes, son la base de la comunicación. Esto es Programadores, no CS Stack Exchange. Si utilizamos palabras como "argumento", "llamada", "función", etc., de la manera que usted sugiere, sería imposible discutir sobre el código real.
hyde
66
@Giorgio Estoy mirando el concepto abstracto. Existe el concepto donde repites y el concepto donde repites. Son conceptos diferentes . Hobbs es 100% correcto porque no hay argumentos y no hay llamada. Son fundamental y abstractamente diferentes. Y eso es bueno porque resuelven diferentes problemas. Usted, por otro lado, está analizando cómo podría implementar bucles cuando su única herramienta es la recursividad. Irónicamente, le está diciendo a Hobbs que deje de pensar en la implementación y comience a buscar conceptos cuando su metodología es la que realmente necesita la reevaluación.
corsiKa
37

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.

Anton Golov
fuente
44
Para ser justos, la función no es recursiva en ninguna definición. Solo contiene un elemento recursivo, el bucle.
Luaan
@Luaan: Definitivamente, pero dado que en los idiomas con una whileconstrucción, la recursividad es generalmente una propiedad de las funciones, simplemente no puedo pensar en otra cosa para describir como "recursiva" en este contexto.
Anton Golov
36

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.

Poligoma
fuente
Un lenguaje con variables locales y recursividad pero sin matrices podría realizar tareas que no podrían ser realizadas por un lenguaje iterativo con variables locales y sin matrices. Por ejemplo, informe si una entrada contiene una cadena alfanumérica de longitud desconocida seguida de un espacio en blanco y luego los caracteres de la cadena original en orden inverso.
supercat
3
Mientras el lenguaje esté completo, puede hacerlo. Una matriz se puede reemplazar fácilmente por una lista (doble) vinculada, por ejemplo. Hablar de iteración o recursividad y si son iguales solo tiene sentido si se comparan dos idiomas completos.
Polygnome
Me refería a no tener nada más que variables estáticas o automáticas simples, es decir, no estar completo de Turing. Un lenguaje puramente iterativo se limitaría a aquellas tareas que pueden llevarse a cabo mediante un simple autómata finito determinista, mientras que un lenguaje recursivo agregaría la capacidad de realizar tareas que requerirían al menos un autómata finito determinista pushdown.
supercat
1
Si el lenguaje no está completo, para empezar no tiene sentido. Los DFA no pueden hacer iteraciones arbitrarias ni recursiones por cierto.
Polygnome
2
En realidad, ninguna implementación es completa de Turing, y los lenguajes que no son completos de Turing pueden ser útiles para muchos propósitos. Cualquier programa que pueda ejecutarse con un número finito de variables con un rango finito puede ser acomodado por un DFA donde cada combinación posible de valores es un estado discreto.
supercat
12

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.

naranja confitada
fuente
55
Creo que "stack implícito" es engañoso. La recursión es parte de la semántica de un lenguaje, no un detalle de implementación. (Por supuesto, la mayoría de los idiomas compatibles con recursividad usan una pila de llamadas; pero en primer lugar, algunos de esos idiomas no lo hacen, y en segundo lugar, incluso en los idiomas que sí lo hacen, no todas las llamadas recursivas necesariamente se agregan a la pila de llamadas, ya que muchos idiomas admiten optimizaciones tales como eliminación de llamadas de cola .) Comprender la implementación habitual / simple puede ser útil para manejar la abstracción, pero no debe engañarse para pensar que es toda la historia.
ruakh
2
@ruakh Yo diría que una función que se ejecuta en espacio constante mediante el uso de la eliminación de llamadas de cola es realmente un bucle. Aquí la pila no es el detalle de la implementación, es la abstracción que le permite acumular diferentes estados para diferentes niveles de recursión.
Cimbali
@ruakh: cualquier estado dentro de una sola llamada recursiva se almacenará en una pila implícita, a menos que el compilador pueda convertir la recursividad en un bucle iterativo. La eliminación de la llamada de cola es un detalle de implementación, el que debe tener en cuenta si desea reorganizar su función para que sea recursiva de cola. Además, "pocos de esos idiomas no lo hacen" : ¿puede proporcionar un ejemplo de idiomas que no necesitan una pila para llamadas recursivas?
Groo
@ruakh: CPS por sí mismo crea la misma pila implícita, por lo que debe basarse en la eliminación de llamadas de cola para que tenga sentido (lo cual es trivial debido a la forma en que está construido). Incluso el artículo de Wikipedia con el que se vinculó dice lo mismo: el uso de CPS sin optimización de llamada de cola (TCO) hará que no solo la continuación construida crezca potencialmente durante la recursión, sino también la pila de llamadas .
Groo
7

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á.

JacquesB
fuente
3

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, , 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".

Giorgio
fuente
2
@morbidCode: la recursividad primitiva y la recursividad μ son formas de recursión con restricciones específicas (o falta de ellas), estudiadas, por ejemplo, en la teoría de la computabilidad. Como resultado, un lenguaje con solo un FORbucle puede calcular exactamente todas las funciones recursivas primitivas, y un lenguaje con solo un WHILEbucle puede calcular exactamente todas las funciones recursivas µ (y resulta que las funciones recursivas µ son exactamente esas funciones que una máquina de Turing puede calcular). O, para abreviar: recursividad primitiva y recursividad µ son términos técnicos de la teoría matemática / computabilidad.
Jörg W Mittag
2
Pensé que "recursión" implicaba una función que se llamaba a sí misma, lo que daba como resultado que el estado de ejecución actual se empujara a la pila, etc. por lo tanto, la mayoría de las máquinas tienen un límite práctico sobre cuántos niveles puede repetir. Mientras que los bucles no tienen tales límites porque internamente usarían algo como un "JMP" y no usarían la pila. Solo mi entendimiento, podría estar equivocado.
Jay
13
Esta respuesta está usando una definición completamente diferente para la palabra "recursiva" que la OP estaba usando, y por lo tanto es muy engañosa.
Mooing Duck
2
@DavidGrinberg: Cita: "C, C ++, Java para bucles no son un ejemplo de recursividad primitiva. La recursividad primitiva significa que el número máximo de iteraciones / profundidad de recursión se fija antes de comenzar el bucle". Giorgio está hablando de las primitivas de la teoría de la computabilidad . No relacionado con lenguajes de programación.
Mooing Duck
3
Tengo que estar de acuerdo con el pato Mooing. Si bien la teoría de la computabilidad podría ser interesante en la CS teórica, creo que todos están de acuerdo en que el OP estaba hablando sobre el concepto de lenguajes de programación.
Voo
2

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.

Basile Starynkevitch
fuente
1

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.

ComicSansMS
fuente
1
Por supuesto, la segunda función recursiva no es recursiva de cola: es mucho más difícil optimizar el espacio ya que no puede usar TCO para reutilizar la pila. La implementación de una lista doblemente vinculada haría que ambos algoritmos fueran triviales de cualquier manera, a costa del espacio de un puntero / referencia por elemento.
Baldrickk
@Baldrickk Lo curioso de la recursión de cola es que terminas con una versión que está mucho más cerca de cómo se vería la versión de bucle, ya que nuevamente elimina tu capacidad de almacenar el estado en la pila de llamadas. Una lista doblemente vinculada lo resolvería, pero rediseñar la estructura de datos a menudo no es una opción cuando se encuentra con este problema. Si bien el ejemplo aquí es algo artificialmente limitado, ilustra un patrón que aparece con frecuencia en lenguajes funcionales en el contexto de tipos algebraicos recursivos.
ComicSansMS
Mi punto fue que si se encuentra con este problema, se debe más a una falta de diseño funcional, que a las construcciones de lenguaje que usa para implementarlo, y cada opción tiene sus propios aspectos positivos y negativos :)
Baldrickk
0

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

zeawee
fuente
44
@Giorgio No es mi voto negativo, pero solo una suposición: creo que la mayoría de los programadores sienten que la recursión implica que hay una llamada de función recursiva, porque, bueno, eso es la recursión, una función que se llama a sí misma. En un bucle, no hay llamada de función recursiva. Por lo tanto, decir que un bucle sin llamada de función recursiva es una forma especial de recursión sería descaradamente incorrecto, si se sigue esta definición.
hyde
1
Bueno, tal vez mirarlo desde un punto de vista más abstracto, lo que parecen ser cosas diferentes, en realidad son conceptualmente iguales. Me resulta bastante desalentador y triste pensar que las personas rechazan las respuestas solo porque no se corresponden con sus expectativas en lugar de aprovecharlas como una oportunidad para aprender algo. Todas las respuestas que intentan decir: "Oye, mira, estas cosas se ven diferentes en la superficie, pero en realidad son las mismas en un nivel más abstracto" han sido rechazadas.
Giorgio
3
@Georgio: El propósito de este sitio es obtener respuestas a las preguntas. Las respuestas que son útiles y correctas merecen votos positivos, las respuestas que son confusas e inútiles merecen votos negativos. Una respuesta que usa sutilmente una definición diferente de un término común sin dejar en claro qué definición diferente se usa es confusa e inútil. Las respuestas que solo tienen sentido si ya conoce la respuesta, por así decirlo, no son útiles, y solo sirven para mostrar a los escritores una comprensión superior de la terminología.
JacquesB
2
@JacquesB: "Las respuestas que solo tienen sentido si ya sabes la respuesta, por así decirlo, no son útiles ...": Esto también se puede decir de las respuestas que solo confirman lo que el lector ya sabe o piensa saber. Si una respuesta introduce una terminología que no está clara, es posible escribir comentarios para pedir más detalles antes de votar.
Giorgio
44
Los bucles no son una forma especial de recursión. Observe la teoría de la computabilidad y, por ejemplo, el lenguaje WHILE teórico y el cálculo µ. Sí, algunos idiomas utilizan bucles como el azúcar sintáctica para realmente utilizar la recursividad detrás de las escenas, pero que pueden hacer que debido a la recursividad e iteración son igualmente expresiva , no porque ellos son los mismos.
Polygnome
-1

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.

El gran pato
fuente
2
Estás hablando de la implementación de una llamada a procedimiento y de un ciclo while y, dado que se implementan de manera diferente, concluyes que son diferentes. Sin embargo, conceptualmente son muy similares.
Giorgio
1
Dependiendo del compilador, una llamada de recursión en línea optimizada podría producir el mismo ensamblaje, como un bucle simple.
hyde
@hyde ... que es solo un ejemplo del hecho bien conocido de que uno puede expresarse a través del otro; No significa que sean idénticos. Un poco como masa y energía. Por supuesto, uno puede argumentar que todas las formas de producir resultados idénticos son "lo mismo". Si el mundo fuera finito, todos los programas serían constexpr, al final.
Peter - Restablece a Monica el
@Giorgio Nah, es una descripción lógica, no una implementación. Sabemos que las dos cosas son equivalentes ; pero la equivalencia no es identidad , porque la pregunta (y las respuestas) es exactamente cómo llegamos al resultado, es decir, necesariamente contienen descripciones algorítmicas (que pueden expresarse en términos de pila y variable, etc.).
Peter - Restablece a Monica el
1
@ PeterA.Schneider Sí, pero esta respuesta dice "Lo más importante de todo ... código de ensamblaje diferente", lo cual no es del todo correcto.
hyde
-1

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".

Dave Cousineau
fuente