La question de la terminaison

Prouver qu'un algorithme termine ?

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.

Cas faciles

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. Dans ces situations, la terminaison est démontrée.

Conjecture de Syracuse

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

🐍 Script Python

def syracuse(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 syracuse(n // 2)
        else:
            # n est impair
            return syracuse(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

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

XKCD 710² : Collatz Conjecture