Mécanique de la récursion

[VDH-Bruno]

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 :

_$ (length '(1 2 3 4 5))

5

 

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

$ (wh-length '(1 2 3 4 5))

(2 3 4 5)

(3 4 5)

(4 5)

(5)

nilnil

 

 

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

_$ (wh-length '(1 2 3 4 5))

5

 

 

 

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

_$ (trace rc-length)

RC-LENGTH

_$ (rc-length '(1 2 3 4 5))

nil

 

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

_$ (rc-length '(1 2 3 4 5))

5

 

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

_$ (rc-length '(1 2 3 4 5))

5

_$ (rc-length '(1 2 3 4 nil))

5

_$ (rc-length '(1 2 3 4 . 5))

5

_$

 

A comparer avec

_$ (length '(1 2 3 4 5))

5

_$ (length '(1 2 3 4 nil))

5

_$ (length '(1 2 3 4 . 5))

; erreur: liste incorrecte: 5

_$

 

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]

[Carboleum]

 (defun rc-length (x)
 (if (null x)
   (setq x 0)
   (1+ (rc-length (cdr x)))
 )
)

Effectivement ça fait plus classe, mais bonjour la lisibilité !!! :casstet:

 

 

Bien au contraire je trouve ce code très élégant.

tu peux même le simplifier:

 

(defun bl:length (x) (if x (1+ (bl:length (cdr x))) 0))

 

(c'est beau! ;-)

 

[VDH-Bruno]

Carboleum, je vois que la simplification n’a pas échappé à ta sagacité et je t’en remercie :cool:

 

Hé oui je dis une chose et je fais le contraire!!!

 

Le compteur devenant la valeur de retour pour l’appel le plus imbriqué … il est donc inutile de mémoriser sa valeur dans une variable comme on le ferait dans une boucle while

 

Je m’en étais rendu compte ce matin au réveil en y repensant, j’ai pas eu le temps de modifié, je corrigerai et re-moulinerai les explications en conséquence ce soir.. ;)

 

Merci

 

(Ps: j'avais tout de même pas poussé la simplification jusqu'au if, il est vrai que dans ce cas cela ne pose pas de problème contrairement à un cond..)

 

EDIT:

je corrigerai et re-moulinerai les explications en conséquence ce soir.. ;)

C'est fait :)

 

 

[Edité le 17/11/2010 par VDH-Bruno]

[Tramber]

Alors là, on peut dire que tu tombes bien !

 

(defun test(lst som /)
 (cond((	(setq lst(reverse(cons(1+(last lst))(cdr(reverse lst))))
      lst(test lst som)))
      ((>(apply '+ lst)som)
(if(not(zerop(1-(last lst))))
  (setq lst(reverse(cons(1-(last lst))(cdr(reverse lst)))))
  (setq lst(reverse(cdr(reverse lst)))))
(setq lst(test lst som)))
      )
 lst)

 

 

 

(test '(2 3 4 5) 0) -> nil

(test '(2 3 4 5) 2) -> (2)

(test '(2 3 4 5) 14) -> (2 3 4 5)

(test '(2 3 4 5) 21) -> (2 3 4 12)

(test '(2 3 4 5) 2115) -> (2 3 4 2106)

(test '(2 3 4 5) 21215) -> rien !

 

(amusant, le dernier test est dépassé, moi aussi ! Mais une explication est bienvenue.)

 

J'avais décidé de m'atteler ce soir (ou demain !) à une fonction qui réduise ou agrandisse le dernier terme d'une liste pour que la somme totale des éléments de la liste fasse une certaine somme.

Eh bien je me suis dit :

Tiens !

Je pourrais travailler sur le dernier élément de la liste pas à pas (en réduisant ou agrandissant de 1 en 1). Tiens, et puis je pourrais faire appel à la fonction elle-même pour l'évaluation suivante !

Ensuite je suis rentré, cigarette finie, et me suis réchauffé les doigts.

Cela m'a pris moins de 10 minutes. Me voilà content et auto-satisfait.

Mais la récursivité n'a pas délivré tous ses secrets pour mon cas.

 

Alors bienvenu à tous les retours d'expériences.... comme d'hab !

 

Edité : bagarre avec le BBcode

 

 

[Edité le 17/11/2010 par Tramber]

[Tramber]

J'ai trouvé la limite avec, par exemple, ces 2 expressions :

 

(test '(1 1 1 1) 19977)

(test '(1 1 1 1) 19978)

 

Chez moi, la 2ème ne renvoie rien. Rien au delà d'une somme supérieure à 19978.

 

Comment cela fonctionne-t-il ?

[(gile)]

Salut,

 

Tramber,

 

Pourquoi une fonction récursive ?

Moi qui ait plutôt l'esprit à ça je n'y aurais certainement pas pensé au premier abord.

Une fonction itérative (while) s'imposerait à mes yeux, c'est plus rapide et il n'y a pas de risque de dépassement de la pile (c'est ce qui ce produit au 19978ème appel récursif à ce moment là chez toi, la limite de la pile dépendant de la mémoire disponible).

 

Autre chose, traiter le dernier élément d'une liste requiert l'utilisation de reverse (qui est quelque peu couteuse), il est donc préférable de limiter les appels à cette fonction (un au début du traitement et un autre à la fin suffisent).

 

(defun test_iter (l s / a)
 (setq l (reverse l))
 (while (/= (setq a (apply '+ l)) s)
   (setq l (cons ((if (  )
 (reverse l)
)

 

Si on veut vraiment utiliser un processus récursif (et dans ce cas on a même pas l'intérêt de la concision du code), l'utilisation d'une fonction auxiliaire permet de limiter les appels à reverse.

 

(defun test_recurs (l s / f)
 (defun f (l s / a)
   (if	(= (setq a (apply '+ l)) s)
     l
     (f (cons ((if (    )
 )
 (reverse (f (reverse l) s))
)

[Tramber]

Oui, j'ai vu le dépassement de la pile dans la ligne de commande.

Et ce que tu dis à propos de reverse est tout simple et utile à considérer dans mon cas.

 

Pour le while, je suis d'accord, c'était même la première instruction à laquelle j'ai pensé. Mais je voulais me faire une récursive pour le principe. test_recurs est sans doute plus rapide.

 

On a sans doute déjà parlé de la pile mais j'aurais une question : avez-vous le même résultat pour le dépassement ou c'est fonction de l'ordinateur ?

[(gile)]

On a sans doute déjà parlé de la pile mais j'aurais une question : avez-vous le même résultat pour le dépassement ou c'est fonction de l'ordinateur ?

 

Refais des tests sur ton poste et tu verras que tu n'as pas toujours le même résultat, c'est fonction de la mémoire disponible à ce moment là.

[Tramber]

ok.

C'est d'ailleurs troublant car on s'perçoit que la limite ne bouge pas beaucoup tant qu'on ne quitte pas ses tests.

 

ffffffooooouu

(if (
 
Voilà qui est balaise ! Il faut y penser et oser.
 
Je ne regarderai pas ce soir si ca peut être changé mais 
(test_iter  '(2 3 4 5) 2) me renvoie (2 3 4 -9) et cela ne me convient pas. Je reste avec des entiers positifs pour mon besoin.
 
 
[Edité le 17/11/2010 par Tramber]

[(gile)]

Tramber,

 

Pour ce que tu veux faire, nul besoin d'itérations ni de récursion :

(defun test (l s / a)
 (if (    (reverse (cons a l))
 )
)

 

Maintenant, on arrête de polluer le sujet de VDH-Bruno que j'applaudis encore pour ses progrès fulgurants :exclam:

[Tramber]

Oui, encore meilleur.

Mais je vais reprendre car j'ai des résultats qui ne me conviennent pas (je ne veux pas de chiffres négatifs et pour l'instant aucune routine ici-présente ne me convient).

Peut-être garderai-je la récursivité.

 

Pour faire au moins un peu le lien avec le sujet ! (J'ignorais que ma contribution deviendrait un sujet.)

Hopppla.

 

Désolé Bruno :cool:

[(gile)]

La dernière routine devrait être incomparablement plus rapide et ne retourne pas de valeurs négatives.

[Tramber]

Mon pauvre Bruno ! Le sujet se perd alors que j'aurais dû faire carrément un sujet !

 

La bonne nouvelle est que ce soir, avant la nuit porte-sommeil, je vais garder ma fonction récursive adaptée avec les conseils de (gile) pour les reverse :

 

(defun test(lst som /); (setq lst(reverse DECOUPFUT) som 32)
 (cond((	(setq lst(cons(1+(car lst))(cdr lst))
      lst(test lst som)))
      ((>(apply '+ lst)som)
(if(not(zerop(1-(car lst))))
  (setq lst(cons(1-(car lst))(cdr lst)))
  (setq lst(cdr lst)))
(setq lst(test lst som)))
      )
 lst)

 

(reverse(test(reverse '(3 4 5 6 7))9)) renvoie (3 4 2)

(reverse(test(reverse '(3 4 5 6 7))39)) renvoie (3 4 5 6 21)

 

Je me trompais pour les négatifs mais les fonctions proposées répondent nil dans le premier cas, au lieu de (3 4 2).

 

La moralité, c'est quand même, que de créer des petites fonctions récursives n'est pas si difficile (voir mon premier sujet, la construction mentale fût rapide).

A demain pour ...mieux !

et bonne nuit à tous :cool:

 

[Edité le 17/11/2010 par Tramber]

[(gile)]

Désolé VDH-Bruno, ton sujet est complètement détourné.

Tu peux peut-être redémarrer un nouveau sujet "Mécanique de la récursion" avec ton premier message et on renommera celui-là.

 

Tramber,

 

Il semble que tu te laisse aveugler par le désir d'utiliser un type de processus (récursion) et que donc tu ne vois pas l'essentiel : l'algorithme que tu veux implémenter relève de la "pré-arithmétique" en ce sens qu'il n'utilise pas (à part dans la somme de la liste à chaque appel) la soustraction ni l'addition de plus de 1 à la fois.

 

L'algorithme principal qu'implémente ta routine raconte à peu près ceci :

- je fais la somme de ce qu'il y a dans la liste,

- je compare le résultat avec une valeur donnée :

-- si le résultat est inférieur à la valeur : j'ajoute 1 au premier élément et je recommence au début

-- si le résultat est supérieur à la valeur : je recommence au début avec :

--- si le premier élément moins 1 est différent de 0 : la liste avec le premier élément moins 1

--- sinon la liste sans le premier élément

 

À partir de la dernière routine que je proposais, et en intégrant ce que tu veux comme retour en cas de résultat négatif, on peut utiliser un algorithme plus simple (et plus performant) parce qu'il n'est nécessaire de boucler (de manière itérative ou récursive) que dans ce dernier cas :

 

- si la différence entre la valeur et la somme des termes de la liste sauf le premier est positive : on retourne la liste en remplaçant le premier élément par cette différence

- sinon on recommence au début avec la liste privée du premier élément

 

(defun toto (l s / a)
 (if (    (cons a (cdr l))
   (toto (cdr l) s)
 )
)

 

(reverse (toto (reverse '(3 4 5 6 7)) 9)) retourne (3 4 2)

 

Un petit benchmark :

_$ (benchmark '((reverse (test (reverse '(3 4 5 6 7)) 9)) (reverse (toto (reverse '(3 4 5 6 7)) 9))))

Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

 

(REVERSE (TOTO (REVERSE (QUOTE (3 4 ...).....1357 / 4.00

(REVERSE (TEST (REVERSE (QUOTE (3 4 ...).....5429 / 1.00

 

Ces résultats s'expliquent clairement en faisant un suivi des deux routines :

(trace test toto)
(reverse (test (reverse '(3 4 5 6 7)) 9))
(reverse (toto (reverse '(3 4 5 6 7)) 9))

Saisie (TEST (7 6 5 4 3) 9)
 Saisie (TEST (6 6 5 4 3) 9)
   Saisie (TEST (5 6 5 4 3) 9)
     Saisie (TEST (4 6 5 4 3) 9)
       Saisie (TEST (3 6 5 4 3) 9)
         Saisie (TEST (2 6 5 4 3) 9)
           Saisie (TEST (1 6 5 4 3) 9)
             Saisie (TEST (6 5 4 3) 9)
               Saisie (TEST (5 5 4 3) 9)
                 Saisie (TEST (4 5 4 3) 9)
[10] Saisie (TEST (3 5 4 3) 9)
[11]   Saisie (TEST (2 5 4 3) 9)
[12]     Saisie (TEST (1 5 4 3) 9)
[13]       Saisie (TEST (5 4 3) 9)
[14]         Saisie (TEST (4 4 3) 9)
[15]           Saisie (TEST (3 4 3) 9)
[16]             Saisie (TEST (2 4 3) 9)
[16]             Résultat:  (2 4 3)
[15]           Résultat:  (2 4 3)
[14]         Résultat:  (2 4 3)
[13]       Résultat:  (2 4 3)
[12]     Résultat:  (2 4 3)
[11]   Résultat:  (2 4 3)
[10] Résultat:  (2 4 3)
                 Résultat:  (2 4 3)
               Résultat:  (2 4 3)
             Résultat:  (2 4 3)
           Résultat:  (2 4 3)
         Résultat:  (2 4 3)
       Résultat:  (2 4 3)
     Résultat:  (2 4 3)
   Résultat:  (2 4 3)
 Résultat:  (2 4 3)
Résultat:  (2 4 3)

Saisie (TOTO (7 6 5 4 3) 9)
 Saisie (TOTO (6 5 4 3) 9)
   Saisie (TOTO (5 4 3) 9)
   Résultat:  (2 4 3)
 Résultat:  (2 4 3)
Résultat:  (2 4 3) 

 

Et, bien sûr, si la somme des termes moins le premier est inférieure à la valeur il n'y qu'un seul appel

[Tramber]

Coucou,

 

J'ai fait beaucoup d'erreurs hiers soir dans mes tests je crois.

l'algorithme que tu veux implémenter relève de la "pré-arithmétique"

 

Il y a plein de dinosaures ici, ils n'ont pas honte !

 

J'ai voulu participer à ce sujet parce qu'il tombait complètemepnt par hasard sur le sujet de l'un de mes travaux du jour.

 

Ca donne une leçon qu'on a déjà eu plus d'une fois ici : il y a souvent moyen de faire plus simple ! et plus puissant. A propos du problème de pile, ta solution est logiquement plus robuste car l'écriture plus simple.

 

Désolé pour mes test hier, je commencais à fatiguer et à mélanger quelques pinceaux.

J'ai décidement toujours des progrès à faire dans la concision.

 

 

[Edité le 18/11/2010 par Tramber]

[(gile)]

Finalement, on ne s'éloigne pas tant du sujet, en tout cas on peut y revenir en se servant de cet exemple.

 

Cet exemple montre bien la primordiale importance de l'algorithmie (le choix du chemin à suivre pour arriver au résultat escompté) dans le processus d'élaboration d'un programme (ou d'une routine).

Ce choix devrait être le fruit d'une réflexion qui intervient avant même l'écriture de la première ligne de code parce que c'est lui qui détermine la structure du code (un processus récursif est-il pertinent ? par exemple) et sa future performance (la concision n'étant, à mon avis, qu'accessoire et ne concerne en général que l'auteur du code).

 

On voit bien dans cet exemple les effets induits par le choix d'un algorithme ou d'un autre : pour les même listes et valeurs : (3 4 5 6 7) et 9, 'test' provoque 16 appels quand toto n'en provoque que 3. ce qui aura des conséquences sur la vitesse d'exécution bien sûr, mais aussi sur les risques de dépassement de la pile : avec toto, la hauteur de la pile n'excèdera jamais la longueur de la liste.

 

Une fois l'algorithme choisi, il faut l'implémenter et c'est là qu'on peut revenir au le sujet de VDH-Bruno.

À ce moment là du processus, il peut être encore possible de choisir entre un processus itératif ou récursif, mais restons en à un processus récursif pour rester dans le sujet.

Si l'algorithme est clairement conçu/exprimé, il contient tous les ingrédients pour construire la fonction :

- les arguments

- type de la valeur de retour

- condition d'arrêt

- modification(s) des arguments à chaque appel récursif pour permettre finalement de remplir la condition d'arrêt.

 

Reprenons l'exemple ci dessus avec l'algorithme de 'test' (même s'il n'est pas très judicieux, il permet de mieux illustrer la "mécanique de la récursion") :

- je fais la somme de ce qu'il y a dans la liste,

- je compare le résultat avec une valeur donnée :

-- si le résultat est inférieur à la valeur : j'ajoute 1 au premier élément et je recommence au début

-- si le résultat est supérieur à la valeur : je recommence au début avec :

--- si le premier élément moins 1 est différent de 0 : la liste avec le premier élément moins 1

--- sinon la liste sans le premier élément

Tel quel, l'algorithme n'est pas très bien exprimé, il s'agit plus de la description d'une fonction déjà écrite (j'ai été obligé d'inverser le processus algorithmie -> implémentation pour le reconstituer) mais il permet d'extraire les ingrédients nécessaires :

- les arguments sont une liste d'entiers et un entier strictement positif

- la fonction doit retourner une liste dont la somme des éléments est égale à une valeur

- la condition d'arrêt n'apparaît qu'implicitement ici : aucune des conditions somme inférieure à la valeur ou somme supérieur à la valeur n'est remplie. autrement dit : la somme est égale à la valeur

- les modifications des arguments pour tendre vers la condition d'arrêt sont différentes suivant que la somme est inférieure ou supérieure à la valeur : on ajoute 1 au premier élément de la liste argument dans le premier cas, dans le second cas, si le premier élément moins 1 est strictement positif (autrement dit si le premier élément est supérieur à 1), on soustrait 1 à cet élément, sinon on le supprime de la liste.

 

En reprenant la méthodologie de VDH-Bruno, on pose :

1_ la fonction et ses arguments :

(defun test (lst som) ...)

2_ on ajoute la condition d'arrêt (avec utilisation de cond puis qu'il y a plus d'une condition à évaluer) et le retour si cette condition est remplie :

(defun test (lst som)
 (cond
   ((= (apply '+ lst) som) lst)
 )
)

3_ on ajoute les autres conditions contenant les appels récursif avec les modification d'argument

(defun test (lst som /)
 (cond
   ((= (apply '+ lst) som) lst)
   ((     (test (cons (1+ (car lst)) (cdr lst)) som)
   )
   ((> (apply '+ lst) som)
    (if (       (test (cons (1- (car lst)) (cdr lst)) som)
      (test (cdr lst) som)
    )
   )
 )
)

 

On peut ensuite essayer d'optimiser le code. Par exemple dans ce cas l'expression (apply '+ lst) peut être évaluée 2 ou 3 fois à chaque appel, il peut donc être judicieux de stocker le résultat de la première évaluation dans une variable locale qui sera utilisée lors des éventuelles autres évaluations. On peut aussi supprimer la dernière : si la somme n'est ni égale ni inférieure à la valeur, elle ne peut être que supérieure

 

(defun test (lst som / tmp)
 (cond
   ((= (setq tmp (apply '+ lst)) som) lst)
   ((     (test (cons (1+ (car lst)) (cdr lst)) som)
   )
   ((if (       (test (cons (1- (car lst)) (cdr lst)) som)
      (test (cdr lst) som)
    )
   )
 )
)

 

On peut aussi noter que tous les (setq lst ...) de la routine originelle ont disparus, il est en général inutile d'utiliser setq pour modifier les valeurs des arguments dans les processus récursifs.

[Tramber]

Là, c'est très intéressant parce que je m'y retrouve.

et ce que tu dis sur les SETQ est fondamental, l'air de rien.

 

Pour prendre une image béton (en l'honneur de VDH-Bruno), les laisser c'est comme ne pas enlever l'étaiement d'une dalle 28 jours après la coulée :D

 

Mais je reste impressionné par TOTO que tu as donné plus haut. C'est du précontraint !

 

Bravo à tous les deux.

[VDH-Bruno]

Bonsoir,

 

Merci à vous deux, car loin d’avoir pollué le sujet vous l’avez considérablement enrichie et (gile) en plus de ramener la discussion d’une main de maître en plein dans le sujet, à en prime livré une jolie démonstration sur la " primordiale importance de l'algorithmie",

 

Thème sur lequel je n’avais osé m’aventurer, c’est pourquoi en introduction j’avais limité mon sujet :

 

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)

 

Maintenant que la notion d’algorithme récursif a été abordé, j’essayerai d’enquiller (à l'occasion..) sur ce thème avec les quelques généralités que j’ai pu synthétiser, ainsi qu’une petite réflexion (qui me tient à cœur) sur la récursivité et sa soi-disant lenteur..

 

 

Tramber : Je suis heureux que mon post ait pu susciter ton intérêt, hé oui l’absence des SETQ (et donc des variables) c’est tous ce qui fait l’élégance et la concision du codage enveloppé.

Sinon enlever l’étaiement à 28 jours ça fait un peu bretelles et ceinture, tu ne trouve pas ?

 

(gile) Merci pour les applaudissements, ça m’encourage car c’est pas toujours évident de se motiver le soir pour bucher après une journée de travail, et même si jusqu’ici " les progrès sont fulgurants" c’est sur des points très très limités et pas encore suffisamment nombreux pour commencer à voir un réel retour sur investissement en terme de routines.

 

 

 

 

[Edité le 19/11/2010 par VDH-Bruno]

[(gile)]

Salut,

 

même si jusqu’ici " les progrès sont fulgurants" c’est sur des points très très limités et pas encore suffisamment nombreux pour commencer à voir un réel retour sur investissement en terme de routines.

 

Tu peux être certain que beaucoup ont écrit de nombreuses routines qui leur facilite le travail sans jamais avoir atteint le niveau de compréhension du LISP que tu as acquis.

 

Tu as compris les principes fondamentaux du LISP (et de la programmation fonctionnelle) : définition de fonctions, utilisation de fonctions comme argument (avec mapcar, apply, vl-sort, etc), fonctions anonymes, récursivité.

À mon avis, le reste n'est que du vocabulaire et de la programmation impérative (procédurale) autant dire des broutilles...

[Tramber]

Tu peux être certain que beaucoup ont écrit de nombreuses routines qui leur facilite le travail sans jamais avoir atteint le niveau de compréhension du LISP que tu as acquis.

 

Tu l'as dit Boofy ! Moi le premier. Je laisse(ais) encore les SETQ dans des récursives et sans honte !

Je m'accroche néanmoins et si je n'arrive pas à apprendre, je fais des efforts (parfois vain) pour me souvenir et me cultiver. J'invite tout un chacun à le faire aussi. Il y a de quoi dans ce forum maintenant !

Manque juste le temps :P

 

Sinon enlever l’étaiement à 28 jours ça fait un peu bretelles et ceinture, tu ne trouve pas ?

 

C'est bien le but. En effet, puisqu'à 28 jours elle est supposée décoffrée et possiblement en charge comme sous le calcul. J'ai forcé un peu sur le temps de prise et j'ai mis 28 jours comme un clin d'oeil. Comme je sais que tu connais le béton...

[Fraid]

Bonjour,

 

Je confirme le fait qu'il ne faut pas y connaitre grand chose pour réaliser des routines qui changent la vie.

 

Notament pour les mises à la charte graphique, puisque cela consiste généralement à selectionner des objets et changer leurs proprietées.

 

Et je voulais vous remercier pour nous prouver qu'Autocad n'est pas seulement un logiciel de DAO et une "plateforme" de développement, mais aussi un '(champ "expérimental").