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 Syracuse1 d'un entier n peut être affichée grâce à la fonction f récursive suivante :
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, ...
>>> f(14)
14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
Le dernier nombre
1est 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 actuellement. 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...