informatique (tronc commun des prépas scientifiques) · Chapitre 6 · Exercice de TD
Convertir une récursion en boucle
Fonctions récursives · niveau 2
Énoncé
Proposer une version récursive de nb_chiffres(n) (calcul du nombre de chiffres d'un entier ), puis, à l'inverse, convertir la fonction récursive somme_chiffres(n) (somme des chiffres de ) en version itérative à l'aide d'une boucle.
Corrigé
def nb_chiffres(n: int) -> int:
if n < 10:
return 1
return 1 + nb_chiffres(n // 10)
def somme_chiffres(n: int) -> int:
s = 0
temp = n
while temp > 0:
s += temp % 10
temp //= 10
return s if n > 0 else 0Ces fonctions ne font qu'un seul appel récursif par niveau (récursion linéaire, mais non terminale : l'addition se fait au retour de l'appel). La conversion en boucle est triviale et élimine tout risque de débordement de pile (RecursionError), ce qui s'avère indispensable en présence de très grandes valeurs de .
Exercices semblables
- Fibonacci, ou l'arbre qui explose corrigé
- Le tracé de Sierpinski corrigé
- Les sous-listes d'une somme donnée corrigé
- Les tours de Hanoï corrigé
- Générer dans l'ordre du code de Gray corrigé