¿Se pueden expresar recursivamente todos los algoritmos iterativos?

¿Se pueden expresar recursivamente todos los algoritmos iterativos?

Sí, pero la prueba no es interesante:

1. Transformar el programa con todo su flujo de control en un solo bucle que contiene una sola sentencia case en la que cada rama es flujo de control en línea recta, posiblemente incluyendo break, return, exit, raise, y así sucesivamente. Introduzca una nueva variable (llámela el "contador de programa" ) que la instrucción case utiliza para decidir qué bloque ejecutar siguiente.

   Esta construcción fue descubierta durante las grandes "guerras de programación estructurada" de la década de 1960, cuando la gente argumentaba el poder expresivo relativo de varias construcciones de flujo de control.

2. Reemplace el bucle con una función recursiva y reemplace cada variable local mutable con un parámetro para esa función. ¡Voilà! Iteración reemplazada por recursión.

Este procedimiento equivale a escribir un intérprete para la función original. Como usted puede imagínese, resulta en código ilegible, y no es una cosa interesante para hacer. Sin embargo, algunas de las técnicas pueden ser útiles para una persona con experiencia en programación imperativa que está aprendiendo a programar en un lenguaje funcional por primera vez.

Como usted dice, cada enfoque iterativo puede convertirse en uno "recursivo", y con llamadas de cola, la pila tampoco explotará. :- ) De hecho, así es como Scheme implementa todas las formas comunes de bucle. Ejemplo en Scheme:

(define (fib n)
  (do ((x 0 y)
       (y 1 (+ x y))
       (i 1 (+ i 1)))
      ((> i n) x)))

Aquí, aunque la función parece iterativa, en realidad recurre a una lambda interna que toma tres parámetros, x, y, y i, y llamándose a sí mismo con nuevos valores en cada iteración.

Aquí hay una forma en que la función podría ser macro-expandido:

(define (fib n)
  (letrec ((inner (lambda (x y i)
                    (if (> i n) x
                        (inner y (+ x y) (+ i 1))))))
    (inner 0 1 1)))

De esta manera, la naturaleza recursiva se vuelve más aparente visualmente.

Definiendo iterativo como:

function q(vars):
  while X:
    do Y

Se puede traducir como:

 function q(vars):
    if X:
      do Y
      call q(vars)

Y en la mayoría de los casos incluiría incrementar un contador que es probado por X. Esta variable tendrá que ser pasada en 'vars' de alguna manera cuando vaya por la ruta recursiva.

Como señala plinth en el su respuesta podemos construir pruebas que muestren cómo la recursión y la iteración son equivalentes y pueden usarse para resolver el mismo problema; sin embargo, aunque sabemos que las dos son equivalentes, hay inconvenientes para usar una sobre la otra.

En idiomas que no están optimizados para la recursión, puede encontrar que un algoritmo que utiliza la iteración se preforma más rápido que el recursivo y, del mismo modo, incluso en idiomas optimizados, puede encontrar que un el algoritmo que usa iteración escrita en un lenguaje diferente se ejecuta más rápido que el recursivo. Además, puede no haber una forma obvia de escribir un algoritmo dado usando recursión versus iteración y viceversa. Esto puede conducir a código que es difícil de leer, lo que conduce a problemas de mantenimiento.

Prolog es un lenguaje recursivo y puedes hacer casi todo en él (no sugiero que lo hagas, pero puedes:))

Las soluciones recursivas suelen ser relativamente ineficientes en comparación con las soluciones iterativas. Sin embargo,se observa que hay algunos problemas que se pueden resolver solo a través de la recursión y la solución iterativa equivalente puede no existir o extremadamente compleja de programar fácilmente (Ejemplo de ello es La función de Ackermann no se puede expresar sin recursión)Aunque las recursiones son elegantes, fáciles de escribir y entender.