Formations — 1 037 leçons en français

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

Écrire le code et le faire exécuter →

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.

La leçon qui prépare cet exercice

Les autres exercices de « Deux pointeurs, comptage, piles et récursivité »