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:
;;;
;;;
(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:
;;;
;;;
;;;
;;;
;;;
;;;
(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.