Accueil › Python › Un panier trop profond pour la récursion
Un panier trop profond pour la récursion
Exercice de la série « Deux pointeurs, comptage, piles et récursivité »avance
Le besoin. Les paniers peuvent contenir des sous-paniers (un coffret cadeau, qui contient lui-même des coffrets). On veut le total, quelle que soit la profondeur — y compris celle, absurde mais réelle, qu'un import automatique a produite.
Ce qu'on vous demande. Écrivez total_panier(panier) qui renvoie la
somme en centimes. Un panier est
{'prix_cents': 250} # un article
{'contenu': [<panier>, <panier>, ...]} # un sous-panier
Un panier sans prix_cents ni contenu vaut 0.
Le banc d'essai construit le panier, et son paramètre profondeur, quand
il est non nul, fabrique une chaîne de cette profondeur contenant un
article de 1 centime tout au fond. Il renvoie le total, ou le nom de
l'erreur levée.
| Appel | Résultat attendu |
|---|---|
{'contenu': [{'prix_cents': 250}, {'prix_cents': 400}]} |
650 |
{} |
0 |
| chaîne de profondeur 400 | 1 |
Le piège. CPython limite la profondeur d'appel : 1 000 par
défaut sur un poste de travail. Le banc d'essai abaisse volontairement
cette limite à 120, parce que la pile du Python compilé pour le
navigateur est bien plus étroite que celle d'un CPython de bureau — le
phénomène est exactement le même, à une échelle qui tient dans un onglet.
Une récursion élégante lève donc RecursionError sur la chaîne profonde,
et il faut s'en passer.
Cas de test
[{"contenu":[{"prix_cents":250},{"prix_cents":400}]}][{}][{"prix_cents":599}][{"contenu":[]}][{"contenu":[{"contenu":[{"prix_cents":100},{"prix_cents":200}]},{"prix_cents":50}]}][{"contenu":[{"prix_cents":-500},{"prix_cents":700}]}]
Votre code s'exécute réellement dans le navigateur, et la correction compare son résultat à celui d'une solution de référence.