Récursivité

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

Récursivité : notion et exemples.¶

Quelques exemples¶

Toutes ces images ont un point commun : on dit qu'elles sont autoréférentes : on trouve dans l'image une référence à l'image elle-même.

Un procédé (au sens large) est dit récursif lorsqu'il possède la propriété de faire référence à lui-même à un moment donné lors de la description de ce procédé.

Certains objets de la vie courante peuvent être définis de manière récursive :

lors d'une mise en abîme
dans un arbre généalogique

Application aux algorithmes¶

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

Énoncé du problème. Pour tout entier $n\in \mathbb{N}^{*}$, on définit le problème $\mathcal{P}(n)$ suivant :

« Calculer la somme des $n$ premiers entiers : $S = 1 + 2 + 3 + \ldots + n$ »

Méthode 1. Il est possible d'écrire une fonction python itérative (avec une boucle), qui prenne en entrée un entier n et qui renvoie l'entier S associé :

def somme(n):
    """ int -> int"""
    S = 0
    for i in range(1, n + 1):
        S = S + i
    return S

Méthode 2. Il est possible d'écrire une fonction python récursive (faisant référence à elle-même), qui prenne en entrée un entier n et qui renvoie l'entier S associé :
1. On sait résoudre le problème dans le cas où $n = 1$. Dans ce cas la solution est $S = 1$.
2. Dans le cas général, on veut résoudre le problème de difficulté $n$, c'est à dire $\mathcal{P}(n) : $ « Calculer la somme des $n$ premiers entiers : $S = 1 + 2 + 3 + \ldots + n$ ».
  1. On suppose que l'on connait la réponse $S'$ au problème de difficulté $n - 1$. On connait donc $S' = 1 + 2 + 3 + \ldots + n - 1$.
  2. À l'aide de $S'$, on construit $S$ la solution au problème $\mathcal{P}(n)$. Il suffit de remarquer que : $S = 1 + 2 + 3 + \ldots + (n - 1) + n = S' + n$
3. On aboutit donc au code python ci-dessous :
  1 2 3 4 5 6 7 8
  def somme(n): # Cas de base: if n == 1: return 1 # Cas général else: Sp = somme(n - 1) # appel dit récursif return Sp + n

Remarque. On peut faire le lien avec la définition par récurrence de la suite $u_n = \text{somme}(n)$, définie pour tout $n \geq 1$ par :

$ u_{n} = \begin{cases} 1&\text{si } n = 1\\ u_{n - 1} + n &\text{sinon.} \end{cases}$

On considère un problème à résoudre, qui dépend d'un certain paramètre $n \in \mathbb{N}$, que l'on appelle le rang (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 $1$)
Résoudre le problème de manière récursive.
- On suppose connue la solution des problèmes de rang strictement inférieur à $n$.
- On construit la solution du problème de rang $n$ à l'aide de la solution d'un problème de rang inférieur.

Récursivité : première application¶

$(u_n)$ est une suite arithmétique de raison $5$ et de premier terme $u_0 = 2$. Écrire une fonction python récursive u qui étant donné un entier $n$ calcule $u_n$.

def u_n(n):
    """ int -> int """
    # Cas de base
    if n <= 0:
        return 2
    else:
        avant = u(n - 1) # appel récursif
        return 5 + avant

$(v_n)$ est une suite géométrique de raison $-2$ et de premier terme $v_0 = 8$. Écrire une fonction python récursive v qui étant donné un entier $n$ calcule $v_n$.

def v(n):
    """ int -> int """
    # Cas de base
    if n <= 0:
        return 8
    else:
        avant = v(n - 1) # appel récursif
        return -2*avant