Précédent Suivant

  Schémas de récursion et fonctions

 

 
Le schéma général de récursion sur les listes avait été ainsi énoncé:
 
(define (f L)
  (if (pair? L)
      (compose (car L) (f (cdr L)))
      fin ) ) 

La précédente définition peut se verbaliser ainsi: soit f la fonction récursive, elle teste si son argument est une liste non vide auquel cas on compose le premier élément de la liste avec le résultat de la récursion appliquée au reste de la liste. Si, en revanche, l'argument de f est vide alors une valeur finale fin est imposée.
 
Les parties en italiques marquaient les endroits où insérer des expressions calculant ce qui est nécessaire. Ainsi la fonction qui somme les nombres d'une liste s'écrit-elle suivant ce schéma comme:
 

;;; somme: LISTE[Nombre] ® Nombre 
;;; (somme L) calcule la somme des termes de L. 
 
(define (somme L)
  (if (pair? L)
      (+ (car L) (somme (cdr L)))
      0 ) ) 

Ainsi compose est-il + et fin est-il 0 dans le cas de somme. Mais on peut directement écrire, en Scheme même, le schéma récursif, en supposant que compose et fin sont deux variables correctement définies:
 

(define (f L)
  (if (pair? L)
      (compose (car L) (f (cdr L)))
      fin ) ) 

Et, pour donner une valeur correcte à compose et fin, on écrira la fonction schema-recursion qui prend en argument les valeurs de compose et fin et qui calcule la fonction récursive définie par le schéma de récursion sur liste et les valeurs des variables compose et fin:
 

;;; schema-recursion: (a×b®bb®(LISTE[a]®b) 
;;; (schema-recursion compose fin) calcule une fonction unaire effectuant 
;;; une récursion sur son argument (de type liste). Quand la liste 
;;; sera vide, la valeur sera fin; dans le cas général, on compose la 
;;; valeur du premier élément de la liste avec le résultat de la 
;;; fonction récursive appliquée au reste de la liste. 
 
(define (schema-recursion compose fin)
  (define (f L)
    (if (pair? L)
        (compose (car L) (f (cdr L)))
        fin ) )
  f ) 

Ainsi, avec ce schéma récursif traduit en une fonction, peut-on dire que la fonction somme explicitement définie récursivement ci-dessus se réécrit, sans récursion apparente, en:
 

(schema-recursion + 0) 

Incidemment, la fonction schema-recursion est un exemple de fonction utilisant une sous-fonction interne et calculant un résultat fonctionnel: la fonction récursive définie par le schéma.
 
Montrons, par un calcul explicite n'utilisant que des substitutions, ce que vaut ((schema-recursion + 0) '(3 4 5)). Chaque fois qu'une fonction est appelée, on substitue ses arguments à ses variables dans son corps.
 

((schema-recursion + 0) '(3 4 5))
(f '(3 4 5)) avec (define (f L)
                    (if (pair? L)
                        (+ (car L) (f (cdr L)))
                        0 ) )
(if (pair? '(3 4 5)) (+ (car '(3 4 5)) (f (cdr '(3 4 5)))) 0)
(+ (car '(3 4 5)) (f (cdr '(3 4 5))))
(+ 3 (f '(4 5))
(+ 3 (if (pair? '(4 5)) (+ (car '(4 5)) (f (cdr '(4 5)))) 0))
(+ 3 (+ (car '(4 5)) (f (cdr '(4 5)))))
(+ 3 (+ 4 (f (cdr '(5)))))
(+ 3 (+ 4 (if (pair? '(5)) (+ (car '(5)) (f (cdr '(5)))) 0)))
(+ 3 (+ 4 (+ 5 (f (cdr '(5))))))
(+ 3 (+ 4 (+ 5 (f '()))))
(+ 3 (+ 4 (+ 5 (if (pair? '()) (+ (car '()) (f (cdr '()))) 0))))
(+ 3 (+ 4 (+ 5 0)))
(+ 3 (+ 4 5))
(+ 3 9)
12 

En résumé, les schémas de récursion peuvent être directement programmés en Scheme et le modèle à substitution est suffisant pour expliciter leur évaluation.




Précédent Suivant