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 :

     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

1. $(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
   

2. $(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