¿Se pueden expresar todos los algoritmos iterativos recursivamente?

Question

Si no, ¿hay un buen ejemplo de contador que muestre un algoritmo iterativo para el que no exista contraparte recursiva?

Si es el caso de que todos los algoritmos iterativos se puedan expresar recursivamente, ¿hay casos en que esto es más difícil de hacer?

Además, ¿qué papel juega el lenguaje de programación en todo esto? Me imagino que los programadores de Scheme tienen una interpretación diferente de la iteración (= recursión de cola) y el uso de la pila que los programadores de solo Java.

Answer 1

Hay una prueba ad hoc simple para esto. Como puedes construir un lenguaje completo de Turing usando estructuras estrictamente iterativas y un lenguaje completo de Turning usando solo estructuras recursivas, entonces las dos son equivalentes.

Answer 2

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

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

Aquí, aunque la función se ve iterativo, que en realidad recursivamente en una lambda interna que utiliza tres parámetros, x, y y i, y se hace llamar con nuevos valores en cada iteración.

Ésta es una forma de que la función podría ser ampliado-macro:

(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 hace más evidente visualmente.

Answer 3

Definición 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 se prueba por X. Esta variable tendrá que ser pasado a lo largo en 'vars' de alguna manera cuando va por la ruta recursiva.

Answer 4

Prolog es único lenguaje recursivo y se puede hacer casi todo en él (no sugiero que hagas, pero se puede :))

Answer 5

Como ha señalado en el zócalo their answer podemos construir pruebas que muestran cómo recursion y la iteración son equivalentes y se pueden usar para resolver el mismo problema; Sin embargo, aunque sabemos que los dos son equivalentes, existen inconvenientes para usar uno sobre el otro.

En los idiomas que no están optimizados para la recursión, es posible que un algoritmo que usa iteraciones preformas sea más rápido que el recursivo y, además, incluso en los idiomas optimizados, un algoritmo que usa iteraciones escritas en un idioma diferente corre más rápido que uno recursivo Además, puede que no exista una forma obvia de escribir un algoritmo dado que use recurrencia versus iteración y viceversa. Esto puede conducir a un código que es difícil de leer y que conduce a problemas de mantenimiento.

Answer 6

¿Se pueden expresar de forma recursiva todos los algoritmos iterativos?

Sí, pero la prueba no es interesante:

1. transformar el programa con todo su flujo de control en un único bucle que contiene una declaración de caso único en el que cada rama es el flujo de control de línea recta, posiblemente, incluyendo break, return, exit, raise, y así sucesivamente. Introduzca una nueva variable (llámelo el "contador de programa") que la declaración de caso utiliza para decidir qué bloque ejecutar a continuación.

   Esta construcción fue descubierta durante las grandes "guerras de programación estructurada" de la década de 1960 cuando las personas discutían el relativo poder expresivo 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 & agrave ;! Iteración reemplazada por recursión.

Este procedimiento equivale a escribir un intérprete para la función original. Como se puede imaginar, da como resultado un código ilegible, y no es algo interesante de 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.

Answer 7

Recursive Solutions son generalmente relativamente ineficientes en comparación con soluciones iterativas. Sin embargo, se observa que hay algunos problemas que pueden resolverse solo mediante recursión y que la solución iterativa equivalente puede no existir o ser extremadamente compleja de programar fácilmente (Ejemplo de esto es La función de Ackermann no se puede expresar sin recursividad). elegante, fácil de escribir y entender