programming-languages - recursivo - recursividad java

¿Pueden todos los algoritmos iterativos expresarse 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 los que esto sea 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

¿Pueden todos los algoritmos iterativos expresarse recursivamente?

Sí, pero la prueba no es interesante:

1. Transforme el programa con todo su flujo de control en un solo bucle que contenga una sola declaración de caso en la que cada rama sea un flujo de control en línea recta que posiblemente incluya 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 sobre 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à! 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 2

Como dices, 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 en una lambda interna que toma tres parámetros, x , y , y que se llama a sí misma con nuevos valores en cada iteración.

Esta es una de las formas en que la función podría expandirse 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 vuelve más aparente visualmente.

Answer 3

Como lo señala su pedestal en su respuesta , podemos construir pruebas que muestren cómo la 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, de la misma manera, incluso en los idiomas optimizados, es posible que un algoritmo que usa iteraciones escritas en un idioma diferente corra más rápido que el 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 4

Definir iterativo como:

function q(vars):
  while X:
    do Y

Se puede traducir como:

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

En la mayoría de los casos, Y incluiría incrementar un contador que sea probado por X. Esta variable se tendrá que pasar en ''vars'' de alguna manera cuando se vaya por la ruta recursiva.

Answer 5

Hay una simple prueba ad hoc para esto. Dado que 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 6

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

Answer 7

Las soluciones recursivas suelen ser relativamente ineficientes en comparación con las 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 recursión) Aunque las recursiones son elegantes, fáciles para escribir y entender