Scheme

LA RÉCURSION TERMINALE

EXPÉRIENCE FONDAMENTALE




(DEFINE (FONCTION1 N)

  (DISPLAY N)

  (DISPLAY "  ")

  (+ 0 (FONCTION1 (+ N 1))))




(DEFINE (FONCTION2 N)

  (DISPLAY N)

  (DISPLAY "  ")

  (FONCTION2 (+ N 1)))

POUR LES DEUX FONCTIONS:
APPEL RÉCURSIF SANS TEST D'ARRÊT
==> BOUCLE INFINIE

MATHÉMATIQUEMENT, CES DEUX
FONCTIONS NE SONT PAS TRÈS
DIFFÉRENTES:
0 + X = X

INFORMATIQUEMENT, LEURS
COMPORTEMENTS SONT RADICALEMENT
DIFFÉRENTS !!!!!

LES OPÉRATIONS NE PEUVENT S'EFFECTUER QUE QUAND ELLES ONT LA VALEUR DE LEURS 2 ARG.
--> ELLES SONT MISES EN ATTENTE DANS UNE PILE (STACK)

--> AUCUNE OPÉRATION N'EST MISE EN ATTENTE
Exemple avec et sans pile (programme : terminale.drs)
LA DEUXIÈME RÉCURSION EST DITE TERMINALE
(= TERMINE NORMALEMENT)
LA PREMIÈRE EST NON TERMINALE
(= BLOQUÉE PAR "OUT OF MEMORY")

POUR DES RÉCURSIONS AVEC PLUSIEURS MILLIERS D'ÉTAPES ( > 157.000), IL EST INDISPENSABLE D'ÉCRIRE DES RÉCURSIONS TERMINALES

CRITÈRE:
POUR VÉRIFIER QU'UNE FONCTION EST RÉCURSIVE TERMINALE:

ON REGARDE LA DÉFINITION

ON CHERCHE L'APPEL RÉCURSIF

S'IL Y A DES OPÉRATIONS EN ATTENTE DEVANT L'APPEL RÉCURSIF
--> NON TERMINAL
SINON
--> TERMINAL

COMMENT ÉCRIRE DES RÉCURSIONS TERMINALES ????

TECHNIQUE:
POUR ÉVITER QUE DES OPÉRATIONS RESTENT EN ATTENTE DEVANT L'APPEL RÉCURSIF,
--> IL FAUT METTRE CES OPÉRATIONS A L'INTÉRIEUR DE L'APPEL RÉCURSIF
. . .
. . . SUR UNE VARIABLE !!!

L'EXEMPLE DE FACTORIEL



(DEFINE (FACT N)

  (COND ((= N 0) 1)

        (ELSE (* N (FACT (- N 1)))))) 

        ; --> CALCUL EN ATTENTE

VERSION TERMINALE:



(DEFINE (FACT-TERMINALE N  X)

  (COND ((= N 0) X)

        (ELSE (FACT-TERMINALE (- N 1) (* N X)))))

            ; --> CALCUL SUR VARIABLE X

LANCEMENT:
(FACT-TERMINALE N 1)
--> INITIALISATION X=1

ATTENTION:
TEST D'ARRET DANS UNE RÉCURSION TERMINALE
--> DONNER LA VARIABLE QUI CONTIENT LE RÉSULTAT DU CALCUL

STRUCTURE DE BLOC



(DEFINE (FACT N)


 (DEFINE (FACT-TERMINALE N X)

  (COND ((= N 0) X)

        (ELSE (FACT-TERMINALE (- N 1) (* N X))))) 

 
  (FACT-TERMINALE N 1)) ;LANCEMENT SOUS-PROGRAMME

ATTENTION: LES DEFINE AUXILIAIRES NE PEUVENT APPARAÎTRE QU'EN TÊTE DU CORPS D'UNE FONCTION !!!!
X : VARIABLE DE CALCUL
--> LE DEFINE AUXILIAIRE (SOUS-PROGRAMME) INTRODUIT DES VARIABLES CACHÉES DANS LA FONCTION PRINCIPALE

N : COMPTEUR DÉCROISSANT
--> ON PEUT UTILISER UN COMPTEUR CROISSANT


(DEFINE (FACT N)


 (DEFINE (AUX K X)

  (COND ((> K N) X)

        (ELSE (AUX (+ K 1) (* K X)))))

 
  (AUX 1 1)) ;LANCEMENT SOUS-PROGRAMME

UN EXEMPLE SUR LES LISTES

(IOTA 5)
--> (5 4 3 2 1)


(DEFINE (IOTA N)

(COND ((= N 0) ())

      (ELSE (CONS N (IOTA (- N 1))))))

MEME PROBLEME QUE POUR FACTORIEL:
(CONS N ...) EN ATTENTE A LA PLACE DE (* N ...)
```
(DEFINE (FACT N)

   (COND ((= N 0) 1)

         (ELSE (* N (FACT (- N 1)))))) 




(DEFINE (IOTA N)

  (DEFINE (AUX N RES)

    (COND ((= N 0) RES) ;RESULTAT DU CALCUL

          (ELSE (AUX (- N 1) (CONS N RES)))))

  (AUX N ()))
```
--> LA LISTE APPARAIT SOUS FORME INVERSÉE !!!
POUR FABRIQUER (5 4 3 2 1) :

UTILISER REVERSE DANS LE TEST D'ARRÊT
(REVERSE RES) AU LIEU DE RES

UTILISER UN COMPTEUR EN SENS INVERSE --> CROISSANT

Scheme