Récursivité

Un objet récursif est un objet qui, dans sa définition, se sert de lui-même.

Vocabulaire

Le mot récursif provient du latin recurrere qui signifie littéralement « revenir en arrière ».

Fonction récursive

Une fonction sera dite récursive lorsqu'elle s’appelle elle-même.

L'utilité d'une telle fonction sera souvent de se ramener à un problème similaire mais de taille plus petite :

1. la fonction va s'appeler elle-même avec un paramètre « plus petit » ;
2. cet appel va en générer un autre, puis un autre, etc... ;
3. la taille du problème va ainsi diminuer.

Un risque est que ces appels successifs soient sans fin. Il est donc nécessaire d'identifier un problème élémentaire que l'on sait résoudre et indiquer que ce problème élémentaire est la condition d'arrêt des appels récursifs.

Méthode

Pour définir une fonction récursive, il faut :

• qu’elle s’appelle elle-même ;
• qu’elle possède une condition d’arrêt.

Exemple

On considère la fonction spirale() définie ci-dessous, dont le paramètre est n (entier).
On admet que les vérifications sur le type de n ont été réalisées avant l'appel à la fonction spirale().

from turtle import *

def spirale(n):
    """
    n - entier
    Sortie: None - Tracé d'une spirale dans la fenêtre turtle
    """
    if n >= 1:
        forward(n)
        left(90)
        spirale(n-1)

• La condition d'arrêt est présente.
  Seuls les paramètres entiers positifs non nuls permettent d'exécuter les instructions de la fonction.
• Cette fonction s'appelle elle-même en ligne 11.
• Le paramètre d'appel diminue.
  Toujours en ligne 11, ce paramètre est à présent n-1.
• Cette condition d'arrêt se réalisera forcément.
  Seuls les entiers n strictement positifs permettent d'exécuter les instructions de la fonction. Dans ce cas, à chaque appel récursif, la valeur du paramètre va diminuer de 1 et deviendra forcément strictement inférieur à 1 à un moment.

Terminaison d'une fonction récursive

Problématique

Est-on certain que, pour n'importe quelle entrée, la fonction récursive se terminera ?

Cette question se ramènera souvent à prouver que les appels successifs ne soient pas sans fin.

Nous allons, comme en classe de première, utiliser la notion de variant de boucle pour justifier qu'une fonction récursive se termine.

Rappel - variant de boucle

En classe de Première et Terminale, on peut par exemple utiliser la définition suivante :

On appelle variant d'une boucle toute quantité $v$ telle que :

• $v \in \mathbb{N}$
• $v$ décroit strictement à chaque passage dans la boucle.

Exemple

On considère les fonctions définies ci-dessous, dont les paramètres sont des entiers.
On admet que les vérifications sur le type de ces paramètres ont été réalisés avant l'appel à la fonction carres_emboites().

from turtle import *

def carre(n):
    """
    n - entier
    Sortie: None - Tracé d'un carré dans la fenètre turtle
    """
    for i in range(4):
        forward(n)
        left(90)

def deplacer(e):
    """
    e - entier
    Sortie: None - déplacement sans tracer d'un  espace e
            (en largeur puis en hauteur) dans la fenètre turtle
    """
    up()
    forward(e)
    left(90)
    forward(e)
    right(90)
    down()


def carres_emboites(n):
    if n == 5:
        carre(5)
    else:
        carre(n)
        deplacer(5)
        carres_emboites(n-5)

1. Copiez/collez tout ce code puis exécutez l'appel carres_emboites(100).
2. Justifiez que la fonction carres_emboites() est récursive.
3. Justifiez que cette fonction ne termine pas nécessairement (on pourra donner un exemple d'appel à carres_emboites() qui conduit à un comportement non souhaité).
4. Améliorez la condition d'arrêt pour qu'elle prenne en compte tous les cas possibles.
5. Justifiez qu'alors la fonction carres_emboites() termine en utilisant la technique du variant de boucle.

Des réponses

1. On obtient :

2. La fonction carres_emboites() :

   1. possède un test d'arrêt ;
   2. s'appelle elle-même ;
   3. avec un paramètre entier dont la valeur diminue strictement.

3. L'appel carres_emboites(103) par exemple...
   Testez-le si vous n'aviez pas trouvé d'exemple de comportement non souhaité puis essayez de justifier ce comportement.

   Attention

   Avoir une variable dont les valeurs décroissent strictement ne suffit pas à définir un variant et à justifier que les appels récursifs cesseront.
   En effet, si la condition d'arrêt des appels récursifs n'est jamais mise en défaut par les valeurs de cette variable, la pile d'appels (cf. cours suivant) se remplira indéfiniment.

4. Par exemple :

   def carres_emboites(n):
       if n >= 5:
           carre(n)
           deplacer(5)
           carres_emboites(n-5)
   

5. Justifions que n est un variant de boucle :

   • n est un entier positif dans l'appel récursif de carres_emboites() car on n'entre dans cet appel que si n >= 5.
     • n diminue strictement à chaque appel récursif puisque l'appel suivant s'effectue en remplaçant n par n-5.

Par conséquent, au bout d'un certain nombre d'appels récursifs, n deviendra strictement inférieur à 5 et le test n >= 5 deviendra faux.

On a trouvé un variant de boucle donc les appels récursifs se terminent.

Calcul et renvoi de valeurs

Une fonction récursive peut aussi renvoyer une valeur. Pour cela elle doit :

• Renvoyer la (ou les) valeurs du (des) cas de base ;
• Renvoyer l'appel récursif suivant de cette fonction.

Exemple

On appelle factorielle de l'entier $n$ le calcul $1 \times 2 \times 3 \times \dots \times (n-1) \times n$. Le but de cet exemple est de programmer une version récursive du calcul de la factorielle d'un entier n.

1. Déterminez le (ou les) cas de base.
2. Exprimer factorielle(n) en fonction de factorielle(n-1).
3. En déduire la définition récursive de la fonction factorielle() :

   def factorielle_rec(n):
       """
       n - entier positif ou nul
       Sortie: entier - le produit des entiers naturels de 1 à n
       """
   

Des réponses

1. n doit être un entier strictement positif (car la multiplication par $0$ renvoie $0$). Par conséquent, le cas de base est factorielle(1) = 1.

2. factorielle(n) = n × factorielle(n-1).

3. Version récursive de la fonction factorielle() :

   def factorielle_rec(n):
       """
       n - entier positif ou nul
       Sortie: entier - le produit des entiers naturels de 1 à n
       """
       if n == 1 :
           return n
       else:
           return n * factorielle_rec(n-1)