🧰 Mécanismes⚓︎

Dans cette section, on montre quelques aspects techniques, certaines limites de la récursivité.

Il ne faut pas oublier que la récursivité reste aussi la méthode la plus simple et élégante pour résoudre certains problèmes.

Rappel sur le Traceback

Le Traceback indique le cheminement d'une erreur.

🐍 Script Python

def f(n):
    return 0 + g(n)

def g():
    return 1 * h(n)

def h(n):
    return 1 / n

Testons l'appel f(0)

🐍 Console Python

>>> f(0)
Traceback (most recent call last):
  File "<pyshell>", line 1, in <module>
  File "/home/francky/test.py", line 2, in f
      return 0 + g(n)
  File "/home/francky/test.py", line 5, in g
      return 1 * h(n)
  File "/home/francky/test.py", line 8, in h
      return 1 / n
  ZeroDivisionError: division by zero
>>>

L'appel f(0) provoque une erreur, on peut retracer l'historique des appels de fonction avec les fichiers associés, ce ne sont pas forcément les mêmes avec des modules importés. Ici

Dans un terminal, il y a eu un appel à f
Dans le fichier test.py, dans la définition de f, il y a eu un appel à g.
Dans le fichier test.py, dans la définition de g, il y a eu un appel à h.
Dans le fichier test.py, dans la définition de h, il y a eu une division par zéro.

Empreinte mémoire

Quand une fonction appelle une autre, son état est sauvegardé en mémoire, cela peut prendre beaucoup de place. La fonction appelée est copiée en mémoire ; une copie de travail supplémentaire. Il peut y avoir plusieurs copies de travail d'une même fonction.

Quand la fonction initiale reçoit le résultat de l'autre fonction, l'autre fonction a sa copie de travail détruite. Et quand elle-même renvoie son résultat, sa copie de travail sera détruite.

Dans le cas d'appels récursifs illimités, la mémoire serait vite saturée. Il faut se protéger de cette situation.

Profondeur de récursion⚓︎

Voici une fonction récursive un peu stupide...

🐍 Script Python

def f():
    return f()

Testons-la.

🐍 Console Python

>>> f()
Traceback (most recent call last):
  File "<pyshell>", line 1, in <module>
  File "/home/francky/test.py", line 1, in f
  File "/home/francky/test.py", line 1, in f
  File "/home/francky/test.py", line 1, in f
  [Previous line repeated 996 more times]
  RecursionError: maximum recursion depth exceeded
>>>

On découvre un message d'erreur précédé du Traceback, qui indique quel est le cheminement de l'erreur.

La fonction f a appelé 999 fois (3 fois affiché et 996 de plus) la fonction f qui a été appelée depuis le terminal.
La fonction f a été appelée récursivement 1000 fois au total.
La tentative supplémentaire provoque l'erreur RecursionError: maximum recursion depth exceeded, à savoir : la profondeur maximale de récursion a été dépassée.

Ce fonctionnement est normal.

Il évite aux débutants de ralentir fortement un ordinateur avec un programme qui utiliserait toute sa mémoire.

Hors programme en NSI

Il est possible de modifier la limite de profondeur de récursion, si le besoin est réel.

🐍 Script Python

import sys
sys.setrecursionlimit(10**5)

La limite est désormais à \(10^5\).

Sur France-IOI, il peut être utile de savoir cela.

Appels multiples⚓︎

Sans atteindre la profondeur maximale de récursion, on peut écrire un programme très lent avec une méthode récursive naïve avec l'appel multiple.

La fonction de Fibonacci⚓︎

On considère la fonction naïve :

🐍 Script Python

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

Ici, fib est une fonction récursive avec appels multiples.

On peut construire à la main le tableau de valeurs

`n`	`0`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`8`	`9`	`10`
`fib(n)`	`0`	`1`	`1`	`2`	`3`	`5`	`8`	`13`	`21`	`34`	`55`

Mais observons comment fonctionne un script qui appelle fib(5)

On constate une profondeur d'appel faible 5, et de manière générale n. Pourtant, il y a de nombreux appels à f : ici \(15\).

On peut faire un script qui compte le nombre d'appels avec une astuce : une fonction est un objet, on lui donne un attribut compteur que l'on initialise avant utilisation.

🐍 Script Python

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

for n in range(10):
    fib.compteur = 0
    fib(n)
    print(n, fib.compteur)


for n in [30, 35]:
    fib.compteur = 0
    fib(n)
    print(n, fib.compteur)

On obtient la suite des nombres de Leonardo¹

`n`	`0`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`8`	`9`	`10`
`leo(n)`	`1`	`1`	`3`	`5`	`9`	`15`	`25`	`41`	`67`	`109`	`177`

Pour n = 30, on atteint \(2\,692\,537\) appels.
Pour n = 35, on atteint \(29\,860\,703\) appels, ce qui ralentit déjà un ordinateur.

On est pourtant loin d'une profondeur de 1000 !

Pour rendre le calcul de la fonction de Fibonacci moins naïf, on peut faire de la mémoïsation. On stocke dans un tableau ou un dictionnaire les résultats déjà connus en vue de leur réutilisation.

Les tours de Hanoï,⚓︎

En guise d'exercice, après avoir résolu le problème des tours de Hanoï, déterminez le nombre de déplacements élémentaires en fonction du nombre de disques initial.

La question de la terminaison⚓︎

On peut déterminer parfois exactement le nombre d'appels récursifs d'une fonction.
On peut aussi parfois juste prouver que les appels finissent par cesser.
Hélas, il y a des situations où on ne sait pas !

Avec une fonction récursive, il y a des situations où on ne sait pas prouver que l'algorithme termine.

Quand on veut prouver la terminaison d'une fonction récursive, il faut prouver qu'on atteint un cas de base en un temps fini.

Souvent, on construit des fonctions récursives définies sur les entiers et on se rapproche du ou des cas de base. Alors, on peut prouver la terminaison. Mais ce n'est pas obligatoire, et il existe des fonctions récursives définies sur autre chose que les entiers...

Pour des fonctions définies sur des chaines de caractères, des tableaux ou toutes structures linéaires, on essaie de faire des appels récursifs sur une donnée de taille strictement inférieure, ce qui permet alors d'atteindre la taille 0 ou 1 qu'il faut fournir en cas de base.

Conjecture de Syracuse⚓︎

La suite de Syracuse² d'un entier n peut être affichée grâce à la fonction f récursive suivante :

🐍 Script Python

def f(n):
    """Affiche la suite de Syracuse de n, jusqu'à 1 exclu,
       et renvoie 1 si l'algorithme termine.
    """
    if n == 1:
        return 1
    else:
        print(n, end=", ")
        if n % 2 == 0:
            # n est pair
            return f(n // 2)
        else:
            # n est impair
            return f(3*n + 1)

Exemple avec la suite de Syracuse de \(14\), qui se poursuivrait avec le cycle 4, 2, 1, 4, 2, 1, 4, 2, 1, ...

🐍 Console Python

>>> f(14)
14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

Le dernier nombre 1 est affiché par le terminal comme valeur renvoyée par la fonction, les autres sont affichés par la fonction.

Pour tout n, un entier non nul, on pense que f(n) finit par renvoyer 1. C'est une conjecture ; aucune preuve n'existe. On a uniquement pu le constater pour tous les nombres inférieurs à \(2^{68}\).

On ne peut pas prouver simplement la terminaison, en effet l'image d'un pair se rapproche de 1, mais l'image d'un impair s'en éloigne...

Appels croisés⚓︎

Étudions cet exemple :

🐍 Script Python

def f(n):
    if n == 0:
        return 0
    else:
        3 * g(n // 3)

def g(n):
    if n == 0:
        return 0
    else:
        return 2 + f(n * 2)

f et g sont des fonctions récursives mutuelles, en effet la définition de l'une contient un appel à l'autre, donc à elle-même.

Ici, il est possible de prouver la terminaison. Ce genre d'exercices ne fait pas partie du programme de NSI.

Sur OEIS, A001595 : les nombres de Leonardo ↩
La conjecture de Syracuse ↩