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 soyions 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 exécutez (affiche-entiers-descendants 5), vous obtiendrez :

5
4
4
2
1
0
-1
-2
-3
-4
-5
-6
-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é :

guile> (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" . ())))))

Guile détecte automatiquement les paires imbriquées dans cette configuration et les affiche 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.

guile> '(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é))))

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\) 1 :

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

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

Ce cas étant très fréquent, on dispose d’une syntaxe plus simple, le named let. La voici :

(let fonction ((argument1 init1)
               (argument2 init2)
               ...)
  ...)

Il s’agit d’une sorte de mélange entre let et define. Le named let évalue les expressions init1, init2, etc., et les affecte à argument1 et consorts, exactement comme un let. Mais ce faisant, il définit aussi fonction, qui peut être appelée à l’intérieur du let avec d’autres paramètres. En d’autres termes, cette syntaxe est équivalente à :

(define (fonction argument1 argument2 ...)
  ...)
(fonction init1 init2 ...)

Notre fonction puissance réécrite avec un named let 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. 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)))))

1

Il s’agit d’un algorithme naïf, avantageusement supplanté par l'exponentiation rapide.