Cours

Vous ne pouvez pas comprendre la récursivité sans avoir d’abord compris la récursivité.

Autoréférence et fonctions récursives¶

Toutes ces images ont pour point commun d'être autoréférentes : cela veut dire que l'image faut référence à elle-même. Ce phénomène peut être retrouvé dans de multiples domaines, comme par exemple :

en logique avec des phrases comme « Cet énoncé comporte trente lettres. », ou bien « Cet phrase est fausse. » ;
en mathématiques avec les fractales ;
en linguistique, car la phrase Dorothée pense que les sorcières sont dangereuses peut être définie comme une structure composée d'un sujet (Dorothée), d'un verbe (pense que), et d'une phrase (les sorcières sont dangeureuses) ;

Il est également possible d'écrire des programmes qui font référence à eux-mêmes dans leur code.

Toute fonction calculable (au sens intuitif) est récursive (au sens large).

Un exemple typique¶

Entrée. Un entier $n$ . Problème. Calculer $S = 1 + 2 + 3 + \ldots + n$

On peut résoudre ce problème en écrivant une fonction somme_premiers qui étant donné un entier n strictement positif renvoie la valeur de la somme des n premiers entiers. Par exemple avec une méthode dite itérative : on accumule dans une variable S les valeurs des nombres compris entre $1$ et $n$ .

def somme_premiers(n):
    """ int -> int
    Calcule 1 + 2 + 3 + ... + n """
    S = 0
    for i in range(1, n + 1):
        S = S + i
    return S

>>> print(somme_premiers(5))
15
>>> print(somme_premiers(10))
55

On peut également mettre en place une méthode dite récursive :

On sait résoudre le problème dans un cas simple, par exemple lorsque $n = 1$ . En effet dans ce cas $S = 1$ .
Dans le cas général, lorsque l'on cherche à résoudre le problème de difficulté $n$ :
- on suppose, en utilisant le principe d'autoréférence que l'on sait résoudre le problème lorsque celui-ci est de difficulté inférieure. On sait donc calculer $S' = 1 + 2 + 3 + \ldots + (n - 1)$ .
- Pour résoudre le problème de difficulté $n$ on calcule donc $S' + n = 1 + 2 + \ldots + (n - 1) + n$ .

Traduit en python cela donne :

def somme_premiers(n):
    """ int -> int
    Calcule 1 + 2 + 3 + ... + n """
    # Cas de base
    if n == 1:
        return 1
    # Cas général
    else:
        Sp = somme_premiers(n - 1)
        return Sp + n

>>> print(somme_premiers(5))
15
>>> print(somme_premiers(10))
55

On parle ici de fonction récursive : il y a un appel récursif somme_premiers(n - 1) dans le corps de la fonction somme_premiers, autrement dit le programme fait référence à lui-même dans son code.

Conclusion et méthode¶

On considère un problème à résoudre, qui dépend d’un certain paramètre $n$ , que l’on appelle le rang (ou la "difficulté") du problème. Pour écrire un algorithme de manière récursive, la méthode générale est la suivante :

Identifier le cas de base. Il s’agit de trouver dans quel cas la résolution du problème est "simple" (souvent $n = 0$ ou $n = 1$ ).
Résoudre le problème de manière récursive. Pour cela :
- On suppose que quelqu’un résout à notre place les problèmes de rang strictement inférieur à $n$ . On considère donc que l'on connait la solution des problèmes de rangs $n - 1$ , $n - 2$ etc.
- On résout le problème de rang $n$ en utilisant la solution d’un (ou plusieurs) problèmes de rang inférieur.