Aller au contenu

Chapitre 2 : Récursivité⚓︎

Carnet Jupyter à télécharger ici

Le but de ce chapitre est d'introduire le concept de fonction récursive.

Notion de fonction récursive⚓︎

Il s'agit d'une fonction qui fait appel à elle-même lors de son exécution.

Premier exemple : calcul de la somme des entiers compris entre a et b⚓︎

On suppose que a est inférieur à b et on souhaite définir une fonction somme qui calcule la somme des entiers compris entre a et b.

Fonction somme

Détermine la somme des entiers compris entre a et b.

Entrées

  • a : entier
  • b : entier supérieur ou égal à a

Sortie

  • total : entier
Implémentation

Une première façon de faire est d'utiliser une boucle pour : on obtient une version itérative de la fonction.

1
2
3
4
5
def somme(a, b):
    total = 0
    for k in range(a, b+1):
        total = total + k
    return total

Une autre façon de faire est de constater qu'il y a deux cas à envisager :

  • Si a == b, cela signifie qu'il y a un seul nombre dans la liste des nombres à additionner : le nombre a. On renvoie donc sa valeur.
  • Si a < b, on calcule récursivement la somme des entiers compris entre a+1 et b, on y ajoute la valeur de a et on renvoie le total.
1
2
3
4
5
6
def somme(a, b):
    if a == b:
        total = a
    else:
        total = a + somme(a+1, b)
    return total

Ainsi définie, la fonction est une fonction récursive parce qu'elle s'appelle elle-même dans le cas où a est différent de b.

On distingue deux parties dans l'écriture d'une fonction récursive :

  • un ou plusieurs cas résursif(s), dans lesquels la fonction fait appel à elle-même avec de nouveaux arguments,
  • un ou plusieurs cas de base, qui permettent de mettre un terme aux appels récursifs successifs.

Deuxième exemple : calcul du produit des entiers compris entre 1 et n⚓︎

On suppose que n est un entier strictement positif et on souhaite définir une fonction factorielle qui calcule le produit des entiers compris entre 1 et n.

Fonction factorielle

Détermine le produit des entiers compris entre 1 et n.

Entrée

  • n : entier strictement positif

Sortie

  • fac : entier
Implémentation 
1
2
3
4
5
def factorielle(n):
    fac = 1
    for k in range(2, n+1):
        fac = k * fac
    return fac

Pour l'écriture de la fonction récursive, deux cas à sont envisager :

  • Si n == 1, cela signifie qu'il y a un seul nombre dans la liste des nombres à multiplier : le nombre 1. On renvoie donc sa valeur. C'est le cas de base.
  • Si n > 1, on calcule récursivement le produit des entiers compris entre 1 et n-1, on multiplie le résultat par la valeur de n et on renvoie le total. C'est le cas récursif.
1
2
3
4
5
6
def factorielle(n):
    if n == 1:
        fac = 1
    else:
        fac = n * factorielle(n-1)
    return fac

Troisième exemple : calcul de x puissance n⚓︎

On suppose que x est un nombre et que n est un entier positif et on souhaite définir une fonction puissance qui calcule x puissance n.

Fonction puissance

Détermine la valeur de x puissance n.

Entrées

  • x : entier ou flottant
  • n : entier positif

Sortie

  • val : même type que le paramètre d'entrée x
Implémentation 
1
2
3
4
5
def puissance(x, n):
    val = 1
    for k in range(1, n+1):
        val = x * val
    return val

Pour l'écriture de la fonction récursive, deux cas à sont envisager :

  • Si n == 0, on utilise la propriété \(x^0 = 1\) : on renvoie la valeur 1. C'est le cas de base.
  • Si n > 0, on utilise la propriété \(x^n = x \times x^{n-1}\) : on calcule récursivement \(x^{n-1}\), on multiplie le résultat par la valeur de x et on renvoie le total. C'est le cas récursif.
1
2
3
4
5
def puissance(x, n):
    if n == 0:
        return 1
    else:
        return x * puissance(x, n-1)

Pile d'appels récursifs⚓︎

Si on effectue l'appel puissance(2, 3), on peut représenter la pile des quatre appels de la fonction puissance, et les paramètres correspondant à chaque appel, sous la forme d'un arbre.

1
2
3
4
5
6
7
8
9
puissance(2, 3)
    |
    return 2 * puissance(2, 2)
                   |
                   return 2 * puissance(2, 1)
                                  |
                                  return 2 * puissance(2, 0)
                                                 |
                                                 return 1

Le nombre d'appels simultanés de fonctions est limité. On peut en connaître le nombre maximal grâce à la fonction getrecursionlimit du module sys.

1
2
from sys import getrecursionlimit
print(getrecursionlimit())

Une erreur apparaît si on essaie de réaliser plus d'appels récursifs que la limite autorisée.

1
RecursionError: maximum recursion depth exceeded in comparison

La limite du nombre d'appels simultanés de fonctions peut être modifiée grâce à la fonction setrecursionlimitdu module sys.

1
2
from sys import setrecursionlimit
setrecursionlimit(4000)

Il faut néanmoins être raisonnable en cas de modification de cette limite, car un nombre excessif de récursions provoque le plantage du programme à cause d'une erreur de débordement de pile d'exécution (stack overflow).

Tours de Hanoï⚓︎

Les tours de Hanoï sont un jeu de réflexion consistant à déplacer des disques de diamètres différents d'une tour gauche à une tour droite en passant par une tour centrale, et ceci en un minimum de coups, tout en respectant les règles suivantes :

  • on ne peut pas déplacer plus d'un disque à la fois,
  • on ne peut placer un disque que sur un autre disque plus grand ou sur un emplacement vide.

Ce jeu est un exemple de problème qui peut être résolu par une approche récursive.

Procédure solution_hanoi

Affiche les mouvements à effectuer pour résoudre le problème des tours de Hanoï à n disques.

Entrées

  • n : entier positif (nombre de disques)
  • depart : chaîne de caractères (nom de la tour de départ)
  • intermediaire : chaîne de caractères (nom de la tour intermédiaire)
  • arrivee : chaîne de caractères (nom de la tour d'arrivée)

Effet de bord : affichage de texte à l'écran

Implémentation 
1
2
3
4
5
def solution_hanoi(n, depart, intermediaire, arrivee):
    if n > 0:
        solution_hanoi(n-1, depart, arrivee, intermediaire)
        print(f"Déplacer un disque de {depart} vers {arrivee}.")
        solution_hanoi(n-1, intermediaire, depart, arrivee)

Le cas de base est celui où il n'y a aucun disque : on ne fait rien du tout.

Pour déplacer n disques de la tour depart vers la tour arrivee, on procède en trois temps :

  • on déplace récursivement n-1 disques de la tour depart vers la tour intermediaire,
  • on déplace un disque (le plus grand) de la tour depart vers la tour arrivee,
  • on déplace récursivement n-1 disques de la tour intermediaire vers la tour arrivee.

L'appel hanoi(3, 'GAUCHE', 'CENTRE', 'DROITE') entraîne les sept affichages suivants :

1
2
3
4
5
6
7
Déplacer un disque de GAUCHE vers DROITE.
Déplacer un disque de GAUCHE vers CENTRE.
Déplacer un disque de DROITE vers CENTRE.
Déplacer un disque de GAUCHE vers DROITE.
Déplacer un disque de CENTRE vers GAUCHE.
Déplacer un disque de CENTRE vers DROITE.
Déplacer un disque de GAUCHE vers DROITE.

Ce qu'il faut savoir et savoir faire⚓︎

  • Écrire une fonction récursive, en identifiant le(s) cas de base et le(s) cas récursif(s).
  • Dessiner un arbre d'appels récursifs.

Exercices et activités⚓︎

Exercices

Carnet Jupyter à travailler sur le site CAPYTALE ou à télécharger ici

Corrigé disponible ici

Carnet Jupyter à travailler sur le site CAPYTALE ou à télécharger ici

Corrigé disponible ici

Carnet Jupyter à travailler sur le site CAPYTALE ou à télécharger ici

Corrigé disponible ici

Carnet Jupyter à travailler sur le site CAPYTALE ou à télécharger ici

Corrigé disponible ici

Carnet Jupyter à travailler sur le site CAPYTALE ou à télécharger ici

Corrigé disponible ici

Activités

L'objectif de l'activité d'écrire des procédures récursives pour dessiner des figures géométriques avec le module turtle.

Cercles tangents

Carnet Jupyter à télécharger ici

Corrigé disponible ici

L'objectif de l'activité d'écrire des procédures récursives pour dessiner des figures fractales avec le module turtle.

Triangle de Sierpinski

Carnet Jupyter à télécharger ici

Corrigé disponible ici

L'objectif de l'activité est de créer un solveur du jeu Le compte est bon.

Le compte est bon !

Carnet Jupyter à travailler sur le site CAPYTALE ou à télécharger ici

Corrigé disponible ici



L'exposition d'estampes de M. C. Escher est une lithographie de 1956 qui représente un homme dans une gallerie en train de regarder le dessin d'un port à l'intérieur duquel on apperçoit la gallerie où l'homme se trouve.