Encontré este código en el manual que An Introduction to Programming in Emacs Lisp
demuestra la recursividad con la ayuda de la cond
funció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?
triangle-using-cond
con 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.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?(triangle-using-cond 3)
.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.Respuestas:
Uso de "depuración de printf"
Puede dejar que Emacs lo ayude a comprender modificando la definición de la función:
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-x
para "instrumentarlo". Luego evalúe la función, por ejemplo, colocando un punto después(triangle-using-cond 3)
y golpeandoC-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 presioneC-M-x
para reevaluar la definición.Usando el depurador estándar de Emacs
M-x debug-on-entry triangle-using-cond
, luego, cuandotriangle-using-cond
se invoca, se le coloca en el depurador de Emacs (búfer*Backtrace*
).Avance por la evaluación usando
d
(oc
para omitir cualquier evaluación no interesante).Para ver el estado intermedio (valores variables, etc.) puede usarlo en
e
cualquier 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 depuradorSOME-SEXP-TO-EVALUATE
se evalúa y se imprime el resultado. (Recuerde que puede insertar dicho código en el código fuente y utilizarloC-M-x
para evaluarlo, luego deshacerlo; no necesita guardar el archivo editado).Consulte el manual de Elisp, nodo
Using Debugger
para 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á con1
o con un número menor o igual a cero.El resultado del caso recursivo es por lo tanto:
Toma por ejemplo
(triangle-using-cond 4)
. Acumulemos la expresión final:en la primera iteración
number
es4
, 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
number
es3
, y el resultado es(+ 3 (triangle-using-cond 2))
. La expresión de resultado total es(+ 4 (+ 3 (triangle-using-cond 2)))
.number
es2
ahora, entonces la expresión es(+ 4 (+ 3 (+ 2 (triangle-using-cond 1))))
number
es1
ahora, y tomamos la(= number 1)
rama, lo que resulta en un aburrido1
. Toda la expresión es(+ 4 (+ 3 (+ 2 1)))
. Evaluar que de adentro hacia afuera y se obtiene:(+ 4 (+ 3 3))
,(+ 4 6)
o simplemente10
.fuente
message (...)
, golpearC-x C-e
muestra el resultado final (10) nada más? ¿Me estoy perdiendo de algo?Edebug
en acción?C-u C-M-x
con un punto dentro de la función para eliminar errores . Luego, simplemente ejecute la función normalmente.(message ...)
cosas se imprimen en el*Message*
búfer.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-flatten
del paquete lispy hace esto. Aquí está el resultado de aplicarlispy-flatten
a(triangle-using-cond 4)
:Puede simplificar la expresión anterior a solo:
Luego aplanar una vez más:
El resultado final:
fuente
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:
Cuando
number
es 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 como1
.Un consejo para cualquiera que esté aprendiendo recursividad: trate de evitar
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.fuente
Los pasos de cálculo para su ejemplo serían los siguientes:
La condición 0 nunca se cumple porque 1 como entrada ya finaliza la recursividad.
fuente
(1)
No es una expresión válida.M-x calc
. :-) En serio, quise mostrar el cálculo, no la evaluación de Lisp.(4 +
lugar de(+ 4
en tu respuesta ... :)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.
fuente