Preuves avec récursion et induction

Lorsqu’on travaille avec des définitions et des algorithmes récursifs, il est important de pouvoir prouver qu’ils font réellement ce qu’ils doivent. La méthode naturelle pour cela est l’induction mathématique. L’induction ressemble à la récursion : on commence par un cas de base et on montre ensuite que si l’énoncé est vrai pour un pas, il est également vrai pour le suivant.

Exemple 1 : Factorielle

Nous voulons prouver que la définition récursive de la factorielle correspond à la formule usuelle du produit :

$$ \large n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n, \quad n \geq 1 $$

Base

Pour $ \large n = 1 $ :

$$ \large 1! = 1 \quad \text{vrai} $$

Étape d’induction

Supposons que l’énoncé soit vrai pour un certain $ \large n $, c’est-à-dire

$$ \large n! = 1 \cdot 2 \cdot \ldots \cdot n $$

Alors, pour $ \large n+1 $ :

$$ \large (n+1)! = (n+1) \cdot n! $$

Par l’hypothèse d’induction, on peut remplacer $ \large n! $ :

$$ \large (n+1)! = (n+1) \cdot (1 \cdot 2 \cdot \ldots \cdot n) $$

On obtient donc exactement le produit jusqu’à $ \large n+1 $. L’énoncé est donc vrai pour tout $ \large n $.

Exemple 2 : Fibonacci

La suite de Fibonacci est définie par

$$ \large F_{0} = 0, \quad F_{1} = 1, \quad F_{n} = F_{n-1} + F_{n-2} \;\; (n \geq 2) $$

Une formule connue dit que la somme des $ \large n $ premiers nombres de Fibonacci est :

$$ \large F_{0} + F_{1} + \ldots + F_{n} = F_{n+2} - 1 $$

Base

Pour $ \large n = 0 $, à gauche on a la somme $ \large F_{0} = 0 $.

À droite on a $ \large F_{2} - 1 = 1 - 1 = 0 $.

Les deux côtés donnent le même résultat, donc l’énoncé est vrai dans le cas de base.

Étape d’induction

Supposons que l’énoncé soit vrai pour un certain $ \large n $ :

$$ \large F_{0} + F_{1} + \ldots + F_{n} = F_{n+2} - 1 $$

Montrons-le pour $ \large n+1 $ :

$$ \large F_{0} + F_{1} + \ldots + F_{n} + F_{n+1} $$

$$ \large = (F_{n+2} - 1) + F_{n+1} \quad \text{(par hypothèse d’induction)} $$

$$ \large = F_{n+1} + F_{n+2} - 1 $$

$$ \large = F_{n+3} - 1 $$

L’énoncé est donc aussi vrai pour $ \large n+1 $. Par induction, la formule est valide pour tout $ \large n $.

Exemple 3 : Correction d’un algorithme récursif

Nous avons vu plus tôt l’algorithme qui trouve le maximum dans une liste :

function max(list):
    if list has length 1:
        return list[0]            // base
    else:
        m = max(rest of list)     // étape récursive
        return the larger of list[0] and m

Nous voulons prouver que l’algorithme retourne toujours le plus grand élément de la liste.

Base

Si la liste a une longueur de 1, l’algorithme retourne l’unique élément. C’est correct, car un seul élément est évidemment le maximum.

Étape d’induction

Supposons que l’algorithme fonctionne correctement pour toutes les listes de longueur $ \large n $. Nous devons montrer qu’il fonctionne aussi pour une liste de longueur $ \large n+1 $.

Soit la liste $ \large [x_0, x_1, \ldots, x_n] $. L’algorithme s’appelle sur la sous-liste $ \large [x_1, \ldots, x_n] $, qui a une longueur $ \large n $. Par hypothèse d’induction, cet appel retourne correctement le maximum de la sous-liste.

Enfin, l’algorithme compare ce maximum avec le premier élément $ \large x_0 $. Il retourne donc le plus grand de tous les éléments $ \large x_0, x_1, \ldots, x_n $, c’est-à-dire le maximum de la liste entière.

Conclusion

Par induction, l’algorithme max retourne toujours le plus grand élément d’une liste, quelle que soit sa longueur.

Résumé

L’induction est la méthode naturelle pour prouver la correction des définitions récursives. On montre que le cas de base est correct, et que si l’énoncé est vrai pour un pas, il l’est aussi pour le suivant. Ainsi, toute la construction infinie est couverte. Cela fait de l’induction un outil fondamental dans le travail avec la récursion.