recursion - No tengo idea de cómo resolver el ejercicio SICP 1.11

scheme iteration

Question

Ejercicio 1.11 :

Una función f se define por la regla de que f(n) = n si n < 3 f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) si n > 3 . Escribe un procedimiento que calcula f por medio de un proceso recursivo. Escribe un procedimiento que calcula f por medio de un proceso iterativo.

Implementarlo recursivamente es bastante simple. Pero no pude encontrar la manera de hacerlo iterativamente. Traté de comparar con el ejemplo de Fibonacci dado, pero no sabía cómo usarlo como una analogía. Así que me di por vencida (me avergüenzo de mí) y busqué en Google una explicación , y encontré esto:

(define (f n)
   (if (< n 3)
       n
       (f-iter 2 1 0 n)))

(define (f-iter a b c count)
   (if (< count 3)
       a
       (f-iter (+ a (* 2 b) (* 3 c))
               a
               b
               (- count 1))))

Después de leerlo, entiendo el código y cómo funciona. Pero lo que no entiendo es el proceso necesario para pasar de la definición recursiva de la función a esto. No entiendo cómo se pudo haber formado el código en la cabeza de alguien.

¿Podría explicar el proceso de pensamiento necesario para llegar a la solución?

Answer 1

Una función f se define por la regla de que f(n) = n, if n<3 f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3), if n > 3 . Escribe un procedimiento que calcula f por medio de un proceso recursivo.

Ya está escrito:

f(n) = n,                                  (* if *)  n < 3
     = f(n - 1) + 2f(n - 2) + 3f(n - 3),   (* if *)  n > 3

Lo creas o no, hubo una vez ese lenguaje . Escribir esto en otro idioma es solo una cuestión de sintaxis. Y, por cierto, la definición como (mal) cito tiene un error, que ahora es muy claro y evidente.

Escribe un procedimiento que calcula f por medio de un proceso iterativo.

La iteración significa avanzar (¡ hay una explicación!) En lugar de que la recursión vaya hacia atrás al principio:

f(n)   =  f(n - 1) + 2f(n - 2) + 3f(n - 3) 
       =  a        + 2b        + 3c
f(n+1) =  f(n    ) + 2f(n - 1) + 3f(n - 2)
       =  a''       + 2b''       + 3c''          a'' = a+2b+3c, b'' = a, c'' = b
......

Esto describe así las transiciones de estado del problema como

 (n, a, b, c)  ->  (n+1, a+2*b+3*c, a, b)

Podríamos codificarlo como

g (n, a, b, c) = g (n+1, a+2*b+3*c, a, b)

pero, por supuesto, nunca se detendría. Entonces, debemos tener

f n = g (2, 2, 1, 0)
  where
  g (k, a, b, c) = g (k+1, a+2*b+3*c, a, b),    (* if *) k < n
  g (k, a, b, c) = a,                           otherwise 

y esto es exactamente igual que el código que solicitó, hasta la sintaxis.

Contar hasta n es más natural aquí, siguiendo nuestro paradigma de "seguir adelante", pero contar hasta 0 como el código que cita es, por supuesto, completamente equivalente.

Los casos de esquina y los posibles errores de uno por uno se dejan de lado como tecnicismos no interesantes de ejercicio .

Answer 2

Creo que estás preguntando cómo uno podría descubrir el algoritmo de forma natural, fuera de un ''patrón de diseño''.

Fue útil para mí ver la expansión de f (n) en cada valor de n:

f(0) = 0  |
f(1) = 1  | all known values
f(2) = 2  |

f(3) = f(2) + 2f(1) + 3f(0)
f(4) = f(3) + 2f(2) + 3f(1)
f(5) = f(4) + 2f(3) + 3f(2)
f(6) = f(5) + 2f(4) + 3f(3)

Mirando más de cerca a f (3), vemos que podemos calcularlo inmediatamente a partir de los valores conocidos. ¿Qué necesitamos para calcular f (4)?

Necesitamos al menos calcular f (3) + [el resto]. Pero a medida que calculamos f (3), también calculamos f (2) yf (1), que necesitamos para calcular [el resto] de f (4).

f(3) = f(2) + 2f(1) + 3f(0)
            ↘       ↘
f(4) = f(3) + 2f(2) + 3f(1)

Entonces, para cualquier número n, puedo comenzar por calcular f (3) y reutilizar los valores que uso para calcular f (3) para calcular f (4) ... y el patrón continúa ...

f(3) = f(2) + 2f(1) + 3f(0)
            ↘       ↘
f(4) = f(3) + 2f(2) + 3f(1)
            ↘       ↘
f(5) = f(4) + 2f(3) + 3f(2)

Ya que los reutilizaremos, les daremos un nombre a, b, c. subscripted con el paso en el que estamos, y caminar a través de un cálculo de f (5):

Step 1: f(3) = f(2) + 2f(1) + 3f(0) or f(3) = a₁ + 2b₁ +3c₁

dónde

a ₁ = f (2) = 2,

b ₁ = f (1) = 1,

c ₁ = 0

desde f (n) = n para n <3.

Así:

f (3) = a ₁ + 2b ₁ + 3c ₁ = 4

Step 2: f(4) = f(3) + 2a₁ + 3b₁

Asi que:

a ₂ = f (3) = 4 (calculado anteriormente en el paso 1),

b ₂ = a ₁ = f (2) = 2,

c ₂ = b ₁ = f (1) = 1

Así:

f (4) = 4 + 2 * 2 + 3 * 1 = 11

Step 3: f(5) = f(4) + 2a₂ + 3b₂

Asi que:

a ₃ = f (4) = 11 (calculado anteriormente en el paso 2),

b ₃ = a ₂ = f (3) = 4,

c ₃ = b ₂ = f (2) = 2

Así:

f (5) = 11 + 2 * 4 + 3 * 2 = 25

A lo largo del cálculo anterior, capturamos el estado en el cálculo anterior y lo pasamos al siguiente paso, en particular:

un _paso = resultado del paso - 1

b _paso = un _{paso - 1}

c _paso = b _{paso -1}

Una vez que vi esto, crear la versión iterativa fue sencillo.

Answer 3

Dado que la publicación a la que se ha vinculado describe mucho acerca de la solución, trataré de proporcionar solo información complementaria.

Está intentando definir una función recursiva de cola en Scheme aquí, dada una definición recursiva (sin cola).

El caso base de la recursión (f (n) = n si n <3) es manejado por ambas funciones. No estoy seguro de por qué el autor hace esto; la primera función podría ser simplemente:

(define (f n)
   (f-iter 2 1 0 n))

La forma general sería:

(define (f-iter ... n)
   (if (base-case? n)
       base-result
       (f-iter ...)))

Tenga en cuenta que aún no completé los parámetros de f-iter, porque primero necesita comprender qué estado necesita pasar de una iteración a otra.

Ahora, veamos las dependencias de la forma recursiva de f (n). Hace referencia a f (n - 1), f (n - 2) yf (n - 3), por lo que debemos mantener alrededor de estos valores. Y, por supuesto, necesitamos el valor de n en sí, por lo que podemos dejar de iterar sobre él.

Así es como se presenta la llamada recursiva de cola: calculamos f (n) para usar como f (n - 1), rotamos f (n - 1) a f (n - 2) yf (n - 2) a f (n - 3) y cuenta de decremento.

Si esto todavía no ayuda, intente hacer una pregunta más específica: es realmente difícil responder cuando escribe "No entiendo", dada una explicación relativamente completa.

Answer 4

Me referiré a esto con un enfoque ligeramente diferente a las otras respuestas aquí, enfocándome en cómo el estilo de codificación puede hacer que el proceso de pensamiento detrás de un algoritmo como este sea más fácil de comprender.

El problema con el enfoque de Bill , citado en su pregunta, es que no está claro de inmediato qué significado transmite las variables de estado, a , b y c . Sus nombres no transmiten información, y la publicación de Bill no describe ninguna norma invariante u otra que obedezcan. Me resulta más fácil formular y comprender algoritmos iterativos si las variables de estado obedecen a algunas reglas documentadas que describen sus relaciones entre sí.

Con esto en mente, considere esta formulación alternativa del mismo algoritmo exacto, que difiere de la de Bill solo en tener nombres de variable más significativos para a , c y una variable de incremento de contador en lugar de una decreciente:

(define (f n)
    (if (< n 3)
        n
        (f-iter n 2 0 1 2)))

(define (f-iter n 
                i 
                f-of-i-minus-2
                f-of-i-minus-1
                f-of-i)
    (if (= i n)
        f-of-i
        (f-iter n
                (+ i 1)
                f-of-i-minus-1
                f-of-i
                (+ f-of-i
                   (* 2 f-of-i-minus-1)
                   (* 3 f-of-i-minus-2)))))

De repente, la corrección del algoritmo, y el proceso de pensamiento detrás de su creación, es simple de ver y describir. Para calcular f(n) :

• Tenemos una variable de contador i que comienza en 2 y sube a n , incrementándose en 1 en cada llamada a f-iter .
• En cada paso del camino, hacemos un seguimiento de f(i) , f(i-1) f(i-2) , que es suficiente para permitirnos calcular f(i+1) .
• Una vez que i=n , hemos terminado.

Answer 5

Necesita capturar el estado en algunos acumuladores y actualizar el estado en cada iteración.

Si tiene experiencia en un lenguaje imperativo, imagínese escribiendo un ciclo while y rastreando información en variables durante cada iteración del ciclo. ¿Qué variables necesitarías? ¿Cómo los actualizarías? Eso es exactamente lo que tienes que hacer para hacer un conjunto iterativo (recursivo) de llamadas en Scheme.

En otras palabras, podría ser útil comenzar a pensar en esto como un ciclo while en lugar de una definición recursiva. Eventualmente serás lo suficientemente fluido con recursivas -> transformaciones iterativas que no necesitarás para ayudarte a comenzar.

Para este ejemplo en particular, debe observar de cerca las tres llamadas a función, porque no está claro cómo representarlas inmediatamente. Sin embargo, este es el proceso de pensamiento probable: (en pseudocódigo Python para enfatizar la imperatividad)

Cada paso recursivo realiza un seguimiento de tres cosas:

f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) 

Entonces necesito tres estados para rastrear los valores actuales, últimos y penúltimos de f . (es decir, f(n-1), f(n-2) and f(n-3) . Llámelos a a, b, c . Tengo que actualizar estas piezas dentro de cada ciclo:

for _ in 2..n:
    a = NEWVALUE
    b = a
    c = b
return a

Entonces, ¿qué es NEWVALUE? Bueno, ahora que tenemos representaciones de f(n-1), f(n-2) and f(n-3) , es solo la ecuación recursiva:

for _ in 2..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

Ahora todo lo que queda es descifrar los valores iniciales de a, b and c . Pero eso es fácil, ya que sabemos que f(n) = n if n < 3 .

if n < 3: return n
a = 2 # f(n-1) where n = 3
b = 1 # f(n-2)
c = 0 # f(n-3)
# now start off counting at 3
for _ in 3..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

Eso todavía es un poco diferente de la versión iterativa del Esquema, pero espero que puedas ver el proceso de pensamiento ahora.