31 - Récursivité avec Python

⏪

⏬

⏩

1 - Principe

2 - Pile

3 - Dépilement

4 - Exercices

5 - nature

6 - FAQ

La récursivité est un moyen efficace de programmer. Elle est très courante même si nous n'en avons pas encore parlé car elle nécessite d'avoir des connaissances assez précises des fonctions pour en comprendre réellement le fonctionnement.

Ca tombe bien : c'est maintenant votre cas.

Prérequis : les activités précédentes sur les fonctions

Logiciel nécessaire pour l'activité : Python 3 : Thonny, IDLE ...

Evaluation ✎ : questions 13-14-15-16-17-18-19-20

Résumé : Version HTML ou fond blanc ou ou PDF (couleur ou gris)

1 - Principe

⇩ ⇧ ⤊

01° Sans lancer ce code, écrire ce que va afficher, à votre avis, ce code à l'écran. Lancer ensuite le code pour visualiser le résultat réel.

def p(x):
    '''Procédure qui affiche un truc'''
    print(f"Début de la procédure p({x})")
 
for x in range(5,-1,-1):
    p(x)

Correction ?

...CORRECTION...

On crée une boucle bornée partant de 5, décroissante avec un pas de -1 et dont la borne limite exclue est -1. x varie donc de 5 à 0.


Début de la procédure p(5)
Début de la procédure p(4)
Début de la procédure p(3)
Début de la procédure p(2)
Début de la procédure p(1)
Début de la procédure p(0)

Il s'agit donc d'un appel successif à des fonctions. Une simple itération.

Mais nous pouvons faire la même chose avec un appel récursif :la procédure peut alors faire appel à une autre instance d'elle-même.

02° Observer le code ci-dessous sans le lancer.

Une fois arrivé en ligne 9,

quel va être le premier affichage sur la console ?
le programme va-t-il s'arrêter ou va-t-on lancer un nouvel appel ?
quel appel ?
que va-t-il afficher ? Que va-t-il activer ?

def p(x):
    '''Procédure qui affiche un truc'''
    print(f"Début de la fonction p({x})")
    if x == 0 :
        pass
    else :
        p(x-1)
 
p(5)

Correction ?

...CORRECTION...

On lance l'appel p(5). Cela va provoquer via la ligne 3 l'affichage suivant :


Début de la fonction p(5)

Comme x contient 5, on va en ligne 7.

On lance alors l'appel p(4). Cela va provoquer via la ligne 3 l'affichage suivant :


Début de la fonction p(4)

Comme x contient 4, on va en ligne 7.

On lance alors l'appel p(3). Cela va provoquer via la ligne 3 l'affichage suivant :


Début de la fonction p(3)

Comme x contient 3, on va en ligne 7.

On lance alors l'appel p(2). Cela va provoquer via la ligne 3 l'affichage suivant :


Début de la fonction p(2)

Comme x contient 2, on va en ligne 7.

On lance alors l'appel p(1). Cela va provoquer via la ligne 3 l'affichage suivant :


Début de la fonction p(1)

Comme x contient 1, on va en ligne 7.

On lance alors l'appel p(0). Cela va provoquer via la ligne 3 l'affichage suivant :


Début de la fonction p(0)

Comme x contient 0, on ne relance plus d'appel.

03° Lancer le code pour comparer à votre lecture du code.

On remarque tout de suite qu'il est nécessaire lors de l'utilisation de la récursivité d'avoir une condtion d'arrêt qui mène à un cas de base : un cas qui ne provoque plus d'appels récursifs.

Ici, la condition d'arrêt est donc x == 0 puisque cette expression évaluée à True ne provoque pas de nouvel appel à p.

def p(x):
    '''Procédure qui affiche un truc'''
    print(f"Début de la fonction p({x})")
    if x == 0 :
        pass
    else :
        p(x-1)
 
p(5)

04° Les lignes 4 et 5 sont-elles vraiment nécessaires ici ? Comment pourrait-on écrire cette fonction avec un test IF sans ELSE ?

Correction ?

...CORRECTION...

Non. Elles permettent juste de bien comprendre et montrer qu'il y a deux cas :

Le cas de base, non récursif
Le cas récursif : on fait encore appel à la fonction ou la procédure

def p(x):
    '''Procédure qui affiche un truc'''
    print(f"Début de la fonction p({x})")
    if x != 0 :
        p(x-1)
 
p(5)

05° Expliquer le problème qu'on va rencontrer sur ce code après l'avoir analysé. Il y a un problème. Cherchez bien.

def p(x):
    '''Procédure qui affiche un truc'''
    print(f"Début de la fonction p({x})")
    if x == 0 :
        pass
    else :
        p(x+1)
 
p(5)

Correction ?

...CORRECTION...

La récursivité provoque une boucle infinie : on ne pourra jamais atteindre la condition d'arrêt puisque les paramètres x deviennent de plus en plus grands. On ne pourra donc jamais valider la condition x == 0.

06° Même question.

def p(x):
    '''Procédure qui affiche un truc'''
    print(f"Début de la fonction p({x})")
    if x == 0 :
        pass
    else :
        p(x-2)
 
p(5)

Correction ?

...CORRECTION...

La récursivité provoque une boucle infinie : on ne pourra jamais atteindre le cas de base non-recursif puisque le paramètre x vaut successivement 5, 3, 1, -1, -3...

Encore une fois, on ne parviendra pas à s'arrêter.

Pour l'instant, nous n'avons utilisé que des procédures. Il s'agit donc d'une simple succession d'action, pas d'un calcul mémorisé.

Voyons un premier exemple classique : le calcul des séries arithmétiques, rencontrées dans la partie Algorithmique.

Pour rappel, voici la formule permettant de calculer la série arithmétique des nombres de 1 à n :

formule 1

07° Réaliser une fonction non récursive permettant de calculer cette série, sans utiliser la formule. Il faut imposer à votre fonction de calculer 1 + 2 + 3 + ... jusqu'à n.

On notera que la fonction fournie possède déjà :

Une documentation pouvant servir au module doctest.
Deux assertions permettant d'imposer la précondition sur le paramètre n qui doit être entier et strictement positif.

def serie_1(n):
    '''Renvoie le résultat de la somme des entiers de 1 à n
 
    :: param n(int) :: un entier positif non nul
    :: return (int) :: la somme voulue 1 + 2 + .. + n-1 + n
 
    :: exemple ::
    >>> serie_1(1)
    1
    >>> serie_1(2)
    3
    >>> serie_1(3)
    6
    >>> serie_1(4)
    10
    >>> serie_1(20)
    210
 
    '''
    assert isinstance(n, int), "Le paramètre doit être un entier"
    assert n > 0, "Le paramètre n doit être supérieur à 0"
    return 0
 
if __name__ == '__main__' :
    import doctest
    doctest.testmod()

Correction ?

...CORRECTION...

def serie_1(n):
    '''Renvoie le résultat de la somme des entiers de 1 à n
 
    :: param n(int) :: un entier positif non nul
    :: return (int) :: la somme voulue 1 + 2 + .. + n-1 + n
 
    :: exemple ::
    >>> serie_1(1)
    1
    >>> serie_1(2)
    3
    >>> serie_1(3)
    6
    >>> serie_1(4)
    10
    >>> serie_1(20)
    210
 
    '''
    assert isinstance(n, int), "Le paramètre doit être un entier"
    assert n > 0, "Le paramètre n doit être supérieur à 0"
    somme = 0
    for x in range(n+1):
        somme = somme + x
    return somme
 
if __name__ == '__main__' :
    import doctest
    doctest.testmod()

Comme on le voit, il y a une grande différence entre le code informatique permettant de calculer cette série (on doit créer une boucle et une variable permettant de stocker les additions successives) et sa définition mathématique (une simple addition 1 + 2 +3 + 4 + ...).

La programmation récursive va nous permettre de coder une fonction dont le code se rapproche de la version mathématique.

Définition récursive de la somme des entiers

Si on utilise cette définition, on doit alors réfléchir de cette façon :

f(5) = 5 + f(4)

f(5) = 5 + 4 + f(3)

f(5) = 5 + 4 + 3 + f(2)

f(5) = 5 + 4 + 3 + 2 + f(1)

f(5) = 5 + 4 + 3 + 2 + 1 + f(0)

f(5) = 5 + 4 + 3 + 2 + 1 + 0

08° Analyser la fonction récursive. Comparer son code à la version récursive de la somme des n premiers entiers.

Questions :

pourquoi est-ce bien une fonction et plus une procédure ?
quelle est la version la plus proche de la version mathématique : la fonction itérative ou la fonction récursive ?

def f(x):
    '''Fonction récursive fournissant la somme des n premiers entiers'''
    print(f"Début de la fonction f({x})")
    if x == 0 :
        return 0
    else :
        return x + f(x-1)
 
f(5)

Le résultat des appels dans la console affiche encore l'activation progressive des fonctions.

Correction ?

...CORRECTION...

Il s'agit bien d'une fonction car cette fois on renvoie un résultat.

On voit bien que c'est cette version récursive qui se rapproche le plus de la définition mathématique précédente. Plus de variable temporaire à créer. On a bien uniquement les deux cas : le cas de base et le cas itératif.

Fonction récursive

Une fonction récursive est par définition une fonction qui peut s'appeler elle-même.

Elle doit en effet posséder au moins deux modes de calcul :

Un cas récursif où on a besoin de lancer à autre appel à la fonction (en modifiant éventuellement les paramètres d'appel)

Un cas de base non récursif qui permet d'obtenir une possibilité d'arrêt. On obtient ce cas lorsque la condition d'arrêt est validée.

On notera qu'il faut être vigilant sur cette condition d'arrêt : elle doit pouvoir être atteinte, sinon on obtient en théorie une boucle infinie d'appels récursifs.

2 - Empilement et dépilement

⇩ ⇧ ⤊

Maintenant que vous avez compris le déroulement global d'une fonction récursive, regardons comment fait l'ordinateur concrétement pour réaliser ce calcul.

Regardons à nouveau notre fonction.

def f(x):
    '''Fonction récursive fournissant la somme des n premiers entiers'''
    print(f"Début de la fonction f({x})")
    if x == 0 :
        return 0
    else :
        return x + f(x-1)
 
f(5)

Lors de l'appel à f(5), on voit donc que la fonction renvoie 5 + f(4).

09° La fonction f(5) peut-elle renvoyer directement un résultat au programme qui l'a appelé ou doit-elle d'abord calculer quelque chose ?

Correction ?

...CORRECTION...

On constate bien que la fonction ne peut rien renvoyer pour l'instant : elle doit renvoyer 5 + f(4) mais ne connait pas le résulat de f(4).

Avant de renvoyer le résultat de f(5) au programme principal, il va donc falloir renvoyer le résultat de f(4) à f(5).

10° Observer le déroulement du programme sur le site Python Tutor, ou utiliser le mode DEBUG progressif de Thonny si vous ne parvenez pas à aller sur Python Tutor.

Vous devriez avoir visualisé le déroulement progressif du calcul :

Le programme principal active f(5). Cette fonction veut renvoyer 5 + f(4). On met donc cette fonction en pause et on lance la suite.
f(5) active f(4). Cette fonction veut renvoyer 4 + f(3). On met donc cette fonction en pause et on lance la suite.
f(4) active f(3). Cette fonction veut renvoyer 3 + f(2). On met donc cette fonction en pause et on lance la suite.
...

Mais du coup, comment est-ce que ça fonctionne ? Comment la fonction sait à qui répondre une fois qu'elle a fini son travail ?

Culture générale : pile d'exécution, cas stack en anglais

La pile d'exécution est la structure de données dans laquelle on enregistre les informations sur les appels de fonctions dans un programme informatique.

Sans rentrer dans les détails, on va donc empiler à partir d'une adresse de départ fondamentalement 3 types d'information pour chaque fonction active :

Les paramètres enregistrés lors de l'appel
L'adresse à laquelle le return doit renvoyer la réponse
Les variables locales qu'elle utilise lors de son exécution

Si nous simplifions la notion pour n'en garder que ce qui nous interesse aujourd'hui, voici le contenu de la pile au fur et à mesure de l'exécution de notre fonction f(5)

On commence avec f(5) qui demande l'appel de f(4)

La pile avec f(5) et f(4)

Du coup f(4) demande l'appel de f(3)

La pile avec f(5) à f(3)

On continue avec f(3) demande l'appel de f(2)

La pile avec f(5) à f(2)

Et, nous allons accumuler sur cette pile, les appels récursifs jusqu'à arriver à la condition d'arrêt. Ici, elle apparaît lors de l'appel à f(0).

Voici la pile d'exécution lorsqu'on en arrive là :

La pile avec f(5) à f(0)

En anglais, on dira call stack.

11° Continuer cette autre représentation des appels successifs imbriqués les uns dans les autres.


f(5) va renvoyer 5 + f(4)
                     |
                    va renvoyer 4 + f(3)
                                    |

Correction ?

...CORRECTION...


f(5) renvoie 5 + f(4)
                  |
                va renvoyer 4 + f(3)
                                 |
                                va renvoyer 3 + f(2)
                                                 |
                                               va renvoyer 2 + f(1)
                                                                |
                                                              va renvoyer 1 + f(0)
                                                                               |
                                                                           renvoie 0

12° Continuer cette dernière représentation des appels successifs imbriqués les uns dans les autres.


Appel à f(5) va renvoyer 5 + f(4)
    Appel à f(4) va renvoyer 4 + f(3)
        Appel à ...

Correction ?

...CORRECTION...


Appel à f(5) va renvoyer 5 + f(4)
    Appel à f(4) va renvoyer 4 + f(3)
        Appel à f(3) va renvoyer 3 + f(2)
            Appel à f(2) va renvoyer 2 + f(1)
                Appel à f(1) va renvoyer 1 + f(0)
                    Appel à f(0) renvoie 0

3 - Dépilement

⇩ ⇧ ⤊

Une fois le cas de base atteint, on ne rajoute plus rien sur la pile.

On peut maintenant calculer les réponses à renvoyer aux fonctions ayant lancé les appels pour qu'elles puissent évaluer leurs propres réponses.

Nous venons donc de trouver f(0) peut renvoyer 0 à f(1).

f(0) renvoie 0

Du coup, f(1) peut renvoyer 1+0 soit 1 à f(2).

f(1) renvoie 1

On continue : f(2) peut renvoyer 2+1 soit 3 à f(3).

f(2) renvoie 3

Du coup, f(3) va renvoyer 3+3 soit 6 à (4).

f(4) va donc renvoyer 4+6 soit 10 à f(5).

En finalement, f(5) peut renvoyer 5+10 ou 15 au programme principal.

Et voilà donc le schéma global de l'empilement et du dépilement :

✎ 13° Expliquer la réponse obtenue après dépilement en utilisant cette autre représentation de l'empilement.


f(5) renvoie 5 + f(4)
                  |
                renvoie 4 + f(3)
                              |
                           renvoie 3 + f(2)
                                        |
                                    renvoie 2 + f(1)
                                                 |
                                              renvoie 1 + f(0)
                                                           |
                                                       renvoie 0

✎ 14° Expliquer la réponse obtenue après dépilement en utilisant cette autre représentation de l'empilement.


Appel à f(5) renvoie 5 + f(4)
    Appel à f(4) renvoie 4 + f(3)
        Appel à f(3) renvoie 3 + f(2)
            Appel à f(2) renvoie 2 + f(1)
                Appel à f(1) renvoie 1 + f(0)
                    Appel à f(0) renvoie 0

4 - Exercices de programmation

⇩ ⇧ ⤊

Voyons maintenant si vous parvenez à réaliser vous-mêmes quelques fonctions récursives, simples ou pas.

✎ 15° Réaliser une fonction produit récursive correspondant à cette manière de voir la multiplication : 5 * 6 = 5+5+5+5+5+5.

Attention aux spécifications d'entrée : n et p sont des entiers, p étant positif.

Définition récursive de la multiplication des entiers

✎ 16° Quelle est la condition d'arrêt de votre fonction ? Quel est son cas de base ? Montrer son empilement et son dépilement pour produit(5,3)

✎ 17° Réaliser une fonction puissance récursive correspondant à cette manière de voir la multiplication : 5⁶ = 5*5*5*5*5*5.

Attention aux spécifications d'entrée : x et n sont des entiers, n étant positif.

✎ 18° Quelle est la condition d'arrêt de votre fonction ? Quel est son cas de base ? Montrer son empilement et son dépilement pour puissance(5,3)

✎ 19° Réaliser une fonction factorielle récursive correspondant à la définition de la factorielle d'un entier : 5! = 5*4*3*2*1.

Attention aux spécifications d'entrée : n est un entier positif.

✎ 20° Quelle est la condition d'arrêt de votre fonction ? Quel est son cas de base ? Montrer son empilement et son dépilement pour factorielle(5)

5 - Récursivité dans la nature

⇩ ⇧ ⤊

La nature regorge de structure de ce genre. Vous avez déja regardé un brocolis de près ?

Voici un programme comportant une procédure permettant de tracer la courbe de Kock.

21° Tester le programme avec des valeurs plus petites de n valant 0, puis 1, puis 2... pour voir le principe.

import turtle as trt
 
def trace(crayon, n, longueur):
    if n == 0 :
        crayon.forward(longueur)
    else :
        trace(crayon, n-1, longueur//3)
        crayon.left(60)
        trace(crayon, n-1, longueur//3)
        crayon.right(120)
        trace(crayon, n-1, longueur//3)
        crayon.left(60)
        trace(crayon, n-1, longueur//3)
 
 
if __name__ == '__main__' :
    crayon = trt.Turtle()
    trace(crayon, 3, 400)

6 - FAQ

⇩ ⇧ ⤊

Rien pour l'instant

Activité publiée le 10 09 2020
Dernière modification : 26 10 2020
Auteur : ows. h.

⏪

⏫

⏩