Récursivité

Cet article traite de la récursion en tant qu’outil pour la définition d’objets mathématiques (en particulier de fonctions). Pour la technique de preuve dite par récurrence, voir Induction.

La récursivité est une technique qui consiste à définir un objet mathématique en fonction d’objets analogues plus petits. La récursivité et l’Induction sont intimement liées et souvent on peut utiliser l’un ou l’autre mot de façon interchangeable (voir Induction ou Récursivité).

Exemples

Les constructions récursives que l’on rencontre le plus souvent définissent des fonctions sur les entiers ou sur d’autres structures dotées d’un ordre bien fondé.

Fonctions récursives sur les entiers

Une fonction de \(\mathbb{N}\) dans \(\mathbb{N}\) est définie récursivement de la façon suivante:

Factorielle

La fonction factorielle \(n!\) peut être définie récursivement de la façon suivante:

Suite de Fibonacci

La suite de Fibonacci est un exemple de définition récursive basée non seulement sur la valeur de la fonction à \(n-1\), mais aussi sur sa valeur à \(n-2\). Par conséquent, deux cas de base sont nécessaires afin d’éviter une définition mal formée.

La suite de Fibonacci apparaît régulièrement en mathématiques, allez voir sa page Wikipedia est un bon point de départ pour se faire une culture là dessus. Régulièrement, on trouve même des biologistes, des historiens et toute autre sorte de savants qui prétendent, à raison ou à tort, avoir rencontré la suite de Fibonacci dans leurs études. Cette page Wikipedia vous donnera quelques idées.

Nombres de Catalan

Les nombres de Catalan sont un autre exemple de définition récursive basée non seulement sur la valeur de la fonction à \(n-1\). Ils sont définis ainsi:

Les nombres de Catalan apparaissent aussi très fréquemment, dès que l’on travaille avec des arbres binaires. On peut montrer l’égalité suivante

\[C(n+1) = \frac{2(2n+1)}{n+2}C(n)\qquad\mathrm{pour tout } n>0.\]

Exponentielle

La fonction exponentielle est définie de la façon suivante:

Cependant, une autre définition tout à fait légitime est:

Cette deuxième définition a un intérêt algorithmique, puisque elle est à la base de l’algorithme d’exponentiation binaire.

Autres fonctions récursives

On peut définir des fonctions ou des propriétés récursives sur autre chose que les entiers. Les chaînes de caractères, par exemple, s’y prêtent très bien.

Palindrômes

Une chaine de caractères est palindrome si elle se lit de la même façon de gauche à droite et de droite à gauche. Par exemple, abba et radar sont palindromes. On peut définir la palindromie de la façon suivante:

Expressions bien parenthésées

On s’intéresse aux chaînes de caractères dans lesquelles les parenthèses ouvrantes et fermantes sont bien distribuées. Par exemple, \((ab(cd))\) est bien parenthésée, mais \((ab))(cd\) ne l’est pas. En ignorant les caractères qui ne sont pas de parenthèses (et qui ne jouent aucun rôle), on se ramène à étudier les chaînes constituées exclusivement de parenthèses. Une expression bien parenthésée est définie alors de la manière suivante:

Exercice: On peut démontrer que le nombre d’expressions bien parenthésées contenant exactement \(n\) parenthèses ouvrantes est égal au nombre de Catalan \(C(n)\). Prouvez cette propriété par récurrence. (Suggestion: Commencez par trouver une autre définition récursive des expressions bien parenthésées qui n’utilise qu’un cas de base et un cas inductif).

Définition générale

De manière intuitive, une fonction (ou une propriété) récursive est une fonction qui est définie en termes d’elle même. Ceci ne suffit pas à définir correctement une fonction, car par exemple l’égalité \(f(x) = f(x)\) ne définit aucune fonction en particulier (toute fonction a cette propriété).

Soit \(A\) un ensemble muni d’une relation d’ordre bien fondée \(\prec\), et soit \(B\) un autre ensemble quelconque. Une fonction (récursive) \(f:A\to B\) est bien définie (ou cohérente ou bien fondée) si pour tout \(a\in A\) la définition de \(f\) ne fait intervenir que des valeurs \(f(a')\) pour \(a'<a\).

Nota bene: Cette définition définition n’impose pas que \(f\) soit nécessairement définie en termes d’elle même pour tout \(a\); ceci arrive notamment pour les cas de base (par exemple la valeur de Fibonacci en \(0\) et \(1\)).

D’un autre côté la définition impose que la fonction ne soit pas définie en termes d’elle même aux éléments minimaux de \(A\). En effet, si \(a\) est un élément minimal (par exemple \(0\in\mathbb{N}\)), il n’y a aucun élément plus petit que \(a\), donc la définition de \(f\) ne peut faire recours à aucune autre valeur de \(f\).

Exercice: Pour chacune des fonction récursives définies précédemment, trouvez l’ordre bien fondé qui garantit la cohérence de la définition.

Exercice: Démontrez par Induction que toute fonction bien définie à une valeur unique à chaque élément de \(A\).

Récursion en informatique

La récursivité est tellement omniprésente en mathématiques, que tous les langages de programmation modernes permettent d’écrire des programmes récursifs, c’est à dire des programmes qui s’appellent eux mêmes.

Factorielle

L’exemple suivant, écrit en Python définit une fonction qui calcule la factorielle \(n!\) pour tout \(n\) positif.

def fact(n):
    if n < 0:
        raise Error
    elif n == 0:
        return 1
    else:
        return n * fact(n-1)

Exponentiation

En imitant la définition récursive de l’exponentielle, on peut écrire une fonction qui calcule \(c^n\) pour tout \(c\) et pour tout entier \(n\).

def exp(c, n):
    if n < 0:
        return 1 / exp(c, -n)
    elif n == 0:
        return 1
    else:
        return c * exp(c, n-1)

Diviser pour régner

Le principe diviser pour régner est l’un des outils fondamentaux en algorithmique. L’idée consiste à résoudre un problème en le coupant en deux sous-problèmes de taille à peu près égale, qu’on résout de façon récursive. Ce principe permet souvent d’obtenir des gains d’efficacité considérables.

Exponentiation binaire

En utilisant la seconde définition récursive pour l’exponentielle, on peut ré-écrire la fonction précédente de la manière suivante

def bin_exp(c, n):
    if n < 0:
        return 1 / bin_exp(c, -n)
    elif n == 0:
        return 1
    else:
        tmp = bin_exp(c, n // 2)
        tmp *= tmp
        if n % 2 == 1:
            tmp *= c
        return tmp

Un appel d’une fonction à elle même est dit un appel récursif. Si on compte combien d’appels récursifs ont lieu lors d’un appel à exp(2,10) on vérifie que celui-ci appelle exp(2,9), qui appelle exp(2,8) et ainsi de suite, pour un total de 10 appels. D’un autre côté un appel à bin_exp(2,10) engendre un appel à bin_exp(2,5), puis à binexp(2,2), puis à bin_exp(2,1) et enfin à bin_exp(2,0), pour un total de 4 appels. En général, exp fera \(n\) appels récursifs, alors que bin_exp en fera seulement \(\lceil\log_2n\rceil\).

L’algorithme bin_exp est appelé exponentiation binaire, à cause du lien avec l’écriture de \(n\) en base \(2\).

Exercice: Étudiez le rapport entre l’exponentiation binaire et l’écriture de \(n\) en base \(2\) et donnez-en une version itérative (c’est à dire avec des boucles for ou while et pas d’appels récursifs).

Pour approfondir

La Tour de Hanoï

Allez voir cet exercice

Fork me on GitHub