Aller au contenu

Note

Roadmap :

  • finir l'écriture.

La récursivité

Principe et exemples

On dit qu'une fonction est récursive lorsqu'elle va s'appeler elle-même lors de son exécution. Le plus souvent, cet appel sera directement visible depuis le corps de la fonction.

Par exemple, la fonction fact suivante permettant de calculer \(n!\) est récursive :

let rec fact n =
    if n = 0
    then 1
    else n * fact (n-1)

int fact(int n)
{
    if (n == 0)
    {
        return 1;
    }
    else
    {
        return n * fact(n-1);
    }
}

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n-1)

On utilise ici un exemple mathématique pour la simplicité des fonctions écrites. En effet, on ne voit rien d'autre dans fact que ces appels récursifs et ils correspondent directement à la définition mathématique :

\[ n! = \begin{cases} 1 & \text{ si } n = 0 \\ n \times (n-1)! & \text{ sinon.} \end{cases} \]

Remarque

En fait, la définition mathématique se fait plutôt en posant :

\[ 0! = 1 \qquad (n+1)! = (n+1) \times n! \]

Donc, pour retraduire une telle définition en tant que fonction, il est souvent nécessaire de décaler les rangs.

On remarque tout de suite deux choses :

  • il y a une valeur, \(n = 0\), pour laquelle on ne fait aucun appel
  • dans les autres cas, quand on fait un appel, l'argument \(n-1\) diminue strictement.

Cela permet d'être sûr que, pour un argument \(n \ge 0\), la suite des appels s'arrête : les arguments successifs \(n, n-1, \dots\) forment une suite strictement décroissante d'entiers naturels, qui ne peut donc pas être infinie, et elle s'arrête quand on atteint \(0\). Attention, pour \(n < 0\), on n'atteint jamais le cas de base et fact n ne termine pas (en pratique, la pile d'exécution déborde). On verra dans la suite comment on peut s'en assurer pour des fonctions plus complexes.

Quand on évalue fact 5 on va effectuer une série d'appels :

Appels récursifs de fact 5 jusqu'au cas de base, puis remontée des valeurs Appels récursifs de fact 5 jusqu'au cas de base, puis remontée des valeurs
Appels récursifs de fact 5 jusqu'au cas de base, puis remontée des valeurs

Pour calculer la valeur il faut descendre le long des appels récursifs jusqu'à tomber sur un cas de base puis remonter.

Implémentation pratique

Que se passe-t-il quand on appelle une fonction ?

Le principe de définition et d'appels de fonctions est à la base de la programmation structurée : au lieu d'avoir une longue succession d'instructions ou d'expressions, on les regroupe au sein de fonctions pour s'organiser. Cela permet également de factoriser du code : au lieu de dupliquer, on regroupe le même code au sein d'une fonction.

La question qu'on se pose ici est celle du mécanisme permettant une telle exécution du code. On pourrait naïvement penser qu'appeler une fonction serait absolument équivalent à copier son corps, c'est-à-dire que le programme

def f(x):
    y = x * x
    return x + y

a = 3
b = f(a)
print(b)

serait équivalent à

a = 3
# Début de f
x = a
y = x * x
# Fin de f et valeur de retour
b = x + y
print(b)

Au début de l'informatique, c'était effectivement la manière dont on appelait les fonctions. Mais on peut se rendre compte facilement du problème en changeant les noms de variables : le programme

def f(x):
    a = x * x
    return x + a

a = 3
b = f(a)
print(b)

deviendrait

a = 3
# Début de f
x = a
a = x * x
# Fin de f et valeur de retour
b = x + a
print(b)

Ici, l'appel de la fonction a changé la valeur de a (qui vaut 9 après l'appel) car a était aussi une variable définie dans f. Il est nécessaire d'avoir un mécanisme sophistiqué permettant de sauvegarder le contexte d'exécution d'une fonction et de le restaurer quand l'appel à une fonction est terminé.

Comme les fonctions vont elles-mêmes appeler d'autres fonctions, on ne peut pas se contenter de ne garder qu'un seul contexte. La bonne solution est d'utiliser ce qu'on appelle une pile d'exécution. Avant d'évaluer une fonction, on empile son contexte sur la pile, quand elle a terminé, on le dépile. On reverra plus tard la structure de données pile mais, pour le moment, on peut se l'imaginer comme une pile d'assiettes à laver : au départ, elle est vide. Chaque fois qu'on empile une assiette, elle grandit. Quand on veut laver une assiette, on prend nécessairement la dernière assiette empilée.

Un exemple

Si on considère le programme :

def f():
    return 4

def g(x):
    v = x+f()
    return v

def h(x):
    v = g(x+1) ** 2
    return v

print(h(3))

Il va s'exécuter ainsi :

  • Au départ la pile d'exécution est vide :

  • Ligne 12 : on appelle h, on crée donc sur la pile une entrée pour h.

  • Ligne 9 : on appelle g depuis h, on crée donc sur la pile une entrée pour g. On remarque notamment que x n'aura pas le même sens et la même valeur dans g que dans h.

  • Ligne 5 : on appelle f, on crée donc sur la pile une entrée pour f.

  • Ligne 2 : on sort de f en renvoyant la valeur 4. On dépile ainsi l'environnement de f.

  • Ligne 5 : on définit une variable v locale à g avec la valeur x + 4, où 4 est la valeur de retour de f, soit 8.

  • Ligne 6 : on sort de g en renvoyant la valeur 8. On dépile ainsi l'environnement de g.

  • Ligne 9 : on définit une variable v locale à h avec la valeur de retour de g élevée au carré, soit 64 :

  • Ligne 10 : l'appel de h est fini, on le dépile.

  • Ligne 12 : on a récupéré la valeur de retour 64, on l'affiche avec un appel à print (qui sera aussi empilé).

Pour une fonction récursive

Le mécanisme mis en place est suffisamment robuste pour permettre à une fonction de s'appeler elle-même. En effet, le fait d'avoir bien séparé les environnements d'exécution assure qu'il n'y aura pas de problèmes.

Si on reprend l'exemple vu au-dessus de l'évaluation de \(5!\), on remarque que lorsqu'on descend le long des appels, on empile, et lorsqu'on remonte, on dépile.

Programmer en récursif

Pour écrire une fonction récursive, on raisonne comme pour une preuve par récurrence : on suppose qu'on sait résoudre le problème sur des instances plus petites et on cherche à en déduire la solution de l'instance courante. Il faut alors :

  • traiter directement un ou plusieurs cas de base, pour lesquels on ne fait aucun appel ;
  • dans les autres cas, se ramener à des instances strictement plus petites, en un sens qu'il faudra préciser.

Exemple

On veut calculer \(x^n\) pour un entier \(n \ge 0\). La définition \(x^0 = 1\) et \(x^n = x \times x^{n-1}\) donne directement une fonction récursive similaire à fact. Mais on peut aussi remarquer que

\[ x^n = \begin{cases} 1 & \text{ si } n = 0 \\ \left(x^{\lfloor n/2 \rfloor}\right)^2 & \text{ si } n \text{ est pair} \\ x \times \left(x^{\lfloor n/2 \rfloor}\right)^2 & \text{ si } n \text{ est impair} \end{cases} \]

ce qui permet de se ramener à l'instance \(\lfloor n/2 \rfloor\), bien plus petite que \(n - 1\). C'est l'exponentiation rapide.

let rec puissance x n =
    if n = 0
    then 1
    else
        let y = puissance x (n/2) in
        if n mod 2 = 0
        then y * y
        else x * y * y

int puissance(int x, int n)
{
    if (n == 0)
    {
        return 1;
    }
    int y = puissance(x, n/2);
    if (n % 2 == 0)
    {
        return y * y;
    }
    else
    {
        return x * y * y;
    }
}

def puissance(x, n):
    if n == 0:
        return 1
    y = puissance(x, n // 2)
    if n % 2 == 0:
        return y * y
    else:
        return x * y * y

Remarque

On a pris soin de stocker le résultat de l'appel récursif dans y. Écrire puissance x (n/2) * puissance x (n/2) donnerait le même résultat mais ferait deux appels récursifs au lieu d'un : on verra avec l'arbre d'appels que cela fait perdre tout l'intérêt de la méthode.

Prouver la correction par récurrence

La structure d'une fonction récursive se prête naturellement à une preuve par récurrence : l'hypothèse de récurrence porte sur les appels récursifs.

Propriété

Pour tout entier \(n \ge 0\), fact n renvoie \(n!\).

Preuve

Par récurrence sur \(n\). Pour \(n = 0\), fact 0 renvoie \(1 = 0!\).

Soit \(n \ge 1\) tel que fact (n-1) renvoie \((n-1)!\). Comme \(n \neq 0\), fact n renvoie \(n\) multiplié par la valeur de fact (n-1), soit \(n \times (n-1)! = n!\).

Propriété

Pour tout entier \(x\) et tout entier \(n \ge 0\), puissance x n renvoie \(x^n\).

Preuve

Par récurrence forte sur \(n\). Pour \(n = 0\), la fonction renvoie \(1 = x^0\).

Soit \(n \ge 1\) et supposons le résultat vrai pour tout \(k < n\). Comme \(\lfloor n/2 \rfloor < n\), l'hypothèse de récurrence assure que \(y = x^{\lfloor n/2 \rfloor}\).

  • Si \(n\) est pair, \(n = 2 \lfloor n/2 \rfloor\) et la fonction renvoie \(y^2 = x^n\).
  • Si \(n\) est impair, \(n = 2 \lfloor n/2 \rfloor + 1\) et la fonction renvoie \(x y^2 = x^n\).

Exercice

On considère la fonction suivante, où t est un tableau et n un entier tel que \(0 \le n \le\) la longueur de t :

let rec croissant t n =
    if n = 0 || n = 1
    then true
    else t.(n-2) <= t.(n-1) && croissant t (n-1)

bool croissant(int t[], int n)
{
    if (n == 0 || n == 1)
    {
        return true;
    }
    else
    {
        return t[n-2] <= t[n-1] && croissant(t, n-1);
    }
}

def croissant(t, n):
    if n == 0 or n == 1:
        return True
    else:
        return t[n-2] <= t[n-1] and croissant(t, n-1)
  1. Montrer par récurrence que l'appel croissant t n termine.
  2. Montrer par récurrence que croissant t n renvoie vrai si et seulement si \(t_0 \le t_1 \le \dots \le t_{n-1}\).
Solution
  1. Pour \(n \in \{0, 1\}\), il n'y a pas d'appel récursif. Si l'appel pour \(n \ge 1\) termine, l'appel pour \(n + 1\) effectue une comparaison puis éventuellement l'appel pour \(n\), qui termine. On aurait pu se contenter de remarquer que \(n\) diminue strictement à chaque appel en restant dans \(\N\) : c'est la version récursive de la notion de variant de boucle.
  2. On montre par récurrence sur \(n\) que croissant t n est vrai si et seulement si \(\forall i \in \range{0}{n-2}, t_i \le t_{i+1}\). Pour \(n \in \{0, 1\}\), il n'y a rien à comparer et la fonction renvoie vrai. Supposons la propriété vraie au rang \(n \ge 1\). Au rang \(n + 1\), la fonction renvoie vrai si et seulement si \(t_{n-1} \le t_n\) et croissant t n est vrai, c'est-à-dire, par hypothèse de récurrence, si et seulement si \(t_{n-1} \le t_n\) et \(\forall i \in \range{0}{n-2}, t_i \le t_{i+1}\), ce qui équivaut à \(\forall i \in \range{0}{n-1}, t_i \le t_{i+1}\).

Remarque

On a raisonné ici sur des entiers mathématiques. Avec les entiers machine de C ou d'OCaml, le résultat n'est correct que modulo les dépassements de capacité, par exemple fact 21 n'est pas \(21!\) en OCaml sur 63 bits. En Python, les entiers étant en précision arbitraire, il n'y a pas ce problème.

Récursivité croisée

Il arrive que deux fonctions (ou plus) s'appellent l'une l'autre : on parle de récursivité croisée ou mutuelle. Un exemple volontairement simple est celui de la parité d'un entier naturel : \(n\) est pair si \(n = 0\) ou si \(n-1\) est impair, et \(n\) est impair si \(n \neq 0\) et \(n-1\) est pair.

En OCaml, une fonction ne peut faire référence qu'à des noms déjà définis. On définit donc les deux fonctions simultanément avec let rec ... and ... :

let rec est_pair n =
    if n = 0
    then true
    else est_impair (n-1)
and est_impair n =
    if n = 0
    then false
    else est_pair (n-1)

En C, une fonction doit être déclarée avant d'être utilisée. On écrit donc d'abord le prototype de est_impair pour pouvoir l'appeler dans est_pair :

bool est_impair(int n);

bool est_pair(int n)
{
    if (n == 0)
    {
        return true;
    }
    return est_impair(n-1);
}

bool est_impair(int n)
{
    if (n == 0)
    {
        return false;
    }
    return est_pair(n-1);
}

En Python, le nom est_impair n'est cherché qu'au moment de l'appel, il n'y a donc rien de particulier à faire :

def est_pair(n):
    if n == 0:
        return True
    return est_impair(n-1)

def est_impair(n):
    if n == 0:
        return False
    return est_pair(n-1)

On retrouvera ce schéma de manière beaucoup plus naturelle avec des types de données mutuellement récursifs ou en analyse syntaxique, où chaque catégorie de la grammaire (expression, terme, facteur, ...) correspond à une fonction.

L'arbre d'appels

Définition

Définition

L'arbre d'appels associé à l'évaluation d'une fonction récursive sur un argument est l'arbre dont :

  • la racine est l'appel initial ;
  • les fils d'un nœud sont les appels récursifs effectués directement par cet appel, dans l'ordre où ils sont faits.

Les feuilles correspondent aux appels qui n'en font aucun autre, le plus souvent les cas de base.

Pour fact 5, l'arbre est un simple chemin, comme sur la figure du début du chapitre. Il en va autrement quand une fonction fait plusieurs appels récursifs, comme le calcul naïf du \(n\)-ième terme de la suite de Fibonacci définie par \(F_0 = 0\), \(F_1 = 1\) et \(F_{n} = F_{n-1} + F_{n-2}\) pour \(n \ge 2\) :

let rec fib n =
    if n <= 1
    then n
    else fib (n-1) + fib (n-2)

int fib(int n)
{
    if (n <= 1)
    {
        return n;
    }
    return fib(n-1) + fib(n-2);
}

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

L'arbre d'appels de fib 4 est alors :

Arbre d'appels de fib 4 : fib 2 est calculé deux fois Arbre d'appels de fib 4 : fib 2 est calculé deux fois
Arbre d'appels de fib 4 : fib 2 est calculé deux fois

On y voit que fib 2 est calculé deux fois et fib 1 trois fois : la fonction refait sans cesse les mêmes calculs.

La pile d'exécution permet de relier cet arbre à l'exécution réelle : à chaque instant, la pile contient exactement les appels situés sur le chemin de la racine au nœud en cours d'évaluation. La hauteur de la pile est donc majorée par la hauteur de l'arbre plus un.

Complexité en nombre d'appels

Si chaque appel effectue, en dehors de ses appels récursifs, un nombre d'opérations borné par une constante, la complexité temporelle est proportionnelle au nombre de nœuds de l'arbre d'appels. On compte alors les appels en traduisant la structure de la fonction en une équation de récurrence.

Exemple

Notons \(C(n)\) le nombre d'appels effectués lors de l'évaluation de fact n. On a \(C(0) = 1\) et \(C(n) = 1 + C(n-1)\) pour \(n \ge 1\), d'où \(C(n) = n + 1\).

Propriété

Notons \(A(n)\) le nombre d'appels effectués lors de l'évaluation de fib n. Pour tout \(n \ge 0\), \(A(n) = 2F_{n+1} - 1\). En particulier, en notant \(\varphi = \frac{1+\sqrt{5}}{2}\), on a \(A(n) \ge 2\varphi^{n-1} - 1\) : le nombre d'appels est exponentiel en \(n\).

Preuve

On a \(A(0) = A(1) = 1\) et, pour \(n \ge 2\), \(A(n) = 1 + A(n-1) + A(n-2)\) en comptant l'appel lui-même puis les deux sous-arbres.

On montre \(A(n) = 2F_{n+1} - 1\) par récurrence double. Pour \(n = 0\) et \(n = 1\) : \(2F_1 - 1 = 2F_2 - 1 = 1\). Si c'est vrai aux rangs \(n-1\) et \(n-2\), alors \(A(n) = 1 + 2F_n - 1 + 2F_{n-1} - 1 = 2F_{n+1} - 1\).

Montrons ensuite \(F_n \ge \varphi^{n-2}\) pour \(n \ge 1\), encore par récurrence double : \(F_1 = 1 \ge \varphi^{-1}\), \(F_2 = 1 = \varphi^0\) et, pour \(n \ge 3\), \(F_n = F_{n-1} + F_{n-2} \ge \varphi^{n-3} + \varphi^{n-4} = \varphi^{n-4}(\varphi + 1) = \varphi^{n-2}\) car \(\varphi^2 = \varphi + 1\). D'où \(A(n) = 2F_{n+1} - 1 \ge 2\varphi^{n-1} - 1\).

Concrètement, fib 30 effectue \(2 F_{31} - 1 = 2\,692\,537\) appels alors qu'une simple boucle calculant les termes successifs en ferait une trentaine. On verra avec la programmation dynamique comment éviter ces recalculs.

Propriété

Notons \(P(n)\) le nombre d'appels effectués lors de l'évaluation de puissance x n. On a \(P(0) = 1\) et, pour \(n \ge 1\), \(P(n) = \lfloor \log_2 n \rfloor + 2\).

Preuve

On a \(P(0) = 1\) et \(P(n) = 1 + P(\lfloor n/2 \rfloor)\) pour \(n \ge 1\). On procède par récurrence forte sur \(n \ge 1\). Pour \(n = 1\) : \(P(1) = 1 + P(0) = 2 = \lfloor \log_2 1 \rfloor + 2\).

Soit \(n \ge 2\) et \(k = \lfloor \log_2 n \rfloor \ge 1\), de sorte que \(2^k \le n < 2^{k+1}\). On a alors \(2^{k-1} \le \lfloor n/2 \rfloor < 2^k\), donc \(\lfloor n/2 \rfloor \ge 1\) et \(\lfloor \log_2 \lfloor n/2 \rfloor \rfloor = k - 1\). Par hypothèse de récurrence, \(P(n) = 1 + (k - 1) + 2 = k + 2\).

Avec la version maladroite évoquée plus haut qui fait deux appels puissance x (n/2), l'équation devient \(P'(n) = 1 + 2P'(\lfloor n/2 \rfloor)\) et on vérifie de même que \(P'(2^k) = 2^{k+2} - 1\) : on fait alors plus d'appels que la méthode naïve en \(n+1\) appels.

Terminaison

On a justifié la terminaison de fact n pour \(n \ge 0\) en remarquant que l'argument décroît strictement dans \(\N\). On généralise cette idée.

Définition

Soit \(f\) une fonction récursive dont les arguments appartiennent à un ensemble \(D\). Un variant (ou une mesure) pour \(f\) est une application \(\mu : D \to \N\) telle que, pour tout \(a \in D\), chaque appel récursif effectué lors de l'évaluation de \(f(a)\) se fait sur un argument \(a' \in D\) vérifiant \(\mu(a') < \mu(a)\).

Théorème

Si \(f\) admet un variant \(\mu\) sur \(D\) et si, en dehors des appels récursifs, l'évaluation de \(f(a)\) termine pour tout \(a \in D\), alors l'évaluation de \(f(a)\) termine pour tout \(a \in D\).

Preuve

On montre par récurrence forte sur \(m \in \N\) la propriété : « pour tout \(a \in D\) tel que \(\mu(a) = m\), l'évaluation de \(f(a)\) termine ».

Soit \(m \in \N\) tel que la propriété soit vraie pour tout \(m' < m\) et soit \(a \in D\) avec \(\mu(a) = m\). Chaque appel récursif fait par \(f(a)\) porte sur un \(a' \in D\) avec \(\mu(a') < m\), il termine donc par hypothèse de récurrence. Comme le reste du calcul termine aussi, l'évaluation de \(f(a)\) termine. Le cas \(m = 0\) est contenu dans ce raisonnement : il ne peut alors y avoir aucun appel récursif.

Exemple

  • Pour puissance x n, avec \(D = \N\), \(\mu(n) = n\) convient car \(\lfloor n/2 \rfloor < n\) pour \(n \ge 1\).
  • Pour est_pair et est_impair, on applique le même raisonnement aux deux fonctions à la fois avec la mesure \(\mu(n) = n\).
  • Pour fact, l'ensemble \(D\) est important : sur \(\Z\), \(\mu(n) = n\) n'est pas à valeurs dans \(\N\) et, effectivement, fact (-1) ne termine pas.

Parfois, aucune mesure entière simple ne s'impose. On utilise alors plus généralement un ensemble ordonné \((E, \preceq)\) bien fondé, c'est-à-dire dans lequel il n'existe pas de suite infinie strictement décroissante. La preuve s'adapte : si \(f(a_0)\) ne terminait pas, l'un de ses appels récursifs \(f(a_1)\) ne terminerait pas, puis l'un des appels de \(f(a_1)\), et ainsi de suite, ce qui construirait une suite infinie strictement décroissante \(\mu(a_0) \succ \mu(a_1) \succ \dots\), contradiction.

Exemple

La fonction d'Ackermann est définie sur \(\N^2\) par

\[ A(m, n) = \begin{cases} n + 1 & \text{ si } m = 0 \\ A(m-1, 1) & \text{ si } m > 0 \text{ et } n = 0 \\ A(m-1, A(m, n-1)) & \text{ sinon.} \end{cases} \]

Le premier argument ne décroît pas toujours (appel \(A(m, n-1)\)) et le second peut augmenter énormément (appel \(A(m-1, A(m, n-1))\)). En revanche, chaque appel fait décroître strictement le couple \((m, n)\) pour l'ordre lexicographique sur \(\N^2\) : \((m-1, \cdot) < (m, n)\) et \((m, n-1) < (m, n)\).

Cet ordre est bien fondé : dans une suite strictement décroissante \((m_k, n_k)_k\), la suite \((m_k)\) est décroissante dans \(\N\) donc constante à partir d'un certain rang, et à partir de ce rang \((n_k)\) est strictement décroissante dans \(\N\), ce qui empêche la suite d'être infinie. Ainsi, l'évaluation de \(A(m,n)\) termine toujours, même si elle peut prendre un temps colossal : \(A(3, 3) = 61\) mais \(A(4, 2) = 2^{65536} - 3\).

Récursivité terminale

Présentation

Quand on évalue fact n, il faut attendre le retour de l'appel fact (n-1) pour effectuer la multiplication par n : le contexte de l'appel courant doit être conservé sur la pile. C'est ce qui explique la phase de remontée vue au début du chapitre.

Définition

Un appel de fonction est terminal lorsque sa valeur est directement la valeur renvoyée par la fonction appelante, sans aucun calcul supplémentaire. Une fonction récursive est récursive terminale lorsque tous ses appels récursifs sont terminaux.

fact n'est pas récursive terminale à cause de la multiplication n * .... Pour la rendre terminale, on effectue la multiplication avant l'appel en la stockant dans un argument supplémentaire, appelé accumulateur :

let fact_term n =
    let rec aux n acc =
        if n = 0
        then acc
        else aux (n-1) (n * acc)
    in aux n 1

int fact_aux(int n, int acc)
{
    if (n == 0)
    {
        return acc;
    }
    return fact_aux(n-1, n * acc);
}

int fact_term(int n)
{
    return fact_aux(n, 1);
}

def fact_term(n, acc=1):
    if n == 0:
        return acc
    return fact_term(n-1, n * acc)

L'évaluation de fact_term 3 donne la suite d'appels aux 3 1, aux 2 3, aux 1 6, aux 0 6 qui renvoie directement 6 : il n'y a plus rien à faire à la remontée.

Remarque

Pour prouver la correction, on ne peut pas montrer que aux n acc renvoie \(n!\), ce qui est faux. On montre par récurrence sur \(n\) la propriété plus forte : pour tout entier acc, aux n acc renvoie \(n! \times \texttt{acc}\). On en déduit que fact_term n renvoie \(n! \times 1\). Généraliser l'énoncé pour faire apparaître l'accumulateur est le point clé de ce type de preuve.

Optimisation

Lors d'un appel terminal, le contexte de la fonction appelante n'a plus aucune utilité puisqu'il n'y a plus rien à calculer après. Le compilateur peut donc réutiliser son emplacement sur la pile au lieu d'en empiler un nouveau : l'appel devient un simple saut au début de la fonction avec de nouveaux arguments. Une fonction récursive terminale s'exécute alors avec une pile de taille constante, exactement comme une boucle.

OCaml garantit cette optimisation. On peut le constater sur le calcul de \(\sum_{k=1}^n k\) :

# let rec somme n = if n = 0 then 0 else n + somme (n-1);;
val somme : int -> int = <fun>
# somme 100_000_000;;
Stack overflow during evaluation (looping recursion?).
# let somme_term n =
    let rec aux n acc = if n = 0 then acc else aux (n-1) (acc + n) in
    aux n 0;;
val somme_term : int -> int = <fun>
# somme_term 100_000_000;;
- : int = 5000000050000000

La limite exacte dépend de la taille de pile autorisée, mais seule la version terminale fonctionne pour tout \(n\).

La norme du langage C ne garantit rien. En pratique, gcc et clang effectuent cette optimisation lorsqu'on compile avec optimisations (-O2), mais il ne faut pas s'en remettre à cela pour la correction d'un programme : en C, on écrira plutôt une boucle.

Python n'effectue jamais cette optimisation. De plus, la profondeur de la pile d'appels est limitée par défaut à 1000 :

>>> fact_term(10000)
Traceback (most recent call last):
  ...
RecursionError: maximum recursion depth exceeded

On peut augmenter cette limite avec sys.setrecursionlimit, mais pour des calculs de grande profondeur, on préfère une boucle.

Techniques

Accumulateur

La technique de l'accumulateur vue sur fact est très générale : on ajoute un argument qui contient le résultat partiel déjà calculé, et le cas de base renvoie cet accumulateur.

Sur les listes en OCaml, le parcours voit les éléments de gauche à droite et, quand on ajoute chaque élément en tête d'un accumulateur, le premier élément vu se retrouve au fond. C'est exactement ce qu'il faut pour renverser une liste :

let renverse l =
    let rec aux l acc =
        match l with
        | [] -> acc
        | t :: q -> aux q (t :: acc)
    in aux l []

Mais c'est un piège quand on veut conserver l'ordre : on renverse alors le résultat à la fin, ce qui reste linéaire :

let map_term f l =
    let rec aux l acc =
        match l with
        | [] -> List.rev acc
        | x :: q -> aux q (f x :: acc)
    in aux l []

Du récursif terminal à l'itératif

Une fonction récursive terminale se traduit mécaniquement en boucle : les arguments deviennent des variables, le cas de base devient la condition de sortie et l'appel récursif devient une mise à jour des variables.

let fact_iter n =
    let n = ref n in
    let acc = ref 1 in
    while !n <> 0 do
        acc := !n * !acc;
        n := !n - 1
    done;
    !acc

int fact_iter(int n)
{
    int acc = 1;
    while (n != 0)
    {
        acc = n * acc;
        n = n - 1;
    }
    return acc;
}

def fact_iter(n):
    acc = 1
    while n != 0:
        acc = n * acc
        n = n - 1
    return acc

Réciproquement, toute boucle while peut s'écrire comme une fonction récursive terminale dont les arguments sont les variables modifiées par la boucle. Récursif terminal et itératif sont donc deux écritures d'un même calcul.

Remarque

Pour une fonction qui n'est pas récursive terminale, comme fib ou un parcours d'arbre, le passage à l'itératif est plus délicat : il faut gérer soi-même une pile qui remplace la pile d'exécution. On le fera pour le parcours en profondeur d'un graphe.

Le choix entre les deux écritures relève avant tout de la clarté : une fonction récursive qui suit la structure du problème est souvent plus simple à écrire et à prouver. On ne cherche à la rendre terminale que lorsque la profondeur des appels peut devenir grande, typiquement linéaire en la taille des données.

Types inductifs et induction structurelle

Définition naïve des types inductifs

Un type inductif est un type dont les valeurs sont construites à l'aide d'un nombre fini de constructeurs, chacun pouvant prendre des arguments, dont certains sont eux-mêmes du type que l'on définit. Naïvement, une valeur d'un tel type est obtenue en appliquant un nombre fini de fois ces constructeurs.

En OCaml, les listes en sont l'exemple de base : une liste est soit [], soit x :: q où q est une liste. On peut définir de même les arbres binaires dont les nœuds sont étiquetés par des entiers :

type arbre = Vide | Noeud of arbre * int * arbre

Une fonction récursive sur un type inductif suit naturellement sa définition, avec un cas par constructeur et un appel récursif sur chaque argument du type lui-même :

let rec taille a =
    match a with
    | Vide -> 0
    | Noeud (g, _, d) -> 1 + taille g + taille d

let rec nb_vides a =
    match a with
    | Vide -> 1
    | Noeud (g, _, d) -> nb_vides g + nb_vides d

Une telle fonction termine toujours : le nombre de constructeurs utilisés pour écrire l'argument est un variant, puisque g et d en utilisent strictement moins que Noeud (g, x, d).

Pour démontrer des propriétés de ces fonctions, on raisonne de la même manière.

Théorème

Soit \(P\) une propriété portant sur les valeurs du type arbre. Si

  • \(P(\texttt{Vide})\) est vraie,
  • pour tous arbres \(g, d\) et tout entier \(x\), \(P(g)\) et \(P(d)\) impliquent \(P(\texttt{Noeud}(g, x, d))\),

alors \(P(a)\) est vraie pour tout arbre \(a\). C'est le principe d'induction structurelle.

Preuve

On montre par récurrence forte sur \(k \in \N\) que \(P(a)\) est vraie pour tout arbre \(a\) écrit avec \(k\) constructeurs. Soit \(a\) un tel arbre. Si \(a = \texttt{Vide}\), c'est la première hypothèse. Sinon, \(a = \texttt{Noeud}(g, x, d)\) où \(g\) et \(d\) sont écrits avec strictement moins de \(k\) constructeurs : \(P(g)\) et \(P(d)\) sont vraies par hypothèse de récurrence, donc \(P(a)\) par la seconde hypothèse.

Exemple

Pour tout arbre a, nb_vides a = taille a + 1. En effet, c'est vrai pour Vide (\(1 = 0 + 1\)) et si c'est vrai pour g et d, alors pour a = Noeud (g, x, d) on a nb_vides a \(= (\texttt{taille g} + 1) + (\texttt{taille d} + 1) = \texttt{taille a} + 1\).

Le principe se généralise à tout type inductif : il y a une hypothèse par constructeur, avec une hypothèse d'induction pour chaque argument du type lui-même. Pour les listes, on retrouve : si \(P(\texttt{[]})\) et si \(P(q)\) implique \(P(\texttt{x :: q})\), alors \(P\) est vraie pour toute liste. Pour le type type nat = Z | S of nat, on retrouve exactement la récurrence sur \(\N\).