¿Se pueden codificar todas las funciones recursivas con iteraciones? [cerrado]

7

¿Cuáles son las ventajas de la recursión?

Algunos lenguajes de programación pueden optimizar la recursión de cola, pero aún en términos generales, la recursión consume más recursos que los bucles regulares.

¿Es posible tener una versión iterativa de alguna función recursiva?

    
pregunta OscarRyz 09.12.2010 - 19:51

5 respuestas

7

Sí, puedes codificar funciones recursivas como iteraciones. Básicamente, requiere que mantengas la información de forma manual que, de lo contrario, habría sido atendida por el código de llamada del método generado por el compilador.

En otras palabras, necesita una pila donde cada entrada es una estructura que contiene los parámetros pasados y todas las variables locales. Siempre trabajas en la entrada superior de la pila. Si necesita llamarse a sí mismo, cree una nueva entrada y póngala en la parte superior de la pila. Cuando haya terminado, tome la entrada superior de la pila exponiendo la que se encuentra a continuación, y use la entrada superior anteriormente para extraer los valores de retorno y actualizar la nueva entrada superior en consecuencia.

Le sugiero que estudie un libro de compilación para ver cómo esto generalmente se implementa en código de máquina.

    
respondido por el user1249 09.12.2010 - 19:59
14

La recursión es a menudo una forma más natural de ver las cosas que la iteración. Por ejemplo, considere la posibilidad de atravesar un árbol binario: inorder(left); process(); inorder(right); es mucho más simple que mantener una pila explícitamente.

Siempre y cuando no profundices demasiado (volar la pila), la diferencia en el uso de recursos suele ser trivial. No te preocupes por eso en general. El código simple normalmente es mejor que el código optimizado a mano, aunque hay excepciones. El derecho es normalmente mejor que rápido.

Cualquier algoritmo recursivo puede expresarse como un algoritmo iterativo, pero es posible que deba mantener una pila explícita (correspondiente a la pila de llamadas que se maneja de manera implícita). Después de todo, si compilas una función recursiva, obtienes algo que se basa en la manipulación de una pila y el bucle a través de la función, y eso es iterativo.

Las funciones recursivas de cola se pueden traducir fácilmente a bucles, y no necesitan una pila, pero ese es un caso especial.

    
respondido por el David Thornley 09.12.2010 - 20:05
4
  

¿Cuáles son las ventajas de la recursión?

Intenta resolver el problema de las Torres de Hanoi de forma iterativa. Una vez que se dé por vencido, eche un vistazo a la solución iterativa y compárela con la recursiva. ¿Cuál es más simple?

  

¿Es posible tener una versión iterativa de alguna función recursiva?

Sí, en principio. Sin embargo, para muchos problemas, que incluyen tareas muy comunes, como las travesías de árboles, las soluciones recursivas son mucho más simples y elegantes que las iterativas.

    
respondido por el Dima 09.12.2010 - 20:17
3
  

¿Cuáles son las ventajas de la recursión?

Simplicidad. Sin la optimización de la llamada de cola, por supuesto, requiere más recursos (pila), pero ¿cómo implementaría, por ejemplo, deltree en Java sin recursión? El problema es que delete() solo puede eliminar directorios si están vacíos; Aquí lo tenemos con recursión:

deltree(File fileOrDirectory) {
    if (fileOrDirectory.isDirectory()) {
        for (File subFileOrDirectory : fileOrDirectory.listFiles()) {
            deltree(subFileOrDirectory);
        }
    }
    fileOrDirectory.delete();
}
    
respondido por el Joonas Pulakka 09.12.2010 - 20:07
0

Creo que la recursión es una de esas herramientas que un programador debe tener que vivir. Con la recursión, puede "pensar" sus algoritmos y resolverlos de la forma en que lo pensó. Pero, debo advertirles que todos están hablando sobre lo bonita que es la recursión y cuánta simplicidad aporta al código, y tengo algunas cosas que decir:

  1. En primer lugar, no es fácil pensar la "forma recursiva" de un algoritmo. Construir una función como un factorial (n!) O algo así como Hanoi Towers es solo la punta del iceberg, y llegar al final requiere un tiempo muy largo.
  2. No piense que la recursión trae simplicidad solo a su código, a veces, la forma iterativa es fea y desordenada, pero es rentable (busque en la solución recursiva del problema de Fibonacci)

Teniendo esas cosas en mente, ¡aprende recursión! Es divertido, complejo y ¡te destrozará el cerebro !, pero te encantará.

¡La mejor de las suertes!

    
respondido por el David Conde 10.12.2010 - 08:20

Lea otras preguntas en las etiquetas