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