Me pregunto si la recursividad es la única solución a un problema, entonces ¿la iteración con pilas es la única otra solución? Creo que son equivalentes: si la recursividad funciona, entonces la iteración funcionará con seguridad, y viceversa.

Además, no estoy seguro de por qué la recursividad se considera ineficiente y, a menudo, causa desbordamientos de pila, mientras que la iteración con pilas no lo hace. La recursividad solo usa pilas de una manera automática invisible para el usuario.

5
J Freebird 30 ene. 2016 a las 06:43

2 respuestas

La mejor respuesta

Aunque dancancode la respuesta habla sobre diferentes tipos de problemas como problemas primitivos recursivos, problemas recursivos y problemas recursivamente enumerables, en mi humilde opinión, esta pregunta trata más sobre recursividad o < una href = "https://en.wikipedia.org/wiki/Iteration" rel = "noreferrer"> iteración .

Me pregunto si la recursividad es la única solución a un problema, entonces ¿la iteración con pilas es la única otra solución?

No, existen muchos modelos de cálculo diferentes. Sin embargo, el cálculo lambda (la base de la recursividad) y Las máquinas de Turing (la base de la iteración) son los modelos de cálculo más populares. Otro modelo popular de cálculo es μ-recursión.

¿Qué es un modelo de cálculo?

Durante mucho tiempo, los matemáticos quisieron estudiar la naturaleza de la computación. Querían saber qué problemas se pueden calcular (es decir, qué problemas tienen solución) y qué problemas no se pueden calcular (es decir, qué problemas no tienen solución). También querían saber la naturaleza del cálculo (por ejemplo, cuánto tiempo se tarda en calcular la solución en relación con su tamaño de entrada, etc.).

Sin embargo, solo había un problema: "computación" es un término muy abstracto. ¿Cómo razonas sobre algo que no es concreto? Esa es la razón por la que los matemáticos necesitaban un modelo de cálculo sobre el que pudieran razonar. Un modelo de computación captura la "esencia de la computación". Eso significa que si hay un problema que se puede calcular, debe haber un algoritmo para calcularlo en cada modelo de cálculo.

Creo que son equivalentes: si la recursividad funciona, entonces la iteración funcionará con seguridad, y viceversa.

Si eso es correcto. La tesis de Church-Turing esencialmente establece que todo modelo de cálculo es equivalente en poder. Por lo tanto, todo lo que puede hacer usando la recursividad (es decir, el cálculo lambda) también se puede hacer usando iteración (es decir, una máquina de Turing).

De hecho, la mayoría de las computadoras del mundo se basan en la máquina de Turing. Por lo tanto, cada computadora usa solo iteración. Sin embargo, su computadora aún puede ejecutar programas recursivos. Esto se debe a que un compilador traduce su programa recursivo en código de máquina iterativo.

Además, no estoy seguro de por qué la recursividad se considera ineficiente y, a menudo, causa desbordamientos de pila, mientras que la iteración con pilas no lo hace. La recursividad solo usa pilas de una manera automática invisible para el usuario.

Esto se debe a la forma en que los sistemas operativos manejan los procesos. La mayoría de los sistemas operativos imponen un límite máximo al tamaño de una pila. En mi sistema operativo Linux, el tamaño máximo de pila es de 8192 KB, que no es mucho. Utilice ulimit -s para encontrar su tamaño de pila predeterminado en un sistema operativo compatible con POSIX. Esta es la razón por la que el uso de demasiada recursividad provoca un desbordamiento de pila.

Por otro lado, el tamaño del montón se puede aumentar dinámicamente mientras se ejecuta el proceso (siempre que haya espacio libre disponible). Por lo tanto, no tiene que preocuparse por quedarse sin memoria cuando usa la iteración (incluso cuando usa una pila explícita).

Además, la recursividad es generalmente más lenta que la iteración porque llamar a una función requiere un cambio de contexto mientras que en la iteración solo es necesario modificar el puntero de la instrucción (es decir, saltar, posiblemente condicional).

Sin embargo, esto no significa que la iteración sea siempre mejor que la recursividad. Los programas recursivos suelen ser más pequeños y más fáciles de entender que los programas iterativos. Además, en ciertos casos, el compilador puede eliminar los cambios de contexto por completo a través de optimización de llamadas finales (TCO). Esto no solo hace que la recursividad sea tan rápida como la iteración, sino que también garantiza que el tamaño de la pila no aumente.

Curiosamente, todos los programas recursivos se pueden convertir en recursivos finales traduciendo el programa al estilo de continuación de paso. (CPS). Por lo tanto, CPS y TCO pueden eliminar la necesidad de una pila de llamadas implícita por completo. Varios compiladores e intérpretes de lenguajes de programación funcionales utilizan esta capacidad de formas novedosas.

8
Community 23 may. 2017 a las 12:07

Existen las llamadas funciones recursivas primitivas que se pueden reescribir con un bucle. Luego hay una clase de funciones llamadas recursivas, que deben definirse de forma recursiva. Una última clase son las funciones enumerables de forma recursiva.

La famosa función de Ackermann es recursiva pero no recursiva primitiva.

Hay un excelente video sobre el tema en el canal de youtube de Computerphile: ¿El programa más difícil de calcular?

La recursividad ciertamente puede ser eficaz. Tenga en cuenta que la implementación glibc de merge sort (msort.c) es recursivo.

Tenga en cuenta que existe una optimización del compilador común para la recursividad de cola que compila la función recursiva en un bucle.

0
dancancode 30 ene. 2016 a las 04:19