Récursivité

Si vous avez suivi ce tutoriel jusqu’ici, vous avez pu vous demander quand viendraient les boucles. En effet, dans les langages dits impératifs (dont font partie l’écrasante majorité des langages très populaires comme Python, C, C++, Java, PHP, etc.), il existe presque toujours deux types de boucles, while et for. Même si ces boucles existent bien en Scheme, sous des formes édulcorées, elles sont très rarement utilisées. En effet, Scheme est un langage de type fonctionnel, et la manière courante d’itérer des opérations est plutôt de définir des fonctions dites « récursives ». À la place d’une bête boucle for, on écrira donc une « fonction auxiliaire récursive terminale avec accumulateur », ce qui peut paraître barbare, mais ne doit pas effrayer.

Principe de la récursivité

Essayons d’écrire une fonction qui prend un paramètre \(n\) et affiche les entiers de \(n\) à 0 en descendant. En Python par exemple, on écrirait :

def affiche_entiers_descendants(n):
    for i in reversed(range(n+1)):
        print(i)

En Scheme, bien qu’il existe des équivalents lointains au for, on pense différemment. Mettons que nous soyons bloqués, et commencions un peu bêtement par afficher le premier de ces entiers.

(define (affiche-entiers-descendants n)
  (display n) (newline)
  ???)

Il nous reste à afficher les entiers de \(n-1\) à 0. Mais… on dispose d’une fonction pour cela ! C’est notre fonction affiche-entiers-descendants. Essayons :

(define (affiche-entiers-descendants n)
  (display n) (newline)
  (affiche-entiers-descendants (1- n)))

(Si vous l’avez oubliée, la procédure 1- est mentionnée dans le chapitre Expressions.)

Si vous exécutez (affiche-entiers-descendants 5), vous obtiendrez :

⊨ 5
⊨ 4
⊨ 3
⊨ 2
⊨ 1
⊨ 0
⊨ -1
⊨ -2
⊨ -3
⊨ -4
⊨ -5
⊨ -6
⊨ x-7
...

En effet, notre fonction s’appelle elle-même, et il n’y a aucune raison que cela s’arrête. En réalité, nous avons oublié un détail. Si \(n\) vaut \(0\), il ne faut pas continuer, car on afficherait \(-1\) alors que nous voulions nous arrêter à \(0\). Il faut donc ajouter une condition, qui permettra que l’exécution de notre fonction ne continue pas indéfiniment :

(define (affiche-entiers-descendants n)
  (display n) (newline)
  (if (not (= n 0))
      (affiche-entiers-descendants (1- n))))

Cette fois-ci, on obtient bien le résultat souhaité :

(affiche-entiers-descendants 5)
⊨ 5
⊨ 4
⊨ 3
⊨ 2
⊨ 1
⊨ 0

Une fonction récursive est donc une fonction qui s’appelle elle-même. La récursivité est un cas de la technique dite « diviser pour régner », qui consiste à résoudre un problème en le « cassant » en plusieurs problèmes plus petits, puis en rassemblant les morceaux. En l’occurrence, le problème « afficher les entiers de \(n\) à \(0\) » a été séparé en « afficher \(n\) » et « afficher les entiers de \(n-1\) à \(0\) ». Le premier est facile à résoudre, et le deuxième se résout en utilisant exactement la même technique. Il faut toujours penser aux cas de base, les plus petites instances du problème, ici le cas \(n = 0\), afin que la récursion ne soit pas infinie.

Retour sur les listes

Il est temps de révéler le secret des listes Scheme.

Les listes n’existent pas.

Elles n’existent tout simplement pas ! Il n’y a que des paires.

Imaginons que nous voulions caser les éléments de la liste '(0 1 2 3 "Bonjour") dans une paire. Bêtement (mais en fait intelligemment, comme dans l’exemple précédent), nous allons commencer par mettre le premier élément dans le car de la paire.

'(0 . ???)

Il nous reste quatre éléments, mais plus que le cdr pour les stocker. Là intervient l’idée géniale. Il suffit de les mettre… dans une nouvelle paire !

'(0 . (??? . ???))

Dans cette paire, nous avons de la place pour un nouvel élément, dans le car.

'(0 . (1 . ???))

À nouveau, le cdr sera une paire, dont le car sera l’élément suivant.

'(0 . (1 . (2 . ???)))

On continue :

'(0 . (1 . (2 . (3 . ("Bonjour" . ???)))))

Tous les éléments de notre liste ont trouvé une place dans le car d’une paire. Reste le cdr de la dernière paire à remplir. Il correspond au cas de base, qui est celui d’une liste à 0 élément. C’est tout simplement la liste vide, '(). Finalement, on obtient :

'(0 . (1 . (2 . (3 . ("Bonjour" . ())))))

Les paires imbriquées dans cette configuration sont automatiquement détectées et affichées sous forme de listes. En réalité, ce ne sont que des paires. Les listes n’existent que par convention, comme paires de paires de paires etc.

'(0 . (1 . (2 . (3 . ("Bonjour" . ())))))
⇒ (0 1 2 3 "Bonjour")

Une liste est donc une paire. Son car est son premier élément. Son cdr est la liste des éléments restants. Le cas particulier est celui de la liste vide, '(), qui n’est pas une paire. C’est tout simplement une constante, qui peut être comparée avec eq? tout comme les symboles. Cette définition des listes est récursive, puisqu’une liste est soit la liste vide, soit une paire d’un élément et d’une liste. Elle est naturellement adaptée à l’écriture de fonctions récursives.

Prenons par exemple la fonction filter, et implémentons-la sous forme d’une fonction récursive filter2, dont les paramètres seront fonction (la fonction qui dit si un élément est à garder ou non) et liste (la liste à filtrer).

• Si liste est la liste vide, filter2 renverra évidemment la liste vide. Nous avons notre cas de base.

• Sinon, liste est une paire de son premier élément et de la liste des suivants. On peut commencer par appliquer le filtrage à la liste des suivants, c’est le problème plus petit. Ensuite, on appelle fonction sur le premier. Si fonction renvoie #t (ou une valeur vraie), on rajoute l’élément à la liste des suivants filtrée. Sinon, on ne l’ajoute pas. Ainsi, on a résolu le problème plus grand à partir du problème plus petit.

Le code sera :

(define (filter2 fonction liste)
  (if (null? liste)
      '()
      (let* ((premier (car liste))
             (reste (cdr liste))
             (reste-filtré (filter2 fonction reste)))
        (if (fonction premier)
            (cons premier reste-filtré)
            reste-filtré))))

(filter2 even? '(0 1 2 3 4 5))
⇒ (0 2 4)

Remarquez que le test (eq? liste '()) est si fréquent qu’il peut s’abréger en (null? liste).

Récursivité terminale

Cette partie n’est pas strictement nécessaire pour la programmation courante, mais sera profitable à qui cherche à comprendre la programmation fonctionnelle, ou à écrire du code efficace.

Intéressons-nous au calcul de puissances. Si vous vous rappelez de lointains cours de mathématiques, l’entier \(a^n\) est défini par \(\underbrace{a \times a \times \cdots \times a}_\text{n fois}\).

Voici une fonction Python qui, grâce à une boucle for, calcule \(a^n\). (NB : Il s’agit d’un algorithme naïf, avantageusement supplanté par l’exponentiation rapide.)

def puissance(a, n):
    résultat = 1
    for i in range(n):
        résultat = résultat*a
    return résultat

En Scheme, nous allons essayer à nouveau de « casser » le problème. Pour cela, on remarque que si on a déjà calculé \(a^{n-1}\), il suffit de multiplier une dernière fois par \(a\) pour obtenir \(a^n\). Ceci se voit sur la définition : \(a^n = \underbrace{a \times a \times \cdots \times a \times a}_\text{n fois} = \underbrace{a \times a \times \cdots \times a}_\text{n-1 fois} \times a\). Le cas de base est ici \(a^0 = 1\), ce qui correspond à l’initialisation à 1 de la variable résultat dans la fonction Python. La fonction Scheme récursive est donc :

(define (puissance a n)
  (if (= n 0)
      1
      (* a (puissance a (1- n)))))

Il y a cependant un problème caché mais important. Notre fonction Scheme est très nettement plus gourmande en mémoire que la fonction Python. D’après mes tests, Calculer \(2^{300\,000}\) demande environ 10 MiB de mémoire pour la fonction Python, 40 MiB avec notre fonction Scheme.

Afin de comprendre pourquoi, il faut se représenter la manière dont la fonction puissance est exécutée. Prenons l’exemple de l’appel (puissance 2 5).

• On entre dans l’appel (puissance 2 5). Puisque \(5 \neq 0\), l’expression renvoyée sera (* 2 (puissance 2 4)).

• On continue avec (puissance 2 4), qui appelle (puissance 2 3).

• Ainsi de suite jusqu’à (puissance 2 1), qui appelle (puissance 2 0).

• (puissance 2 0) renvoie 1, qui est passé à (puissance 2 1).

• (puissance 2 1) a obtenu tout ce qu’il fallait pour terminer et renvoie 2.

• Ainsi de suite jusqu’à (puissance 2 4).

• (puissance 2 4) renvoie 16 à (puissance 2 5), qui multiplie le résultat par 2 et renvoie finalement 32.

En arrivant à l’appel (puissance 2 0), l’ordinateur devait se souvenir de tous les appels précédents, car ils n’étaient pas encore terminés. Par conséquent, la pile d’appels a grandi pour contenir jusqu’à 5 appels, avant de décroître et de revenir à une taille 0. Si nous avions pris \(n = 300\,000\), la pile serait parvenue à une taille de \(300\,000\). Au contraire, le programme Python n’a qu’une boucle for. La pile ne grandit jamais.

Ce problème de la taille de la pile d’appels n’est peut-être pas si important que cela en Guile 2.2, puisqu’il ne s’agit que d’un peu de mémoire utilisée en plus. Cependant, il se pose avec acuité en Guile 1.8, ou bien dans d’autres langages fonctionnels. (Relire Pourquoi Scheme ? pour savoir quelle est votre version de Guile.) En effet, en raison de la manière dont la pile d’appels est souvent implémentée, sa taille est souvent très limitée. Ainsi, en Guile 1, cette fonction puissance ne sera pas capable de calculer \(a^n\) pour \(n\) au-delà de quelques dizaines de milliers. Pire, elle provoquera probablement une erreur sans aucune information quant à sa cause, comme « Segmentation fault (core dump) », ou bien, dans Frescobaldi, « Arrêté avec le code de retour 11 ».

Notre premier programme récursif ne présentait pas ce problème. Pour comprendre pourquoi, il faut observer la place de l’appel récursif.

(define (affiche-entiers-descendants n)
  (format #t "~a\n" n)
  (if (not (= n 0))
      (affiche-entiers-descendants (1- n))))

Lorsque l’exécution de affiche-entiers-descendants atteint l’appel à la fonction affiche-entiers-descendants elle-même, il n’y a plus rien d’autre à faire. Donc, il n’y a aucun intérêt à conserver l’appel dans la pile d’appels. Pensez à l’accueil d’une administration pénible qui vous demanderait : « demandez le formulaire au secrétariat du troisième étage et revenez me voir ». Supposons que le secrétariat du troisième étage vous demande à son tour d’aller au service du sixième étage et de revenir, puis que le service du sixième étage, une fois encore, vous envoie au couloir de direction au huitième étage et de revenir ensuite. Lorsque vous arrivez au couloir de direction, vous devez vous rappeler des numéros des bureaux visités pour tamponner le document que vous obtiendrez de la direction au service du sixième étage, puis au secrétariat du troisième étage avant de retourner finalement à l’accueil au rez-de-chaussée. Si, au contraire, chaque personne vous demande d’aller voir ailleurs, sans revenir, vous n’avez besoin de vous rappeler de rien. La direction au huitième étage vous fournira le document, et vous pourrez sortir, en ayant éventuellement déjà oublié que c’était le service numéro 40B du sixième qui vous avait envoyé là, sur demande du secrétariat 26 du troisième où vous avait conseillé de vous rendre l’accueil du rez-de-chaussée.

Cette récursion intelligente est dite récursion terminale. Elle se produit lorsqu’une fonction termine son exécution en renvoyant la valeur de retour d’une autre fonction. L’interpréteur peut alors oublier cet appel, passer à l’autre fonction et renvoyer sa valeur directement. Le fait que l’appel soit oublié signifie en termes techniques que l’entrée qu’il occupait sur la pile d’appels est simplement remplacée par une nouvelle entrée, au lieu qu’une nouvelle entrée s’ajoute par dessus. Par conséquent, la pile d’appels reste au même niveau au lieu de grossir. La spécification de Scheme commande que toutes les implémentations doivent optimiser le cas de la récursion terminale.

Nous allons donc chercher à transformer le code de notre fonction puissance pour que la récursion devienne terminale. Regardons-le droit dans les yeux :

(define (puissance a n)
  (if (= n 0)
      1
      (* a (puissance a (1- n)))))

Le but est de se passer de la multiplication par a du résultat de puissance. Comme il faut bien multiplier par a quelque part, l’idée va être de le faire avant d’appeler puissance, et d’incorporer cette multiplication à l’intérieur de l’appel à puissance. Au lieu de demander la valeur de \(a^{n-1}\) et de la multiplier par \(a\), la fonction va multiplier par \(a\) un résultat partiel, et passer ce résultat partiel à l’appel suivant.

(define (puissance-partielle a n r)
  (if (= n 0)
      r
      (puissance-partielle a
                           (1- n)
                           (* a r))))

Cette fonction puissance-partielle prend un argument supplémentaire, r, qui est notre résultat partiel, nommé accumulateur. Lorsque la fonction constate que \(n\) est parvenu à 0, elle peut mettre fin au cycle d’appels et renvoyer l’accumulateur. Sinon, elle s’appelle elle-même, de manière terminale, ce qui est tout l’objectif. Le paramètre a ne change pas, n baisse de 1 puisque l’on a effectué une itération de plus, et r est multiplié par a.

Comme la fonction attendue par l’utilisateur ne prend que deux arguments, a et n, on termine le code par une fonction puissance qui se contente d’appeler puissance-partielle en passant 1 pour r (le cas de base).

(define (puissance a n)
  (puissance-partielle a n 1))

La fonction puissance s’aide bien d’une fonction auxiliaire récursive terminale avec accumulateur.

Cependant, la fonction puissance-partielle ne sert qu’à la fonction puissance. Tout compte fait, on préfère la définir à l’intérieur même de puissance. Ainsi, il n’y a pas besoin de répéter le paramètre a. Pour éviter d’avoir deux n différents dans la fonction, mieux vaut renommer le paramètre n de puissance-partielle en i.

(define (puissance a n)
  (define (puissance-partielle i r)
    (if (= i 0)
        r
        (puissance-partielle (1- i)
                             (* a r))))
  (puissance-partielle n 1))

Syntaxe avec let nommé

Il est fréquent de définir une fonction auxiliaire récursive (avec de préférence une récursivité terminale). La plupart du temps, la fonction n’est appelée qu’une fois, juste après avoir été définie. C’est pourquoi Scheme fournit une syntaxe plus simple pour ce cas, le let nommé (named let). Il s’agit d’une sorte de mélange entre let et define. Avant d’introduire cette syntaxe, remarquons d’abord qu’une expression let est en fait un raccourci pour un appel de fonction. Il y a équivalence entre

(let ((variable1 valeur1)
      (variable2 valeur2)
      ...)
  expressions ...)

et

(define (fonction-du-let variable1 variable2 ...)
  expressions ...)
(fonction-du-let valeur1 valeur2 ...)

Pour comprendre, il faut modifier son point de vue sur la construction let. Certes, c’est un moyen de poser des variables, pour les réutiliser dans une série d’expressions. Mais on peut aussi voir ces expressions qui se trouvent dans le corps du let comme un calcul qui dépendrait de paramètres, les variables posées dans le let. C’est ce que traduit la transformation ci-dessus. La fonction fonction-du-let contient toutes les expressions, qui peuvent éventuellement utiliser les variables du let. Ces variables sont passées comme des paramètres de fonction. Le fait d’invoquer ce calcul avec les valeurs données pour les variables se traduit par l’appel de la fonction avec ces valeurs.

(Notez que je mens très légèrement en disant que ces deux formes sont équivalentes car define n’est pas valable partout, voir Variables locales.)

Jusqu’ici, cette transformation a l’air d’un délire de théoriciens. (De fait, elle a une grande importance dans la théorie, car c’est exclusivement avec des fonctions lambda que l’on peut utiliser des variables dans le lambda-calcul, le formalisme sur lequel est fondé Scheme à l’origine.) Néanmoins, il est plus facile d’assimiler le let nommé si on l’a comprise. En effet, le let nommé vous permet, dans les expressions qui forment le corps du let, d’appeler la fameuse fonction sur d’autres paramètres. Voici la syntaxe :

(let nom-fonction ((variable1 valeur1)
                   (variable2 valeur2)
                   ...)
  expressions ...)

Cette forme du let s’évalue comme un let normal, mais avec une possibilité en plus. À l’intérieur du let, la variable nom-fonction est liée à la fonction qui se trouverait dans l’autre manière d’écrire le let avec un define. Tout à l’heure, le nom fonction-du-let était arbitraire, et implicitement, on n’imaginait pas qu’il puisse être réutilisé à l’intérieur de la fonction elle-même. Avec un let nommé, cela devient possible, en écrivant le nom que l’on veut pour cette fonction au début du let avant les variables. Dans l’exemple ci-dessus, ce nom est nom-fonction. Cet let serait traduit par

(define (nom-fonction variable1 variable2 ...)
  expressions ...)
(nom-fonction valeur1 valeur2 ...)

Ainsi, dès que vous avez une fonction auxiliaire récursive et que vous la définissez seulement pour l’appeler directement, vous pouvez utiliser le let nommé. Pour rappel, la dernière version de notre fonction puissance était :

(define (puissance a n)
  (define (puissance-partielle i r)
    (if (= i 0)
        r
        (puissance-partielle (1- i)
                             (* a r))))
  (puissance-partielle n 1))

Réécrite avec un let nommé, cette fonction devient :

(define (puissance a n)
  (let puissance-partielle ((i n)
                            (r 1))
    (if (= i 0)
        r
        (puissance-partielle (1- i)
                             (* a r)))))

C’est le style idiomatique de Scheme.

Pour conclure, voici une nouvelle implémentation de filter, cette fois-ci avec récursivité terminale, et écrite à l’aide d’un let nommé. L’accumulateur est construit en ajoutant des éléments en tête avec cons, il faut donc le renverser juste avant de le renvoyer.

(define (filter3 fonction liste)
  (let boucle ((reste liste)
               (accu '()))
    (if (null? reste)
        (reverse accu)
        (boucle (cdr reste)
                (if (fonction (car reste))
                    (cons (car reste)
                          accu)
                    accu)))))