¿Cómo entender este código de recursión?

12

Encontré este código en el manual que An Introduction to Programming in Emacs Lispdemuestra la recursividad con la ayuda de la condfunción para averiguar el número de guijarros en función del número ingresado de filas, es decir, si las filas = 2, entonces los guijarros deberían ser 3, si 4 filas deberían ser 10 guijarros allí.

(defun triangle-using-cond (number)
  (cond ((<= number 0) 0)
        ((= number 1) 1)
        ((> number 1)
         (+ number (triangle-using-cond (1- number))))))

evaluar a 10 después de pasar el argumento 4:

(triangle-using-cond 4)

El manual no explica claramente lo que sucede en cada paso de este código de ejemplo en particular y no pude entender cómo funciona la recursividad aquí. ¿Pueden ayudarme a comprender la mecánica paso a paso de lo que sucede en cada caso?

doctorado
fuente
Dejaré que alguien más te ayude con la palabra "recursión" (porque lo considero algo diferente a este contexto) o explicaré mejor lo que estoy a punto de escribir: (a) si el número es menor o igual a 0, luego 0; (b) si el número es igual a 1, entonces 1; (c) si el número es mayor que 1, agregue el número al valor devuelto por la función triangle-using-condcon el argumento 1 menor que cualquiera que sea el número. Las condiciones van en orden de a, b, y luego c - lo que coincida primero, es donde se detiene el dinero.
abogados el
como de costumbre, el intérprete de elisp evalúa de lo más interno a lo más externo. Por lo tanto, 1-4 = 3. Ahora la llamada recursiva será (triangle-using-cond 3), pero eso terminará con la misma llamada recursiva una y otra vez hasta que llegue al 1 condicional, ¿verdad? ¿qué pasará después?
doctorado
Ah, ya veo, la función se reutiliza en el paso 3, está bien, buen punto.
abogados el
Me pregunto cuál sería el resultado (triangle-using-cond 3).
doctorado
2
nb La función 1-tiene un nombre particularmente engañoso, especialmente si lee una llamada como si fuera una notación infija. Devuelve su argumento menos uno; NO uno menos el argumento.
phils

Respuestas:

14

Uso de "depuración de printf"

Puede dejar que Emacs lo ayude a comprender modificando la definición de la función:

(defun triangle-using-cond (number)
  (message (format "called with %d" number))
  (cond ((<= number 0) 0)
        ((= number 1) 1)
        ((> number 1)
         (+ number (triangle-using-cond (1- number))))))

Simplemente agregue un (message ...)lugar para imprimir un rastro en el *Messages*búfer.

Usando Edebug

Coloque el punto en cualquier lugar dentro de la definición de la función y presione C-u C-M-xpara "instrumentarlo". Luego evalúe la función, por ejemplo, colocando un punto después (triangle-using-cond 3)y golpeando C-x C-e.

Ahora estás en modo Edebug. Presiona la barra espaciadora para recorrer la función. Los valores intermedios de cada expresión se muestran en el área de eco. Para salir del modo Edebug solo presiona q. Para eliminar la instrumentación, coloque el punto en cualquier lugar dentro de la definición y presione C-M-xpara reevaluar la definición.

Usando el depurador estándar de Emacs

M-x debug-on-entry triangle-using-cond, luego, cuando triangle-using-condse invoca, se le coloca en el depurador de Emacs (búfer *Backtrace*).

Avance por la evaluación usando d(o cpara omitir cualquier evaluación no interesante).

Para ver el estado intermedio (valores variables, etc.) puede usarlo en ecualquier momento. Se le solicita que ingrese un sexp para evaluar, y se imprime el resultado de la evaluación.

Mientras usa el depurador, mantenga una copia del código fuente visible en otro marco, para que pueda seguir lo que está sucediendo.

También puede insertar llamadas explícitas para ingresar el depurador (más o menos puntos de interrupción) en lugares arbitrarios en el código fuente. Usted inserta (debug)o (debug nil SOME-SEXP-TO-EVALUATE). En el último caso, cuando se ingresa el depurador SOME-SEXP-TO-EVALUATEse evalúa y se imprime el resultado. (Recuerde que puede insertar dicho código en el código fuente y utilizarlo C-M-xpara evaluarlo, luego deshacerlo; no necesita guardar el archivo editado).

Consulte el manual de Elisp, nodo Using Debuggerpara obtener más información.

La recursión como un bucle

De todos modos, piense en la recursividad como un bucle. Hay dos casos de terminación definidos: (<= number 0)y (= number 1). En estos casos, la función devuelve un número simple.

En el caso recursivo, la función devuelve la suma de ese número y el resultado de la función con number - 1. Eventualmente, la función se llamará con 1o con un número menor o igual a cero.

El resultado del caso recursivo es por lo tanto:

(+ number (+ (1- number) (+ (1- (1- number)) ... 1)

Toma por ejemplo (triangle-using-cond 4). Acumulemos la expresión final:

  • en la primera iteración numberes 4, entonces (> number 1)se sigue la rama. Comenzamos a construir una expresión (+ 4 ...y llamamos a la función con (1- 4), es decir (triangle-using-cond 3).

  • ahora numberes 3, y el resultado es (+ 3 (triangle-using-cond 2)). La expresión de resultado total es (+ 4 (+ 3 (triangle-using-cond 2))).

  • numberes 2ahora, entonces la expresión es(+ 4 (+ 3 (+ 2 (triangle-using-cond 1))))

  • numberes 1ahora, y tomamos la (= number 1)rama, lo que resulta en un aburrido 1. Toda la expresión es (+ 4 (+ 3 (+ 2 1))). Evaluar que de adentro hacia afuera y se obtiene: (+ 4 (+ 3 3)), (+ 4 6)o simplemente 10.

rekado
fuente
3
Edebug será aún mejor. =)
Malabarba
¿Cómo hacer que se imprima el rastro usando message (...), golpear C-x C-emuestra el resultado final (10) nada más? ¿Me estoy perdiendo de algo?
doctorado
@Malabarba, ¿cómo poner Edebugen acción?
doctorado
1
@doctorate golpeó C-u C-M-xcon un punto dentro de la función para eliminar errores . Luego, simplemente ejecute la función normalmente.
Malabarba
@doctorate las (message ...)cosas se imprimen en el *Message*búfer.
Rekado
6

El Modelo de sustitución para la aplicación de procedimiento de SICP puede explicar el algoritmo para comprender un código como este.

Escribí un código para facilitar esto también. lispy-flattendel paquete lispy hace esto. Aquí está el resultado de aplicar lispy-flattena (triangle-using-cond 4):

(cond ((<= 4 0)
       0)
      ((= 4 1)
       1)
      ((> 4 1)
       (+ 4 (triangle-using-cond (1- 4)))))

Puede simplificar la expresión anterior a solo:

(+ 4 (triangle-using-cond 3))

Luego aplanar una vez más:

(+ 4 (cond ((<= 3 0)
            0)
           ((= 3 1)
            1)
           ((> 3 1)
            (+ 3 (triangle-using-cond (1- 3))))))

El resultado final:

(+ 4 (+ 3 (+ 2 1)))
abo-abo
fuente
3

Esto no es específico de Emacs / Elisp, pero si tienes experiencia en matemáticas, entonces la recursión es como la inducción matemática . (O si no lo haces: ¡cuando aprendes la inducción, es como una recursión!)

Comencemos con la definición:

(defun triangle-using-cond (number)
  (cond ((<= number 0) 0)
        ((= number 1) 1)
        ((> number 1)
         (+ number (triangle-using-cond (1- number))))))

Cuando numberes así 4, ninguna de las dos primeras condiciones se cumple, por lo que se evalúa de acuerdo con la tercera condición:
(triangle-using-cond 4)se evalúa como
(+ number (triangle-using-cond (1- number))), es decir, como
(+ 4 (triangle-using-cond 3)).

Del mismo modo,
(triangle-using-cond 3)se evalúa como
(+ 3 (triangle-using-cond 2)).

Del mismo modo, (triangle-using-cond 2)se evalúa como
(+ 2 (triangle-using-cond 1)).

Pero para (triangle-using-cond 1), la segunda condición se cumple, y se evalúa como 1.

Un consejo para cualquiera que esté aprendiendo recursividad: trate de evitar

El error común de principiante de tratar de pensar en lo que sucede durante la llamada recursiva en lugar de confiar en que la llamada recursiva funciona (a veces llamada el salto recursivo de la fe).

Si está tratando de convencerse de si (triangle-using-cond 4)devolverá la respuesta correcta, simplemente suponga que (triangle-using-cond 3)devolverá la respuesta correcta y verifique si será correcta en ese caso. Por supuesto, también debe verificar el caso base.

ShreevatsaR
fuente
2

Los pasos de cálculo para su ejemplo serían los siguientes:

(4 +               ;; step 1
   (3 +            ;; step 2
      (2 +         ;; step 3
         (1))))    ;; step 4
=> 10

La condición 0 nunca se cumple porque 1 como entrada ya finaliza la recursividad.

pimenton
fuente
(1)No es una expresión válida.
Rekado
1
Se evalúa muy bien con M-x calc. :-) En serio, quise mostrar el cálculo, no la evaluación de Lisp.
pimentón
Oh, ni siquiera me di cuenta de que está en (4 +lugar de (+ 4en tu respuesta ... :)
rekado
0

Creo que es bastante fácil, no necesitas emacs lisp para esto, solo son matemáticas de primaria.

f (0) = 0

f (1) = 1

f (n) = f (n-1) + n cuando n> 1

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

Ahora es obvio.

Chen Bin
fuente
Sin embargo, en el caso de esta función, f (0) nunca se llama.
Rekado