Comment comprendre ce code de récursivité?

12

J'ai trouvé ce code dans le manuel An Introduction to Programming in Emacs Lispdémontrant la récursivité à l'aide de la condfonction 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?

doctorat
la source
Je laisserai quelqu'un d'autre vous aider avec le mot "récursivité" (parce que je pense que c'est quelque chose de différent que dans ce contexte) ou mieux expliquer ce que je vais écrire: (a) si le nombre est inférieur ou égal à 0, puis à 0; (b) si le nombre est égal à 1, alors 1; (c) si le nombre est supérieur à 1, alors ajoutez le nombre à la valeur retournée par la fonction triangle-using-condavec 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.
lawlist
comme d'habitude, l'interprète elisp évalue de l'intérieur vers l'extérieur. Ainsi, 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?
doctorat du
Oh, je vois - la fonction se réutilise à l'étape 3 - d'accord, bon point.
lawlist
Je me demande quel serait le résultat (triangle-using-cond 3)?
doctorat du
2
nb La fonction 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.
phils

Réponses:

14

Utilisation du "débogage printf"

Vous pouvez laisser Emacs vous aider à comprendre en modifiant la définition de la fonction:

(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))))))

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-xdessus pour "l'instrumenter". Évaluez ensuite la fonction, par exemple en plaçant le point après (triangle-using-cond 3)et en appuyant dessus C-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 sur C-M-xpour réévaluer la définition.

Utilisation du débogueur Emacs standard

M-x debug-on-entry triangle-using-cond, puis, lorsque triangle-using-condest invoqué, vous êtes placé dans le débogueur Emacs (tampon *Backtrace*).

Parcourez l'évaluation en utilisant d(ou cpour ignorer les évaluations sans intérêt).

Pour voir l'état intermédiaire (valeurs variables, etc.), vous pouvez utiliser à etout 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-EVALUATEest évalué et le résultat est imprimé. (N'oubliez pas que vous pouvez insérer un tel code dans le code source et l'utiliser C-M-xpour l'évaluer, puis annuler - vous n'avez pas besoin d'enregistrer le fichier modifié.)

Voir le manuel Elisp, node Using Debuggerpour 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 avec 1un nombre ou un nombre inférieur ou égal à zéro.

Le résultat du cas récursif est donc:

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

Prenez par exemple (triangle-using-cond 4). Accumulons l'expression finale:

  • dans la première itération numberest 4, 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).

  • numberest maintenant 3, et le résultat est (+ 3 (triangle-using-cond 2)). L'expression du résultat total est (+ 4 (+ 3 (triangle-using-cond 2))).

  • numberest 2maintenant, donc l'expression est(+ 4 (+ 3 (+ 2 (triangle-using-cond 1))))

  • numberest 1maintenant, et nous prenons la (= number 1)branche, ce qui entraîne un ennuyeux 1. 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 simplement 10.

rekado
la source
3
Edebug sera encore mieux. =)
Malabarba
comment imprimer le tracé en utilisant le message (...), frapper C-x C-ene montre que le résultat final (10) rien d'autre? Suis-je en train de manquer quelque chose?
doctorat
@Malabarba, comment mettre Edebugen action?
doctorat du
1
@doctorate a frappé C-u C-M-xavec un point à l'intérieur de la fonction pour le modifier. Exécutez ensuite la fonction normalement.
Malabarba
@doctorate les (message ...)trucs imprimés dans le *Message*tampon.
rekado
6

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-flattendu paquet lispy fait cela. Voici le résultat de l'application lispy-flattenà (triangle-using-cond 4):

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

Vous pouvez simplifier l'expression ci-dessus pour simplement:

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

Aplatissez encore une fois:

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

Le résultat final:

(+ 4 (+ 3 (+ 2 1)))
abo-abo
la source
3

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:

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

Quand numberest 4, 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 comme 1.

Un conseil pour tous ceux qui apprennent la récursivité: essayez d'éviter

l'erreur courante du débutant d'essayer de penser à ce qui se passe pendant l'appel récursif au lieu de croire que l'appel récursif fonctionne (parfois appelé le saut récursif de la foi).

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.

ShreevatsaR
la source
2

Les étapes de calcul de votre exemple seraient les suivantes:

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

La condition 0 n'est en fait jamais remplie car 1 comme entrée termine déjà la récursivité.

paprika
la source
(1)n'est pas une expression valide.
rekado
1
Il évalue très bien avec M-x calc. :-) Sérieusement cependant, je voulais montrer le calcul, pas l'évaluation Lisp.
paprika
Oh, je n'ai même pas remarqué que c'est au (4 +lieu de (+ 4dans votre réponse ... :)
rekado
0

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.

chen bin
la source
Dans le cas de cette fonction, cependant, f (0) n'est jamais appelé.
rekado