Pile bornée — estimer avant d'exécuter

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 6 — Fonctions récursives

Énoncé

Pour les fonctions somme_jusqua(n), dichotomie_rec, puissance(x, n), fib(n) (naïve), sous_listes(t) et koch(L, n), indiquer la profondeur maximale de pile d'appels et identifier les risques de débordement en Python (limite de 1000).

Corrigé

somme_jusqua(n) : profondeur $O (n)$ . Risque de crash élevé dès $n \geq 1000$ . Parade : passage à une boucle itérative.
dichotomie_rec : profondeur $O (lo g n)$ . Aucun risque de débordement ( $30$ appels pour $1 0^{9}$ éléments).
puissance(x, n) : profondeur $O (lo g n)$ . Aucun risque.
fib(n) : profondeur $O (n)$ en théorie, mais l'explosion du nombre d'appels ( $O (1.61 8^{n})$ ) bloque le temps d'exécution bien avant d'atteindre la limite de pile. Parade : écriture itérative.
sous_listes(t) : profondeur $O (n)$ , mais la mémoire requise pour stocker les $2^{n}$ listes sature le système dès $n \approx 25$ , rendant la profondeur de pile secondaire.
koch(L, n) : profondeur $O (n)$ . Aucun danger en pratique car le nombre de segments dessinés ( $4^{n}$ ) limite $n$ à des valeurs très faibles (souvent $n \leq 5$ ).

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.