La file de la cantine
Trois amis font la queue à la cantine. Ils peuvent se placer dans plusieurs ordres : Lina, Karim, Zoé, ou Karim, Lina, Zoé, et ainsi de suite.
Pour compter les ordres, un truc simple : choisis le premier, puis range les autres. C’est un problème plus petit. La récursivité est faite pour ça.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Récursivité | Une fonction qui s’appelle elle-même. Voir la leçon « Une fonction qui s’appelle ». | somme(liste[1:]) |
| Valeur rendue | La réponse donnée par return. | return 1 |
| Pile d’appels | Les appels commencés et pas finis, du plus ancien au plus récent. | somme([5, 3, 2]), somme([3, 2]) |
| Tranche | Un morceau de liste. liste[1:] garde tout sauf le premier élément. | [5, 3, 2][1:] donne [3, 2] |
| Liste vide | Une liste sans élément. Sa longueur est 0. | [] |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Rendre une valeur
Le compte à rebours affichait des lignes. Ici, la fonction rend un nombre.
La règle est la même : un cas de base, puis un appel récursif. Mais on utilise la réponse de l’appel pour fabriquer la nôtre.
Pour ranger 4 personnes : on en choisit une (4 choix), puis on range les 3 autres.
À toi : les files possibles
def nombre_de_files(n):
# De combien de façons peut-on ranger n personnes en file ?
if n == 0:
return 1
return n * nombre_de_files(n - 1)
print(nombre_de_files(3))
print(nombre_de_files(4))
print(nombre_de_files(5))
# Avec 6 amis dans la file du cinéma, combien de files possibles ?
Exemple travaillé : nombre_de_files(4)
| Étape | Appel | Ce qu’il rend |
|---|---|---|
| 1 (descente) | nombre_de_files(4) | attend 4 × nombre_de_files(3) |
| 2 (descente) | nombre_de_files(3) | attend 3 × nombre_de_files(2) |
| 3 (descente) | nombre_de_files(2) | attend 2 × nombre_de_files(1) |
| 4 (descente) | nombre_de_files(1) | attend 1 × nombre_de_files(0) |
| 5 (cas de base) | nombre_de_files(0) | 1 |
| 6 (remontée) | nombre_de_files(1) | 1 × 1 = 1 |
| 7 (remontée) | nombre_de_files(2) | 2 × 1 = 2 |
| 8 (remontée) | nombre_de_files(3) | 3 × 2 = 6 |
| 9 (remontée) | nombre_de_files(4) | 4 × 6 = 24 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Contrôle rapide
À toi de jouer
Contrôle rapide
3 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.
Additionner une liste
Comment additionner une liste avec la récursivité ? On prend le premier nombre. On l’ajoute à la somme du reste.
Le reste, c’est liste[1:], une liste plus courte d’un élément.
Le cas de base : une liste vide vaut 0.
À toi : la somme d’une liste
def somme(liste):
# Cas de base : une liste vide vaut 0.
if len(liste) == 0:
return 0
# liste[1:] veut dire : toute la liste sauf le premier.
return liste[0] + somme(liste[1:])
print(somme([5, 3, 2]))
print(somme([]))
print(somme([10, 20, 30, 40]))
# Essaie avec les prix de ton panier du marché.
À toi : voir la pile en marche
def somme(liste):
print("J'entre avec", liste)
if len(liste) == 0:
print(" cas de base, je rends 0")
return 0
reste = somme(liste[1:])
print(" je remonte :", liste[0], "+", reste)
return liste[0] + reste
print("Résultat :", somme([5, 3, 2]))