Recursivité

3 - Fonctionnement par un exemple

⇩ ⇧ ⤊

En classe de première, de nombreux programmes sont écrits avec des boucles et des affectations.

La notion de fonction permet en particulier d'éviter de réécrireun code similaireà plusieurs endroits d'un programme.

Le style de programmation est :

• impétatif, les séquences d'instructionssonr exécutées l'une après l'autre;
• itératif, des instructions sont exécutéesdans des boucles while ou for

Différents styles de programmations seront présentés dans un prochain chapitre.

Définitions

Fonction récursive

• Une fonction est dite récursive si elle s'appelle elle même.

Nous parlons alors d'appel récursif.

• De manière générale, un sous programme est dit récursif s'il s'appelle lui même.

Exemple : la somme des n premiers entiers

• Pour définir la somme des n premiers entiers, on a l’habitude d’écrire la formule suivante :
0 + 1 + 2 + ... + n

• Autre méthode

  Il existe en effet une autre manière d’aborder ce problème. Il s’agit de définir une fonction mathématique somme(n) qui, pour tout entier naturel n, donne la somme des n premiers entiers de la manière suivante :

  

  Cette définition nous indique ce que vaut somme(n) pour un entier n quelconque,selon que n soit égal à 0 ou strictement positif.

  Ainsi, pour n = 0,la valeur de somme(0) est simplement 0.
  Dans le cas où n est strictement positif, la valeur de somme(n) est n + somme(n − 1).

  Par exemple

  voici ci-dessous les valeurs de somme(n), pour n valant 0, 1, 2 et 3.

  

  Comme on peut le voir, la définition de somme(n) dépend de la valeur de somme(n − 1).
  Il s’agit là d’une définition récursive, c’est-à-dire d’une définition de fonction qui fait appel à elle-même.
  Ainsi, pour connaître la valeur de somme(n), il faut connaître la valeur de somme(n − 1), donc connaître la valeur de somme(n−2), etc.
  Ceci jusqu’à la valeur de somme(0) qui ne dépend de rien et vaut 0.

  La valeur de somme(n) s’obtient en ajoutant toutes ces valeurs.

• Principe de la recursivité

L’intérêt de cette définition récursive de la fonction somme(n) est qu’elle est directement calculable, c’est-à-dire exécutable par un ordinateur.
En particulier, cette définition est directement programmable en Python, comme le montre le code ci-dessous:

def somme(n):
    if n == 0:
        return 0
    else:
        return n + somme(n-1)




L’analyse par cas de la définition récursive est ici réalisée par une instruction conditionnelle pour tester si l’argument n est égal à 0.
Si c’est le cas, la fonction renvoie la valeur 0, sinon elle renvoie la somme n + somme(n - 1).

Cet appel à somme(n - 1) dans le corps de la fonction est un appel récursif , c’est-à-dire un appel qui fait référence à la fonction que l’on est en train de définir.

On dit de toute fonction qui contient un appel récursif que c’est une fonction récursive.

Exemple pour n = 3

l’évaluation de l’appel à somme(3) peut se représenter de la manière suivante

où on indique uniquement pour chaque appel à somme(n) l’instruction qui est exécutée après le test n == 0 de la conditionnelle.
Cette manière de représenter l’exécution d’un programme en indiquant les différents appels effectués est appelée arbre d’appels.




Ainsi, pour calculer la valeur renvoyée par somme(3), il faut tout d’abordappeler somme(2).
Cet appel va lui-même déclencher un appel à somme(1),qui à son tour nécessite un appel à somme(0).
Ce dernier appel se termine directement en renvoyant la valeur0.

Le calcul de somme(3) se fait donc « à rebours ».
Une fois que l’appel à somme(0) est terminé, c’est-à-dire que la valeur 0 a été renvoyée,
l’arbre d’appels a la forme suivante, où l’appel à somme(0) a été remplacé par 0 dans l’expression return 1 + somme(0).

À cet instant, l’appel à somme(1) peut alors se terminer et renvoyer le résultat de la somme 1 + 0.
L’arbre d’appels est alors le suivant.

Enfin, l’appel à somme(2) peut lui-même renvoyer la valeur 2 + 1 comme résultat,
ce qui permet à somme(3) de se terminer en renvoyant le résultat de 3 + 3.

On obtient bien au final la valeur 6 attendue

Eléments Caractéristiques

1. il faut au moins une situation qui ne consiste pas en un appel récursif.

                
                if n == 0:
                    return 0
                
            

Cette situation est appelée situation de terminaison ou situation d’arrêt ou cas d’arrêt ou cas de base.

2. chaque appel récursif doit se faire avec des données qui permettent de se rapprocher d’une situation de terminaison.

                
                return n + somme(n-1)
                
            

Il faut s’assurer que la situation de terminaison est atteinte après un nombre fini d’appels récursifs.

4 - Aures Exemples

⇩ ⇧ ⤊

Exemple 1 : La fonction Factorielle

la fonction factorielle est définie, pour tout entier naturel n par (noté : n!) :

• 0! = 1
• n! = n x (n-1)! si n > 1

Principe :

  5! = 5 x 4!
     = 5 x 4 x 3!
     = 5 x 4 x 3 x 2!
     = 5 x 4 x 3 x 2 x 1!
     = 5 x 4 x 3 x 2 x 1 x 0!
     = 5 x 4 x 3 x 2 x 1 x 1
     = 120

Programmation

def fact(n):
    if n <= 1:
        return 1
    else:
        return n * fact(n-1)

>>> fact(5)
120

Déroulement de l’exécution

Mise en évidence :

On utilise une application en ligne PythonTutor

Exemple 2 : Calculer le nombre d’occurrences d’un caractère dans une chaîne

Il faut trouver un énoncé récursif de résolution du problème, c’est-à-dire un énoncé qui fasse référence au problème lui-même

Énonce

s la chaine de caractères et c est le caractère cherché.
• Le nombre d’occurrences de c dans s est 0 si s est vide.
• Si c est le premier caractère de s, on ajoute 1 au nombre d’occurrences de c dans les autres caractères de s.
• Sinon, il s’agit du nombre d’occurrences de c dans les autres caractères de s.

Programmation

def occurrences(c,s):
    if s == "":
       return 0
    elif c == s[0]:
    	 return 1 + occurrences(c,s[1:])
    else:
         return occurrences(c,s[1:])

La terminaison se vérifie en considérant la suite des longueurs des chaînes passées en paramètre.

Déroulement de l’exécution

Mise en évidence :

On utilise une application en ligne PythonTutor

5 - Récursivité Terminale

⇩ ⇧ ⤊

Définition

Un algorithme récursif simple est terminal lorsque l’appel récursif est le dernier calcul effectué pour obtenir le résultat.

Il n’y a pas de “calcul en attente”.

L’avantage est qu’il n’y a rien à mémoriser dans la pile.

Ce n’est pas le cas des deux exemples précédents fact et occurrences.

Exemple d’algorithme récursif terminal

Prédicat de présence d’un caractère dans une chaîne

• Un caractère c est présent dans une chaîne s non vide, s’il est le premier caractère de s ou s’il est présent dans les autres caractères de s.
• Il n’est pas présent dans la chaîne vide.

Programmation

def est_present(c,s):
    if s == '':
        return False
    elif c == s[0]:
        return True
    else:
        return est_present(c,s[1:])
    

Déroulement de l’exécution

Mise en évidence :

On utilise une application en ligne PythonTutor.

Rendre terminal un algorithme récursif

Méthode

On utilise un accumulateur, passé en paramètre, pour calculer le résultat au fur et à mesure des appels récursifs.

La valeur de retour du cas de base devient la valeur initiale de l’accumulateur et lors d’un appel récursif, le “calcul en attente” sert à calculer la valeur suivante de l’accumulateur.

Ainsi on obtient :

def fact_term(n, acc = 1):
    if n <= 1:
        return acc
    else:
        return fact_term(n-1, acc * n)

et

def occurrences_term(c,s, acc = 0):
    if s == "":
       return acc
    elif c == s[0]:
         return occurrences_term(c,s[1:], acc + 1)
    else:
         return occurrences_term(c,s[1:], acc)