J'ai trouvé ce code dans le manuel An Introduction to Programming in Emacs Lisp
démontrant la récursivité à l'aide de la cond
fonction pour trouver le nombre de cailloux en fonction du nombre de lignes entré, c'est-à-dire si les lignes = 2, alors les cailloux devraient être 3, si 4 lignes, alors ce devrait être 10 cailloux Là.
(defun triangle-using-cond (number)
(cond ((<= number 0) 0)
((= number 1) 1)
((> number 1)
(+ number (triangle-using-cond (1- number))))))
évaluer à 10 après avoir passé l'argument 4:
(triangle-using-cond 4)
Le manuel n'a pas expliqué clairement ce qui se passe à chaque étape de cet exemple de code en particulier et je n'ai pas pu comprendre comment la récursivité fonctionne ici. Pouvez-vous m'aider à comprendre la mécanique étape par étape ce qui se passe à chaque instance?
triangle-using-cond
avec l'argument étant 1 de moins que le nombre. Les conditions vont dans l'ordre de a, b, puis c - tout ce qui correspond en premier, c'est là que l'argent s'arrête.1-4 = 3
. Maintenant, l'appel récursif sera(triangle-using-cond 3)
, mais cela se terminera avec le même appel récursif encore et encore jusqu'à ce qu'il atteigne le 1 conditionnel, non? que va-t-il se passer ensuite?(triangle-using-cond 3)
?1-
a un nom particulièrement trompeur, surtout si vous lisez un appel comme s'il s'agissait d'une notation infixée. Il renvoie son argument moins un; PAS un moins l'argument.Réponses:
Utilisation du "débogage printf"
Vous pouvez laisser Emacs vous aider à comprendre en modifiant la définition de la fonction:
Ajoutez simplement un
(message ...)
endroit pour imprimer une trace dans le*Messages*
tampon.Utiliser Edebug
Placez le point n'importe où à l'intérieur de la définition de la fonction et appuyez
C-u C-M-x
dessus pour "l'instrumenter". Évaluez ensuite la fonction, par exemple en plaçant le point après(triangle-using-cond 3)
et en appuyant dessusC-x C-e
.Vous êtes maintenant en mode Edebug. Appuyez sur la barre d'espace pour parcourir la fonction. Les valeurs intermédiaires de chaque expression sont affichées dans la zone d'écho. Pour quitter le mode Edebug, appuyez simplement sur
q
. Pour supprimer l'instrumentation, placez le point n'importe où dans la définition et appuyez surC-M-x
pour réévaluer la définition.Utilisation du débogueur Emacs standard
M-x debug-on-entry triangle-using-cond
, puis, lorsquetriangle-using-cond
est invoqué, vous êtes placé dans le débogueur Emacs (tampon*Backtrace*
).Parcourez l'évaluation en utilisant
d
(ouc
pour ignorer les évaluations sans intérêt).Pour voir l'état intermédiaire (valeurs variables, etc.), vous pouvez utiliser à
e
tout moment. Vous êtes invité à saisir un sexp à évaluer et le résultat de l'évaluation est imprimé.Pendant que vous utilisez le débogueur, gardez une copie du code source visible dans un autre cadre, afin de pouvoir suivre ce qui se passe.
Vous pouvez également insérer des appels explicites pour entrer le débogueur (plus ou moins de points d'arrêt) à des endroits arbitraires dans le code source. Vous insérez
(debug)
ou(debug nil SOME-SEXP-TO-EVALUATE)
. Dans ce dernier cas, lorsque le débogueur est entréSOME-SEXP-TO-EVALUATE
est évalué et le résultat est imprimé. (N'oubliez pas que vous pouvez insérer un tel code dans le code source et l'utiliserC-M-x
pour l'évaluer, puis annuler - vous n'avez pas besoin d'enregistrer le fichier modifié.)Voir le manuel Elisp, node
Using Debugger
pour plus d'informations.Récursivité en boucle
Quoi qu'il en soit, pensez à la récursivité comme une boucle. Deux cas de résiliation sont définis:
(<= number 0)
et(= number 1)
. Dans ces cas, la fonction renvoie un nombre simple.Dans le cas récursif, la fonction renvoie la somme de ce nombre et le résultat de la fonction avec
number - 1
. Finalement, la fonction sera appelée avec1
un nombre ou un nombre inférieur ou égal à zéro.Le résultat du cas récursif est donc:
Prenez par exemple
(triangle-using-cond 4)
. Accumulons l'expression finale:dans la première itération
number
est4
, donc la(> number 1)
branche est suivie. Nous commençons à construire une expression(+ 4 ...
et appelons la fonction avec(1- 4)
, ie(triangle-using-cond 3)
.number
est maintenant3
, et le résultat est(+ 3 (triangle-using-cond 2))
. L'expression du résultat total est(+ 4 (+ 3 (triangle-using-cond 2)))
.number
est2
maintenant, donc l'expression est(+ 4 (+ 3 (+ 2 (triangle-using-cond 1))))
number
est1
maintenant, et nous prenons la(= number 1)
branche, ce qui entraîne un ennuyeux1
. L'expression entière est(+ 4 (+ 3 (+ 2 1)))
. Évaluer que de l'intérieur et vous obtenez:(+ 4 (+ 3 3))
,(+ 4 6)
, ou tout simplement10
.la source
message (...)
, frapperC-x C-e
ne montre que le résultat final (10) rien d'autre? Suis-je en train de manquer quelque chose?Edebug
en action?C-u C-M-x
avec un point à l'intérieur de la fonction pour le modifier. Exécutez ensuite la fonction normalement.(message ...)
trucs imprimés dans le*Message*
tampon.Le modèle de substitution pour l'application de procédures du SICP peut expliquer l'algorithme pour comprendre un code comme celui-ci.
J'ai également écrit du code pour faciliter cela.
lispy-flatten
du paquet lispy fait cela. Voici le résultat de l'applicationlispy-flatten
à(triangle-using-cond 4)
:Vous pouvez simplifier l'expression ci-dessus pour simplement:
Aplatissez encore une fois:
Le résultat final:
la source
Ce n'est pas spécifique à Emacs / Elisp, mais si vous avez une formation en mathématiques, la récursion est comme une induction mathématique . (Ou si vous ne le faites pas: alors quand vous apprenez l'induction, c'est comme la récursivité!)
Commençons par la définition:
Quand
number
est4
, aucune des deux premières conditions n'est vérifiée, donc il est évalué selon la troisième condition:(triangle-using-cond 4)
est évalué comme(+ number (triangle-using-cond (1- number)))
, à savoir comme(+ 4 (triangle-using-cond 3))
.De même,
(triangle-using-cond 3)
est évalué comme(+ 3 (triangle-using-cond 2))
.De même,
(triangle-using-cond 2)
est évalué comme(+ 2 (triangle-using-cond 1))
.Mais pour
(triangle-using-cond 1)
, la deuxième condition est vérifiée et elle est évaluée comme1
.Un conseil pour tous ceux qui apprennent la récursivité: essayez d'éviter
Si vous essayez de vous convaincre si vous renverrez
(triangle-using-cond 4)
la bonne réponse, supposez simplement que(triangle-using-cond 3)
cela renverra la bonne réponse et vérifiez si elle sera correcte dans ce cas. Bien sûr, vous devez également vérifier le cas de base.la source
Les étapes de calcul de votre exemple seraient les suivantes:
La condition 0 n'est en fait jamais remplie car 1 comme entrée termine déjà la récursivité.
la source
(1)
n'est pas une expression valide.M-x calc
. :-) Sérieusement cependant, je voulais montrer le calcul, pas l'évaluation Lisp.(4 +
lieu de(+ 4
dans votre réponse ... :)Je pense que c'est assez facile, vous n'avez pas besoin de lire Emacs en dessous, c'est juste des mathématiques à l'école primaire.
f (0) = 0
f (1) = 1
f (n) = f (n-1) + n lorsque n> 1
donc f (5) = 5 + f (4) = 5 + 4 + f (3) = 5 + 4 + 3 + 2 + 1 + 0
Maintenant c'est évident.
la source