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

¿Cuáles son las ventajas de la recursividad?

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?

Sí, puede codificar funciones recursivas como iteraciones. Básicamente requiere que mantengas la información de forma manual que de otro modo habría sido atendida por el código de llamada al 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 más alta de la pila. Si necesita llamarse a sí mismo, cree una nueva entrada y colóquela en la parte superior de la pila. Cuando termine, tome la entrada superior de la pila exponiendo la siguiente y use la entrada superior anterior 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 se implementa generalmente en el código de máquina.

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 explícitamente una pila.

Siempre y cuando no profundices demasiado (explotando la pila), la diferencia en el uso de recursos suele ser trivial. No te preocupes por eso en general. El código simple es normalmente mejor que el código optimizado a mano, aunque hay excepciones. Lo correcto 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 implícitamente). Después de todo, si compila una función recursiva, obtiene algo que depende de manipular una pila y recorrer la función, y eso es iterativo.

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

¿Cuáles son las ventajas de la recursividad?

Intenta resolver el problema de Towers of Hanoi de forma iterativa. Una vez que te rindas, mira la solución iterativa y compárala con la recursiva. ¿Cuál es más simple?

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

Si, en principio. Sin embargo, para muchos problemas, incluidas tareas muy comunes, como los recorridos en árbol, las soluciones recursivas son mucho más simples y elegantes que las iterativas.

¿Cuáles son las ventajas de la recursividad?

Sencillez. Sin la optimización de la cola, por supuesto, requiere más recursos (stack), pero ¿cómo implementaría, por ejemplo, deltreeJava sin recurrencia? El giro es que delete()puede eliminar directorios solo si están vacíos; Aquí está con recursividad:

deltree(File fileOrDirectory) {
    if (fileOrDirectory.isDirectory()) {
        for (File subFileOrDirectory : fileOrDirectory.listFiles()) {
            deltree(subFileOrDirectory);
        }
    }
    fileOrDirectory.delete();
}

Creo que la recursividad es una de esas herramientas que un programador debe tener para vivir. Con la recursividad puede "pensar" sus algoritmos y resolverlos tal como lo pensó. Pero, debo advertirte, todo el mundo está hablando de lo bonita que es la recursividad y cuánta simplicidad aporta al código, con respecto a eso, tengo algunas cosas que decir:

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

Teniendo esas cosas en mente, ¡aprende la recursividad! ¡es divertido, complejo y te destrozará el cerebro !, pero te encantará.

¡La mejor de las suertes!