Classement

Salut, je n'ai pas très bien compris les histoires d'orientation. Pourrais tu être plus précis dans ton explication ?

Bonjour, En tant que débutant, je me lance dans une tentative d’explication sur comment à écrire une fonction récursive d’une façon que j’espère méthodique (c’est celle que je me suis faite), en espérant amener une approche différente de celle déjà proposé dans ce forum, et à l’attention de ceux qui souhaiteraient faire leurs premier pas dans ce domaine. Mon propos porte plus sur la mécanique d’écriture plutôt que sur la détection d’un algorithme récursif (ce qui est à mon sens un autre aspect du problème) (Pour une définition de la récursion et une autre explication voir ce post) A titre d’illustration, j’ai choisi un exemple très simple : Réécrire la fonction lenght Exemple : C’est le type de fonction qui s’écrit très facilement avec while ( de façon itérative), justement je vais m’appuyer dessus pour la méthodologie que je propose d’employer. Avec while comment je procédais: (il y a encore quelques mois de cela :( ) 1 - Je définissais mon nom de fonction et son argument: (defun wh-length (lst) ... ) 2 - Puis ma boucle et la condition de sortie de boucle, ainsi qu’une instruction pour vérifier son bon fonctionnement. ((defun wh-length (lst) (while lst (princ "\n") (princ (setq lst (cdr lst))) ) ) Console Visual LISP 3 - Et enfin j’habillai le tout pour obtenir le résultat escompté (defun wh-length (lst / compt) (setq compt 0) (while lst (setq lst (cdr lst) compt (1+ compt) ) ) ) Console Visual LISP De façon récursive on peut (je pense) adopter le même principe Etape 1 – Définir le nom de fonction et son argument: (defun rc-length (lst) ... ) Etape 2 – Construire l’appel récursif et sa condition d’arrêt, puis tracer ses appels pour vérifier son bon déroulement avant d’écrire la suite. (defun rc-length (lst) (if lst (rc-length (cdr lst)) ) ) (cdr lst) passé en argument réduit la liste d’un élément à chaque appel de rc-length jusqu'à satisfaire la condition d’arrêt (basé sur la validité du symbol lst). (Code très similaire avec celui fait en 2 pour la boucle while) Pour visualiser les appels récursif, il y a la fonction trace bien plus élégante que l’insertion de mes princ de l’exemple précédent. Console Visual LISP Fenêtre de suivie Saisie (RC-LENGTH (1 2 3 4 5)) Saisie (RC-LENGTH (2 3 4 5)) Saisie (RC-LENGTH (3 4 5)) Saisie (RC-LENGTH (4 5)) Saisie (RC-LENGTH (5)) Saisie (RC-LENGTH nil) Résultat: nil Résultat: nil Résultat: nil Résultat: nil Résultat: nil Résultat: nil La fonction s’appelle bien (ou boucle) jusqu’à remplir la condition d’arrêt nil, on peut passer à l’étape numéro 3 car en l’état la fonction ne retourne rien. Etape 3 – Habiller la fonction pour obtenir le résultat voulu. C’est.à.dire. incrémenter un compteur à chaque appel de rc-length pour comptabiliser le nombre l’élément de la liste. Pour cela on va initialiser le compteur à 0 dans la condition d’arrêt, en modifiant légèrement la structure du if (pour mieux visualiser la condition d’arrêt ) (if (null lst) (setq compt 0) Le compteur devenant la valeur de retour pour l’appel le plus imbriqué. On peut maintenant incrémenter chaque appel enveloppant de rc-length avec la syntaxe suivante : (setq compt (1+ (rc-length (cdr lst)))) Note: Dans un premier temps, j’ai volontairement introduit une variable comme on pourrait être tenté de le faire ( par habitude des boucles itératives), et comme il m’arrive encore de le faire (voir réponse de Carboleum) Le code (defun rc-length (lst / compt) (if (null lst) (setq compt 0) (setq compt (1+ (rc-length (cdr lst)))) ) ) Console Visual LISP Fenêtre de suivie Saisie (RC-LENGTH (1 2 3 4 5)) Saisie (RC-LENGTH (2 3 4 5)) Saisie (RC-LENGTH (3 4 5)) Saisie (RC-LENGTH (4 5)) Saisie (RC-LENGTH (5)) Saisie (RC-LENGTH nil) Résultat: 0 Résultat: 1 Résultat: 2 Résultat: 3 Résultat: 4 Résultat: 5 rc-length à maintenant le fonctionnement voulu, mais si on veut pousser l’analyse un peu plus loin il y a encore de petites simplifications possibles. Etape 4 – Optimisation des variables du code. Si on observe le déroulement de la fonction, l’argument lst est utilisé à l’ empilement des appels jusqu’à satisfaire la condition d’arrêt. Alors l’appel le plus imbriqué retourne 0 à la fonction enveloppante (ou appelante) qui s’incrémente de +1 au dépilement des appels. Ce qui pourrait ce traduire par : (1+ (1+ (1+ ( 1+ (1+ 0))))) retourne 5 0 et (1+ (rc-length (cdr lst))) sont les valeurs de retour de la fonction, il est donc inutile de mémoriser leurs valeurs dans une variable comme on le ferait dans une boucle while. Pour if on peut également simplifier, en remplaçant l’expression (null lst) par lst, sans oublier d’inverser l’ordre des deux lignes suivantes. Le code finalisé (defun rc-length (lst) (if lst (1+ (rc-length (cdr lst))) 0 ) ) Effectivement c’est beau.. :D Epilogue Comme il n’y a guère d’intérêt à écrire une fonction qui n’apporte rien de plus que la fonction lenght, nous allons la modifier encore un petit peu, histoire de... ;) (defun rc-length (x) (cond ((and (atom x) (not (null x))) 1) ((null x) 0) (T (1+ (rc-length (cdr x)))) ) ) Résultat A comparer avec En espérant avoir été suffisamment clair pour que cela puisse aider d’autre débutant. (Ps : Toutes précisions et/ou contestations sont les bienvenus cela ne pourra que me faire progresser :D ) Salutations Bruno (Edit message corrigé) [Edité le 17/11/2010 par VDH-Bruno]