(gile) Posté(e) le 6 août 2006 Partager Posté(e) le 6 août 2006 Il arrive qu'on parle ici ou là de "récursivité" ou de "fonctions récursives".Qu'en est il plus précisément ?... Comment ça se traduit en LISP ?...Je vais tenter de répondre à ces questions. Une fonction récursive est une fonction qui s'appelle elle même pendant son exécution.En LISP on reconnaît un fonction récursive à l'appel fait à elle même dans son DEFUN. L'exemple le plus souvent utilisé pour expliquer la récursivité est la fonction factorielle, petit rappel de math : Factorielle n s'écrit n! si n = 0 => n! = 1 et pour tout n > 0 => n! = n * (n - 1)! Par exemple :4! = 4 * 3! = 4 * 3 * 2! = 4 * 3 * 2 * 1! = 4 * 3 * 2 * 1 = 24 En LISP, on peut écrire : (defun fact (n) (if (zerop n) 1 (* n (fact (1- n))) ) ) Une fonction définie récursivement contient au moins une condition d'arrêt : (zerop n) -> 1et un appel récursif : (* n (fact (1- n))) Par exemple : (fact 4) sera interprété une première fois (* 4 (fact 3)), puis (* 4 (* 3 (fact 2))) etc,... jusqu'à (* 4 (* 3 (* 2 (* 1 (fact 0))))) où (fact 0) remplit la condition d'arrêt et retourne 1 On appelle "empilement" les appels successifs à la fonction jusquà la condition d'arrêt et "dépilement" leurs interprétations depuis cette condition. On peut voir la procédure dans la fenêtre de suivi de la console VisualLISP en "traçant" la fonction fact avec la fonction LISP trace : http://img155.imageshack.us/img155/4381/rcurs1ku8.png Du fait de l'utilisation de la pile, l'usage de fonctions récursives permet souvent de faire de manière plus élégante ce qui avec une boucle (while) aurait nécéssité l'utilisation d'une nouvelle variable pour stocker les résultats successifs.Par exemple la fonction fact définie de manière itérative, avec while : (defun fact (n / rslt) (cond (( (T (setq rslt n) (while ( (setq rslt (* rslt (setq n (1- n)))) ) ) ) ) L'usage de fonction récursives est aussi très pratique avec des listes. ;;; TRUNC Retourne la liste tronquée à partir de la première occurrence ;;; de l'expression (liste complémentaire de celle retournée par MEMBER) (defun trunc (expr lst) (cond ;; Conditions d'arrêt ((or (null lst) (equal (car lst) expr) ) nil ) ;; Appel récursif (T (cons (car lst) (trunc expr (cdr lst)))) ) ) http://img86.imageshack.us/img86/4333/rcurs2je6.png Pour comparaison, la fonction trunc définie de façon itérative : (defun trunc (elt lst / n rslt) (setq n 0) (while ;; Conditions d'arrêt (and ( (not (equal (nth n lst) elt)) ) (setq rslt (cons (nth n lst) rslt)) (setq n (1+ n)) ) ;; Résultat (reverse rslt) ) Les fonctions récursives ont aussi quelques inconvénients, la pile n'est pas infinie et ne permet qu'un certains nombre d'évaluations au-delà duquel la "limite de la pile interne atteinte" produit une erreur. D'après mes essais, cette limite semble être fixée à 19975 sur AutoCAD.On ne peut donc utiliser de fonction récursives sur des listes de plus de 19975 éléments. L'avantage de cet inconvénient est que si la condition d'arrêt n'est jamais remplie, on n'entre pas dans une boucle sans fin comme avec (while ...)On peut faire le test avec (fact -1) D'autre part, l'exécution des fonctions récursives semble plus lente que celle des fonctions itératives et ce d'autant plus que le nombre d'interprétations (hauteur de la pile) est important. Bien évidemment, tous les eventuels ajouts, remarques, corrections, questions sont les bienvenus. [Edité le 6/8/2006 par (gile)] 1 Gilles Chanteau - gileCAD - GitHub Développements sur mesure pour AutoCAD Lien vers le commentaire Partager sur d’autres sites More sharing options...
phil_vsd Posté(e) le 22 septembre 2006 Partager Posté(e) le 22 septembre 2006 Bonsoir, Je comprend pas tout au lisp, ni aux math mais d'après ta On ne peut donc utiliser de fonction récursives sur des listes de plus de 19975 éléments. et que les résultat de factorielle doivent gagner un zéro à chaque multiple de 5 on peut concatainer et peut être ralonger la liste. Non ? http://villemin.gerard.free.fr/Denombre/Factorie.htm Et avec la fonction dite "Equation logistique" ? Le lisp se met en erreur lors d'un dédoublement de période ? Fun non ? http://fr.wikipedia.org/wiki/Fonction_logistique Je t'avoue que j'utilise rarement les factorielles pour faire mes coupes et façades ! ;) Mais parfois ça tourne à la théorie du chaos... See you ! "La ligne droite est le plus court chemin entre deux points, à condition que les deux points soient bien en face l'un de l'autre" P. Desproges. Lien vers le commentaire Partager sur d’autres sites More sharing options...
(gile) Posté(e) le 22 septembre 2006 Auteur Partager Posté(e) le 22 septembre 2006 Salut Phil, Je dois avouer ne pas tout comprendre à ta réponse. Toujours est-il que l'exemple de la factorielle pour expliquer la récursivité doit être mauvais même si c'est le plus souvent utilisé. Quand on s'attache plus à l'exemple qu'a ce qu'il est sensé illustrer, c'est que l'exemple est mal choisi. Mon propos était plus d'essayer d'expliquer la forme récursive en LISP que la fonction factorielle dont je ne me sers jamais non plus (ça sert en calcul de probabilités si mes souvenirs sont bons). [Edité le 23/9/2006 par (gile)] Gilles Chanteau - gileCAD - GitHub Développements sur mesure pour AutoCAD Lien vers le commentaire Partager sur d’autres sites More sharing options...
phil_vsd Posté(e) le 25 septembre 2006 Partager Posté(e) le 25 septembre 2006 Yo man ! Quelle différence fais tu entre récursivité et ré-itération, ou itération. Du moins en point de vue langage lisp ou Vb ? "La ligne droite est le plus court chemin entre deux points, à condition que les deux points soient bien en face l'un de l'autre" P. Desproges. Lien vers le commentaire Partager sur d’autres sites More sharing options...
(gile) Posté(e) le 25 septembre 2006 Auteur Partager Posté(e) le 25 septembre 2006 Comme dit dans le premier message : Une fonction récursive est une fonction qui s'appelle elle même pendant son exécution. Jusqu'à ce que la condition d'arrêt soit remplie les appels récursifs à la fonction créent un empilement. Une itération est la répétion d'une ou de plusieurs expressions, jusqu'à ce que la condition d'arrêt soit remplie la fonction boucle :- soit un nombre prédéfini de fois (fonction LISP repeat)- soit jusqu'à ce qu'une condition soit remplie (fonction LISP while)- soit pour tous le membres d'une liste (fonctions LISP foreach et while) Tu peux voir ausssi ce message et le lien qui y est donné. Ou aussi ce court article que je trouve asez clair. [Edité le 25/9/2006 par (gile)] Gilles Chanteau - gileCAD - GitHub Développements sur mesure pour AutoCAD Lien vers le commentaire Partager sur d’autres sites More sharing options...
phil_vsd Posté(e) le 27 septembre 2006 Partager Posté(e) le 27 septembre 2006 Bonjour, J'ai compris l'idée, j'avoue ne pas avoir posé mon regard dans la FAQ ni cherché dans le forum pensant que le sujet serai exclusif. Ce passage de l'article est clair : "lorsque la première procédure fait appel à elle-même, l'état de la première procédure doit rester en mémoire pendant que la deuxième s'exécute." , d'où l'appellation d'empilement sans doute. J'ai bien aimé le passage : la Loi récursive de Hofstadter par exemple : "Il faut toujours plus de temps que prévu, même en tenant compte de la loi de Hofstadter." Tout cela me rappelle les fractales... Merci pour tout, à bientôt ! "La ligne droite est le plus court chemin entre deux points, à condition que les deux points soient bien en face l'un de l'autre" P. Desproges. Lien vers le commentaire Partager sur d’autres sites More sharing options...
(gile) Posté(e) le 27 septembre 2006 Auteur Partager Posté(e) le 27 septembre 2006 On dit aussi parfois : "Une fonction récursive est une fonction récursive." 1 Gilles Chanteau - gileCAD - GitHub Développements sur mesure pour AutoCAD Lien vers le commentaire Partager sur d’autres sites More sharing options...
phil_vsd Posté(e) le 27 septembre 2006 Partager Posté(e) le 27 septembre 2006 Que l'on peut abréger par : "Une fonction récursive.". Moi presque tout compris... Hé hé A suivre ! "La ligne droite est le plus court chemin entre deux points, à condition que les deux points soient bien en face l'un de l'autre" P. Desproges. Lien vers le commentaire Partager sur d’autres sites More sharing options...
phil_vsd Posté(e) le 16 octobre 2006 Partager Posté(e) le 16 octobre 2006 Yo man ! J'ai trouvé ça dans le livre "programmer autocad", mais soit je suis droitier, sois il y a effectivement des fautes de frappes dans ce bouquin... Presque à chaques routines... L'éditeur lisp me met des messages mais je ne sais y répondre... : (defun c:spirale (/ PT R NC N Centre) (setq PT (Getpoint "\nPoint de départ : ")) (setq R (Getdist PT "\nRayon de départ : ")) (setq NC (Getint "\nNombre de cycles ? : ")) (if (> NC 2) (progn (Setq N 1) (Setq Centre (polar PT Pi R)) (Tracer PT CE N) ))) (Defn Tracer (P1 CE N) (if (/= N NC))) (progn (if (= (rem N 2) 0) (Setq AN 0) (Setq AN pi)) (command "ARC" P1 "c" CE "A" 180) (setq CE P1) (Setq N (1 + N)) (Setq P1 (polar P1 AN (* 2 r))) (setq R (* 2 R)) (Tracer P1 CE N) ))) Amicalement. "La ligne droite est le plus court chemin entre deux points, à condition que les deux points soient bien en face l'un de l'autre" P. Desproges. Lien vers le commentaire Partager sur d’autres sites More sharing options...
(gile) Posté(e) le 16 octobre 2006 Auteur Partager Posté(e) le 16 octobre 2006 sois il y a effectivement des fautes de frappes dans ce bouquin En effet !!! Dans la routine "Tracer" : - Def[surligneur]u[/surligneur]n au lieu de Defn - 2 paranthèses fermantes en trop après : (if (/= N NC)[surligneur]))[/surligneur] - un espace en trop dans : (Setq N (1[surligneur] [/surligneur]+ N)) Essaye avec ça : (Defun Tracer (P1 CE N) (if (/= N NC) (progn (if (= (rem N 2) 0) (Setq AN 0) (Setq AN pi) ) (command "ARC" P1 "c" CE "A" 180) (setq CE P1) (Setq N (1+ N)) (Setq P1 (polar P1 AN (* 2 r))) (setq R (* 2 R)) (Tracer P1 CE N) ) ) ) Sinon un sujet intéressant (en anglais) sur l'utilisation de fonction récursives pour dessiner des fractales ici [Edité le 16/10/2006 par (gile)] Gilles Chanteau - gileCAD - GitHub Développements sur mesure pour AutoCAD Lien vers le commentaire Partager sur d’autres sites More sharing options...
phil_vsd Posté(e) le 16 octobre 2006 Partager Posté(e) le 16 octobre 2006 J'ai parcouru le lien avec intérêt. Il y a vraiment des superpros de la prog... Je n'en suis pas découragé car mes objectifs sont tout autres mais je suis stupéfait de l'architecture des lisp. Nous avons tous notre domaine de compétence. A suivre... "La ligne droite est le plus court chemin entre deux points, à condition que les deux points soient bien en face l'un de l'autre" P. Desproges. Lien vers le commentaire Partager sur d’autres sites More sharing options...
VDH-Bruno Posté(e) le 3 juin Partager Posté(e) le 3 juin Bonjour, En redécouvrant par hasard ce post, je ne résiste pas à l'envie de présenter une version fonctionnelle de l'implémentation du calcul de la factorielle, à noter que c'est une construction qui montre comment se passer de la boucle ou de la récursion dans sa définition. (defun fact (n) ((lambda (f) (f f n) ) (lambda (g k) (if (< k 1) 1 (* k (g g (- k 1))) ) ) ) ) Citation _$ (fact 0) 1 _$ (fact 1) 1 _$ (fact 5) 24 A+ Bruno 2 Apprendre => Prendre => Rendre Lien vers le commentaire Partager sur d’autres sites More sharing options...
bonuscad Posté(e) le 3 juin Partager Posté(e) le 3 juin Bonjour Bruno, Jusqu'à (fact 12) le résultat est correct, mais après cet entier le retour est faux Choisissez un travail que vous aimez et vous n'aurez pas à travailler un seul jour de votre vie. - Confucius Lien vers le commentaire Partager sur d’autres sites More sharing options...
VDH-Bruno Posté(e) le 3 juin Partager Posté(e) le 3 juin Il y a 3 heures, bonuscad a dit : Bonjour Bruno, Jusqu'à (fact 12) le résultat est correct, mais après cet entier le retour est faux Bonsoir Bruno, Oui mais ce n'est pas de mon fait mais plutôt de comment sont implémentés les nombres entiers, pour rappel en AutoLISP les entiers relatifs sont codés sur 32 bits, d'où les limites -2^31 et 2^31 - 1 Donc 13! = 1×2×3×4×5×6×7×8×9×10×11×12×13= 6227020800 (numériquement parlant dépasse la limite des entiers signé sur 32 bits) Le dépassement de la limite des entiers est géré différemment suivant les cas: Si la valeur est entrée directement, elle est automatiquement convertie en réel _$ 6227020800 6.22702e+09 Si la valeur est le résultat d'une opération arithmétique le résultat sera faux ce qui est le cas ici: _$ (* 1 2 3 4 5 6 7 8 9 10 11 12 13) 1932053504 Pour aller au calcul de la factorielle correcte jusqu'au limite des réels supporté par AutoLISP, sur le paradigme précédemment proposé il suffit d'interroger la fonction avec une valeur réelle: _$ (fact 13.) 6.22702e+09 Ou alors par précaution de modifier le code comme ceci: (defun fact (n) ((lambda (f) (f f n) ) (lambda (g k) (if (< k 1) 1. (* k (g g (- k 1))) ) ) ) ) et là on obtient: _$ (fact 13) 6.22702e+09 Bonne soirée (Ps: Je te suis reconnaissant d'avoir soulevé ce point de détail que je n'avais pas pris la peine de développer) Apprendre => Prendre => Rendre Lien vers le commentaire Partager sur d’autres sites More sharing options...
VDH-Bruno Posté(e) le 3 juin Partager Posté(e) le 3 juin Re, Après avoir discuté du fond, au sujet de la forme j’ai conscience que ce type de fonction est un peu « casse-tête » à appréhender. Personnellement je n’en n’écris pas tous les jours moi-même. Ayant une programmation que je qualifierai plus intuitif que théorique, pour expliquer « le comment » arriver à ce type de construction de façon intelligible c’est un peu plus compliqué, mais j’essaierais à l’occasion de monter un autre exemple plus parlant dans un sujet distinct et pour ne pas polluer d'avantage celui-ci. En attendant je peux essayer de renvoyer sur sujet proche ou je m’étais essayé à en expliquer le fonctionnement https://cadxp.com/topic/40897-fraction-continue/?do=findComment&comment=229745 Apprendre => Prendre => Rendre Lien vers le commentaire Partager sur d’autres sites More sharing options...
bonuscad Posté(e) le 3 juin Partager Posté(e) le 3 juin Bonsoir Bruno, C'est marrant de se congratuler entre Bruno!... Pour ta fonction, il est sur que si tu limites aux nombres entier tu atteint vite les limites de puissance de calcul. Pour te dire, je m'étais penché sur les factorielles dans les années 80 pour programmer des clothoïdes... A l'époque (comme Denis H.) je ne comprenais rien aux fonctions récursives. AutoDesk pour la version R12 donnait un exemple de fonction récursive pour une factorielle. Fonction (fact) et (factor). Je l'ai donc utilisé pour calculer une clothoïde unitaire selon la formule de Fresnel. La fonction (trace) m'a été très utile pour appréhender cette fonction récursive. Sur les machine à 32 bits de l'époque (fact 69) était la limite supérieure de calcul. Depuis je n'ai pas re-testé les nouvelles limites sur les machine 64 bits. Pour le fun: voici mon code de la clothoïde unitaire (soyez indulgent c'est un code des années 80...) (defun desclo (lst / pl dl) (setq pl lst dl (length pl)) (command "_.pline") (repeat dl (command (car pl)) (setq pl (cdr pl)) ) (command "") (command "_.pedit" (entlast) "_fit" "") ) (defun factor (y / ) (cond ((= 0 y) 1) (t (* y (factor (1- y)))) ) ) (defun fact (nbr / x) (setq x nbr) (factor (float x)) ) (defun serie (rep / resul mark rp) (setq mark 1 rp rep som 0) (repeat (fix (* l 10)) (setq resul (/ (expt tau rp) (* (1+ (* 2 rp)) (fact rp)))) (if (/= (rem mark 2) 0) (setq resul (- resul)) ) (setq som (+ resul som) rp (+ rp 2) mark (1+ mark)) ) ) (defun c:cloun () (setvar "cmdecho" 0) (setvar "osmode" (+ 16384 (rem (getvar "osmode") 16384))) (setq l (/ (sqrt pi) 10) lst '((0.0 0.0)) tsl ()) (while (<= l (* 4.5 (sqrt pi))) (setq r (/ 1 l) tau (/ (* l l) 2) k (sqrt (* 2 tau))) (serie 2) (setq x (* k (+ 1 som))) (serie 3) (setq y (* k (+ (/ tau 3) som)) xm (- x (* r (sin tau))) ym (+ y (* r (cos tau))) dltr (- ym r) taug (/ (* tau 200) pi) taud (/ (* tau 180) pi)) (prompt "\ntau en grade : ") (prin1 (rtos taug 2 0)) (prompt "\ntau en degre : ") (prin1 (rtos taud 2 2)) (prompt "\nl longueur : ") (prin1 (rtos l 2 4)) (prompt "\nr rayon : ") (prin1 (rtos r 2 4)) (prompt "\ndelta r : ") (prin1 (rtos dltr 2 4)) (prompt "\nxM : ") (prin1 (rtos xm 2 4)) (prompt "\nyM : ") (prin1 (rtos ym 2 4)) (prompt "\nx : ") (prin1 (rtos x 2 4)) (prompt "\ny : ") (prin1 (rtos y 2 4)) (prompt "\n------------------------------------------") ;(grread) (setq l (+ l (/ (sqrt pi) 10))) (setq lst (cons (cons x (cons y ())) lst)) (setq tsl (cons (cons xm (cons ym ())) tsl)) ) (command "_.layer" "_make" "clo" "_color" "3" "" "") (desclo lst) (command "_.layer" "_make" "centre" "_color" "6" "" "") (desclo tsl) (prin1) ) Choisissez un travail que vous aimez et vous n'aurez pas à travailler un seul jour de votre vie. - Confucius Lien vers le commentaire Partager sur d’autres sites More sharing options...
Patrick Emin Posté(e) le 19 août Partager Posté(e) le 19 août Pour comprendre la récursivité, vous devez d'abord comprendre la récursivité. mon site perso Dessein-Tech Lien vers le commentaire Partager sur d’autres sites More sharing options...
Messages recommandés
Créer un compte ou se connecter pour commenter
Vous devez être membre afin de pouvoir déposer un commentaire
Créer un compte
Créez un compte sur notre communauté. C’est facile !
Créer un nouveau compteSe connecter
Vous avez déjà un compte ? Connectez-vous ici.
Connectez-vous maintenant