Recursion Vs Iteration

Question

Creo que todos los problemas que tienen la lógica iterativa se pueden resolver usando iteraciones, pero ¿podemos resolver cualquier problema utilizando la recursión? ¿Puede la recursión siempre sustituir la iteración? Proporcione una prueba de su respuesta si puede. Supongamos también que tenemos una pila infinita o ejecutamos el programa en una máquina de Turing. No me importa si esta prueba es una prueba teórica. (es por eso que mencioné la Máquina de Turing)

Answer 1

Sí, la recursividad siempre puede sustituir a la iteración, esto se ha discutido before. Citando de la publicación vinculada:

Dado que puede construir un lenguaje completo de Turing utilizando estructuras estrictamente iterativas y un lenguaje completo de torneado utilizando únicamente estructuras recursivas, las dos son equivalentes.

Explicando un poco: sabemos que cualquier problema computable puede ser resuelto por una máquina de Turing. Y es posible construir un lenguaje de programación A sin recursión, que es equivalente a una máquina de Turing. De forma similar, es posible construir un lenguaje de programación B sin iteración, igual en potencia computacional a una máquina de Turing.

Por lo tanto, si ambos A y B son Turing-complete podemos concluir que para cualquier programa iterativo debe existir un programa recursivo equivalente, y viceversa. Este es un resultado teórico, en el sentido de que no da ninguna pista sobre cómo derivar un programa recursivo de un programa iterativo arbitrario, o viceversa.

Answer 2

Sí. Hay un tipo de recursión llamado tail recursion, que se puede traducir directamente a iteración. Uno puede convertirse a otro sin ningún problema. Por lo tanto, todas las soluciones iterativas se pueden convertir en soluciones recursivas.

De hecho, muchos compiladores pueden detectar que está haciendo recursividad de cola, y luego convertirlo en código de tipo for-loop para mayor eficiencia.

Answer 3

Se debe utilizar una recursividad cuando no se necesita un bucle, pero el método debe repetirse en un caso determinado. Por ejemplo, comprimir una carpeta. Si hay una subcarpeta, debería llamarse a sí misma (recursiva). Recursion podría sustituir las iteraciones si quisiera, pero no es recomendable. La mayoría de las personas solo usa iteraciones y solo usa recursiones cuando las necesita.