Récursivité

[(gile)]

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

et 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)]

[phil_vsd]

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 !

[(gile)]

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

[phil_vsd]

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 ?

[(gile)]

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

[phil_vsd]

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 !

[(gile)]

On dit aussi parfois :

 

"Une fonction récursive est une fonction récursive."

[phil_vsd]

Que l'on peut abréger par : "Une fonction récursive.".

 

Moi presque tout compris... Hé hé

 

 

A suivre !

[phil_vsd]

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.

[(gile)]

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

[phil_vsd]

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...

 

 

[VDH-Bruno]

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

[bonuscad]

Bonjour Bruno,

Jusqu'à (fact 12) le résultat est correct, mais après cet entier le retour est faux

[VDH-Bruno]

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)

 

[VDH-Bruno]

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

[bonuscad]

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

 

[Patrick Emin]

Pour comprendre la récursivité, vous devez d'abord comprendre la récursivité.