¿Se puede transformar toda solución recursiva en una solución iterativa?

Sí, es comprobable que cada solución recursiva también se puede implementar como una solución iterativa. Dicho esto, el código puede no ser tan claro.

La razón principal para preocuparse por esto, por supuesto, es que una recursión realmente profunda corre el riesgo de volar la pila de llamadas .

En general, un enfoque para convertir una solución recursiva en una iterativa es simplemente mantener su propia estructura de datos de pila y usarla para almacenar cada contexto sucesivo a medida que explora el BST, o realiza su búsqueda de gráfico BFS, o lo que sea que esté haciendo. Puede almacenar menos datos que un marco de pila completo, y el espacio de almacenamiento dinámico de memoria es un poco menos valioso que el espacio de pila de llamadas (al menos para tiempos de ejecución que conozco).

Si.

• Cada función computable es computable por una máquina de Turing adecuada.
• Una TM se define como ejecutar un paso simple repetidamente, en otras palabras, un bucle.

¿Qué dice esto? Para cualquier función computable existe una implementación de bucle. ¿Puedes encontrarlo en un tiempo finito? Se puede demostrar que esto no es posible para una función arbitraria.

En conclusión, si bien hay una implementación de bucle para cualquier función recursiva (¡eso fue un juego de palabras!) No hay garantía de que pueda construir una. Excepto, por supuesto, en el sentido de la traducción a una implementación de máquina basada en pila que opera esencialmente de la misma manera que una TM.