Les poupées russes
Tu ouvres une poupée russe. Dedans, il y a une poupée plus petite. Tu l’ouvres aussi. Et ainsi de suite.
Tu t’arrêtes quand la poupée est toute petite et qu’elle ne s’ouvre plus.
Une fonction peut faire pareil : se rappeler elle-même avec un problème plus petit, jusqu’à un problème tout simple.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Récursivité | Une fonction qui s’appelle elle-même. | compte_a_rebours(n - 1) |
| Cas de base | Le cas si simple que la fonction répond sans s’appeler. Il arrête tout. | if n == 0: |
| Appel récursif | La ligne où la fonction s’appelle elle-même, avec un problème plus petit. | compte_a_rebours(n - 1) |
| Pile d’appels | La liste des appels commencés et pas encore finis. Le dernier appelé finit le premier. | rebours(3), rebours(2), rebours(1) |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Deux règles
Une fonction récursive suit toujours deux règles.
- Le cas de base : si le problème est tout petit, elle répond tout de suite.
- L’appel récursif : sinon, elle s’appelle avec un problème plus petit.
Sans cas de base, elle ne s’arrête jamais.
À toi : le compte à rebours
def compte_a_rebours(n):
# Cas de base : on s'arrête à zéro.
if n == 0:
print("Partez !")
else:
print(n)
compte_a_rebours(n - 1)
compte_a_rebours(3)
# Change 3 en 5. Combien de lignes sont écrites ?
Exemple travaillé : la pile pour n = 3
| Appel | Valeur de n | Ce qu’il affiche | Ce qu’il fait ensuite |
|---|---|---|---|
| compte_a_rebours(3) | 3 | 3 | appelle compte_a_rebours(2) |
| compte_a_rebours(2) | 2 | 2 | appelle compte_a_rebours(1) |
| compte_a_rebours(1) | 1 | 1 | appelle compte_a_rebours(0) |
| compte_a_rebours(0) | 0 | Partez ! | rien : c’est le cas de base |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Contrôle rapide
À toi de jouer
Contrôle rapide
4 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.
Avant ou après l’appel
Le travail peut se faire avant l’appel récursif, comme dans le compte à rebours.
Il peut aussi se faire après. Alors la fonction descend d’abord jusqu’au cas de base. Puis elle remonte et fait son travail à chaque étage.
L’ordre des lignes change complètement.
À toi : le travail après l’appel
def compte_croissant(n):
if n == 0:
print("Départ !")
else:
compte_croissant(n - 1)
print(n)
compte_croissant(3)
# Devine d'abord l'ordre des lignes. Puis lance le programme.
# La ligne print(n) est maintenant APRÈS l'appel récursif.