Une fonction récursive est une fonction qui s'appelle elle même. En voici quelques exemples :

Une fonction qui ne sert à rien, elle sert juste à l'explication.

def affichage_decroissant(nombre:int):
    print(nombre)
    if nombre > 0:
    	affichage_decroissant(nombre-1)

Suite récurrente. En mathématiques, on peut définir une suite $(u_n)_{n\geqslant 0}$ par

• $u_0 = 10$
• pour $n\geqslant 1$, $u_{n} = 0,8 u_{n-1} + 25$.

L'utilisation d'une fonction récurrente rend le calcul extrêmement simple :

def u(n):
    assert n >= 0
    if n == 0:
        return 10
    return 0.8 * u(n-1) + 25

Cas particulier célèbre : la suite de Fibonacci $(F_n)_{n\geqslant 0}$. On définit :

• $F_0 = 1$
• $F_1 = 1$
• pour $n\geqslant 2$, $F_n = F_{n-1} + F_{n-2}$

La fonction factorielle, grande classique de la récursivité.

Je rappelle que factorielle se note avec $!$ et que par définition : $n! = 1 \times 2 \times 3 \times \cdots \times (n-1) \times n$. Par exemple $3! = 1 \times 2 \times 3 = 6$.

On convient que $0! = 1$.

On pourrait voir la factorielle comme une suite $(f)_{n\geqslant 0}$ définie par

• $f_0 = 1$
• pour $n \geqslant 1$, $f_n = n \times f_{n-1}$.

Un mauvais exemple de récurrence qui entraîne une séquence infinie d'appels récurrents :

def mauvais(n:int):
    print(n)
    mauvais(n+1)

Je vous laisse deviner à quoi sert cette fonction…

Vous pouvez la tester avec quelques valeurs de n.

def somme(n,s):
    if n == 0:
        return s
    return somme(n-1, s+n)

# exemples d'utilisation (on met toujours le 2e argument à 0) :
a = somme(10, 0)
print(a)
b = somme(5, 0)
print(b)

Comme vous pouvez le voir, ces fonctions ont quelque chose de répétitif.

Par exemple pour la suite $u$, je calcule de $u_4$ :

• il faut d'abord calculer $u_3$. Mais pour calculer $u_3$,
• il faut d'abord calculer $u_2$. Mais pour calculer $u_2$,
• il faut d'abord calculer $u_1$. Mais pour calculer $u_1$,
• il faut d'abord calculer $u_0$. On sait que $u_0$ vaut 10.

Cette répétition doit finir par se terminer et donc la récurrence nécessite une condition.

Comme pour une boucle TANT QUE – while – qui peut se répéter indéfiniment, il faut veiller particulièrement à la bonne terminaison des fonctions récurrentes.

L'exemple 4 est donc un exemple à ne pas suivre.

Dans l'exemple 2, la fonction commence avec $n \geqslant 0$.

Le cas n == 0 est le cas de base, celui qui ne nécessite pas de nouvel appel récursif et qui met donc fin à la succession des appels.

En général, une fonction récursive doit prévoir un test qui détecte si on est dans un cas de base ou non.

La succession d'appels doit aboutir à un cas de base, sans quoi on aura une récursion infinie et donc une RecursionError.

Comparons les deux possibilités suivantes pour calculer les termes de la suite récurrente u déjà rencontrée :

def u(n):
    if n == 0:
        return 10
    return 0.8 * u(n-1) + 25

def u(n):
    u = 10
    for i in range(n):
        u = 0.8*u + 25
    return u

À gauche, dans la version récurrente, nous avons une écriture très élégante et très proche de l'écriture mathématique. On aimerait pouvoir programmer de cette façon.

Mais si vous essayez de calculer u(1000) vous constaterez que la version de gauche finit par provoquer une erreur :

>>> u(1000)
RecursionError: maximum recursion depth exceeded in comparison

Au contraire, bien que moins élégante, la version de droite ne pose aucun problème. On pourrait même calculer u(100000) !

Dans un programme, une fonction constitue un contexte particulier. On sait par exemple que dans le cas suivant, le a défini en ligne 2 et le a en ligne 5 n'ont rien à voir avec l'autre.

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

a = 17
f(45)
print(a)
f(19)
print(a)

Le a de la ligne 2 n'existe que le temps de la fonction. Il n'est accessible que le temps de l'exécution de la fonction.

De plus la fonction peut-être appelée depuis plusieurs endroits du programme et, après la fin de la fonction, le programme doit continuer là où il en était.

Donc chaque appel de fonction nécessite de créer un contexte lié à la fonction et de mémoriser des informations lié à cet appel particulier. Toutes ces informations devront être conservées jusqu'à la fin de l'exécution de la fonction.

On utilise une pile pour stocker ces informations. Voici un exemple avec l'exécution de facto(4).

On voit que le calcul de facto(4) doit attendre le retour de facto(3) qui lui même attendra le retour de facto(2)…

Quand les appels se terminent, on peut dépiler :

La fin de facto(0) permet de dépiler les informations concernant cet appel dans la pile et de renvoyer le résultat, 1. Ce résultat permet de terminer facto(1) dont l'appel est dépilé, etc.

Le problème est que l'appel de facto(4) reste suspendu dans l'attente de la fin de facto(3). Il est possible de procéder autrement, c'est ce qu'on appelle la récursion terminale.

Prenons les cas de l'exemple 5. qui est en récursion terminale.

def somme(n,s):
    if n == 0:
        return s
    return somme(n-1, s+n)

Cette fois, soit la fonction n'appelle pas de récurrence, soit la récurrence est ce qu'elle fait en dernier.

• Par exemple, si j'appelle somme(10, 0). Comme n != 0, l'appel se terminera par return somme(10 - 1, 0 + 10). Autrement dit, le résultat de somme(10,0) est exactement le même que celui de somme(9, 10).
• Quand somme(10, 0) appelle somme(9,10), il n'est pas nécessaire de garder en mémoire quelque chose de somme(10, 0). On peut terminer l'exécution de somme(10,0) et passer la main à somme(9,10). Inutile d'encombrer la pile avec une fonction somme(10,0) qui attendrait la fin de l'exécution de somme(9,10).

On peut toujours remplacer une récursivité par une boucle TANT QUE – while.

Pour la fonction somme ce serait assez simple :

def somme(n,s):
    if n == 0:
        return s
    return somme(n-1, s+n)

def somme(n,s):
    while n != 0:
        n, s = n-1, s + n
    return s

Dans le cas d'une récursion terminale, ce travail est simple et peut même être fait automatiquement.

Certains langages comme OCaml le font. C'est à dire que si vous leur fournissez une récurrence de type récursion terminale, cette récurrence est automatiquement, à l’exécution, transformée en boucle while.

Voici un exemple de passage automatique.

# cas récurrent terminal
def fonction(arguments):
    if condition:
        return final
    instructions...
    return fonction(nouveaux arguments)

# en version while
def fonction(arguments):
    while not condition:
        instructions...
        arguments = nouveaux arguments
    return final

On a ainsi les avantages de la récurrence et pas ses défauts :

• avantages : programmation plus intuitive,
• défauts : pile d'appel de fonctions qui déborde si le nombre de récurrence est trop élevé.

Si je reprends l'exemple 5, vous avez dû comprendre que la fonction somme réalisait la somme des entiers de 1 à n. l'argument s sert d'accumulateur.

En récursion non terminale on aurait eu tendance à écrire

def somme(n):
    if n == 0:
        return 0
    return somme(n-1) + n

C'est très simple. Mais cette fois le calcul de somme(n-1) n'est pas la dernière chose faite, car après le calcul de somme(n-1), on doit encore faire + n

L'argument s est donc l'astuce qui a permis de rendre la récurrence terminale.

On pourrait présenter les choses ainsi :

• En version non terminale, l'appel parent conserve l'accumulateur s et attend que l'appel enfant donne son résultat pour l'ajouter à s.
• En version terminale, l'appel parent fournit à l'appel enfant l'accumulateur s et laisse à l'appel enfant le soin de la gestion de s. Ainsi l'appel parent n'a plus à attendre, il laisse l'appel enfant poursuivre.

L'utilisation de fonctions récursives permet dans certains cas une écriture très claire et simple des programmes. Certains problèmes peuvent être difficiles à résoudre sans l'utilisation de la récursivité.

Vous pouvez prendre l'exemple de la fonction longueur dans les listes, ou de la fonction hauteur dans les arbres. Ces fonctions sont assez simple en version récursive. Elles le seraient beaucoup moins en version non récursive.

Mais la récursivité pose deux problèmes :

• comme une boucle tant que, une fonction récursive risque de devenir une boucle infinie. Il faut s'assurer que la récurrence arrive à un terme.
• le fonctionnement de l'appel des fonctions suppose dans le système la mémorisation de toute la séquence d'appels sous forme d'une pile d'exécution. Cette pile est de taille limitée et c'est une limite vite atteinte.
  En Python, 1000 appels récursifs saturent la pile.

Dans certains langages – pas Python – l'utilisation de la récursion terminale permet de contourner le second problème.