Récursion enveloppée, finale, croisée..

[VDH-Bruno]

Bonjour,

 

En ce moment je me consacrer à la compréhension de ce que l’on nomme la récursivité, étant complètement néophyte en la matière je me suis un peu documenté (source Wikipédia et CADXP ) ,

 

 

En première approche, j’ai testé les codes simples que j’arrivais à comprendre et je me suis amusé à supprimé certaine condition d’arrêt histoire de me confronté avec la notion de pile.

 

Je pense en avoir saisie les grandes lignes que sont :

- Le choix des conditions d’arrêts.

- L’empilement et le dépilement.

- La notion de pile et sa limite (variable suivant ce que l’on empile)

- La notion d’ appel enveloppée

 

 

En second temps, pour continuer sur ma lancé, j’ai essayé de pousser un peu plus loin ( avec bien moins succès je l’avoue..) dans les formes suivantes :

 

La récursion terminale (ou récursion finale)

 

L’intérêt et d’économiser l’espace de la pile. Pour ce faire j’ai-(je pense avoir) adapté l’exemple de la factoriel fourni en sheme, avec l’emploi d’un accumulateur.

 

 ;; factorielle récursion terminale:  scheme traduit
;; http://fr.wikipedia.org/wiki/R%C3%A9cursion_terminale
(defun fact (n)
 (defun iterer	(n acc)
   (if	(<= n 1)
     acc
     (iterer (1- n) (* acc n))
   ) ;_ Fin de if
 ) ;_ Fin de defun
 (iterer n 1)
) ;_ Fin de defun

 

 

Console visual LISP

-------------------

 _$ (trace fact iterer)
ITERER
_$ (fact 5)
120
_$ 

 

Fenêtre de suivie

------------------

 Saisie (FACT 5)
 Saisie (ITERER 5 1)
   Saisie (ITERER 4 5)
     Saisie (ITERER 3 20)
       Saisie (ITERER 2 60)
         Saisie (ITERER 1 120)
         Résultat:  120
       Résultat:  120
     Résultat:  120
   Résultat:  120
 Résultat:  120
Résultat:  120

 

Le résultat et juste mais visiblement il n’y a pas eu d’économie réalisé sur la pile. Soit l’interpréteur ne sait pas optimiser ce type de récursion, ou plus simplement je n’ai pas réussi à transposer le raisonnement en LISP.

 

 

Récursion mutelle (ou récursivité croisée)

 

C’est une récursion ou deux (ou plus) fonctions sont définies l’une en termes de l’autre, même si je me fais grosso modo une idée du principe. J’aurais tout de même souhaité savoir si un membre de ce forum aurait un exemple de code (ou lien qui m’aurait échappé) pas trop ardu ( c’est encore tout neuf pour moi) à me fournir.

Histoire de regarder comment tout cela s’articule, n’étant pas encore capable dans monter un par moi-même..

 

Merci,

 

[Patrick_35]

Salut

 

(gile) parle de la récursivité qui peut parfois se réveler indispensable.

Mais il existe aussi les fonctions itératives et avec les tests au benchmark, c'est plus rapide et on évite aussi les débordements de pile.

Exemple d'itération

(while une_liste
  ...
  (setq une_liste (cdr une_liste))
)

 

@+

[(gile)]

Salut,

 

À ma connaissance, contrairement à d'autre langages fonctionnels (Scheme, Python, F#, ...), AutoLISP n'est pas optimisé pour détecter la récursion terminale.

L'exemple de code que tu donnes, provoquerait un dépassement de la pile (mais avec la fonction factorielle c'est la limite des entiers positifs (2147483647) qui sera atteint avant).

Un équivalent itératif de la fonction fact pourrait s'écrire :

(defun fact (n / acc)
 (setq acc 1)
 (while (    (setq acc (* acc n)
  n   (1- n)
   )
 )
 acc
)

 

Tu trouveras un exemple de récursion croisée ici.

Il me semble en avoir fait d'autres mais je ne les trouve plus...

[(gile)]

Un exemple de récursion croisée donné sur TheSwamp

 

Il s'agissait d'arborescences et je proposais de les représenter sous forme de listes imbriquées où chaque noeud est le 'car' d'une sous liste pouvant contenir d'autres sous listes.

L'index de chaque noeud est représenté par une liste d'index dans l'ordre de parenté.

 

Exemple avec un arbre où chaque noeud est la chaîne représentant son index.

 

(setq tree
      '(("0"
  ("0.0"
   ("0.0.0")
   ("0.0.1")
  )
  ("0.1")
  ("0.2"
   ("0.2.0")
   ("0.2.1")
   ("0.2.2"
    ("0.2.2.0")
    ("0.2.2.1")
   )
  )
 )
 ("1"
  ("1.0"
   ("1.0.0")
   ("1.0.1")
  )
  ("1.1"
   ("1.1.0")
   ("1.1.1")
  )
 )
)
)

 

Pour retourner un noeud et ses enfants à l'index spécifié, une récursion simple :

(GetNodeAt '(0 2 2) tree) retourne ("0.2.2" ("0.2.2.0") ("0.2.2.1"))

 

(defun GetNodeAt (ind tree)
 (if tree
   (if	(cdr ind)
     (GetNodeAt (cdr ind) (cdr (nth (car ind) tree)))
     (nth (car ind) tree)
   )
 )
)

 

Pour retourner l'index d'un noeud, récursion croisée

(GetIndexOf "1.0.1" tree) retourne (1 0 1)

 

(defun GetIndexOf (node tree / foo1 foo2)
 (defun foo1 (ind node tree)
   (if	tree
     (if (assoc node tree)
(reverse (cons (vl-position (assoc node tree) tree) ind))
(foo2 (cons 0 ind) node tree)
     )
   )	
 )
 (defun foo2 (ind node tree)
   (if	tree
     (cond
((foo1 ind node (cdar tree)))
(T (foo2 (cons (1+ (car ind)) (cdr ind)) node (cdr tree)))
     )
   )
 )
 (foo1 nil node tree)
)

 

[(gile)]

Re,

 

Je ne sais pas si on peut vraiment parler de récursion croisée pour les fonctions de tri des réponses 11, 20 et 21 de ce challenge.

[(gile)]

Re,

 

un autre exemple intéressant ici (il me semble que le code est de Michael Puckett)

[Patrick_35]

eh ben :cool:

Si avec tous les liens donnés pas (gile) VDH-Bruno n'y arrive pas ;)

 

@+

[VDH-Bruno]

Merci beaucoup (gile) pour tous ces liens, j’étudie encore la question.. :yltype:

Patrick-35, tu as raison avec tout cela je devrai bien arriver à quelque chose, mais pas forcément sur une soirée.. ;)

 

Pour l’instant je découvre, potasse, teste et tente d’analyser..

J’apprends énormément, je note et compare si ça continu, je vais finir par aboutir à une thèse.. :casstet:

 

Bon si je réussie à synthétiser tout cela en quelque chose d’intelligible, je vous en ferai part même si à vos yeux j’enfoncerai certainement des portes ouvertes..

 

Cordialement,

 

[(gile)]

Salut,

 

Je déterre ce sujet.

En faisant du "rangement" dans mes bibliothèques de routines, j'ai remis la main sur celles-ci.

Il s'agit du calcul du déterminant d'une matrice carrée par la méthode des cofacteurs (formule de Laplace).

 

La récursion croisée permet ici de calculer soit :

- le cofacteur d'indice i, j d'une matrice (ce qui nécessite de calculer le déterminant de la sous matrice déduite par suppression de la rangée i et de la colonne j ;

- le déterminant d'une matrice en calculant, pour les matrices de dimension > à 2, les cofacteurs d'indice 1, n (soit la première rangée et chaque colonne).

 

;; gc:Cofactor
;; Retourne le cofacteur à l'indice i,j d'une matrice m
(defun gc:Cofactor (i j m)
 (* (gc:Determ
      (gc:RemoveAt
 (1- i)
 (mapcar (function (lambda (x) (gc:RemoveAt (1- j) x))) m)
      )
    )
    (expt -1 (+ i j))
 )
)

;; gc:Determ
;; Retourne le déterminant d'une matrice carré
(defun gc:Determ (m)
 (if (= 2 (length m))
   (- (* (caar m) (cadadr m)) (* (caadr m) (cadar m)))
   ((lambda (r n)
      (apply '+
      (mapcar
	(function (lambda (x) (* x (gc:Cofactor 1 (setq n (1+ n)) m))))
	r
      )
      )
    )
     (car m)
     0
   )
 )
)

;; gc:RemoveAt
;; Retourne la liste privée de l'élément à l'indice spécifié
(defun gc:RemoveAt (ind lst)
 (if (or (zerop ind) (null lst))
   (cdr lst)
   (cons (car lst) (gc:RemoveAt (1- ind) (cdr lst)))
 )
)

[VDH-Bruno]

Salut, (gile),

 

Je déterre ce sujet.

 

En ce qui me concerne, tu ne le déterre pas vraiment, ce sujet fait toujours partie de mon actualité. Mais une grosse activité professionnel de début d’année ne me permet pas en ce moment de me dégager le temps nécessaire.. que je souhaiterais pour approfondir ce type de thème. Mais dés que je pourrai, j’y reviendrai en attendant je te remercie d’avoir eu une pensé pour nous à l’occasion de ton rangement :) .