%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Récursivité/Récursivité|Accueil · Récursivité]]
%% nav-fin %%
# Exercices - Récursivité
Ces exercices s'appuient sur le [[Code et Développement/Programmation/Récursivité/01_Cours Récursivité|cours de récursivité]]. Chaque fonction demandée doit s'appeler elle-même et avoir une condition d'arrêt.
Les cellules Python de cette page s'exécutent dans le navigateur. Le premier clic sur « Exécuter » charge Python, ce qui prend quelques secondes. Les tests vérifient votre fonction après chaque exécution. La correction est cachée sous chaque exercice.
## Exercice 1 : somme des entiers de 1 à n
Écrivez une fonction récursive `somme(n)` qui renvoie la somme des entiers de 1 à `n`.
La condition d'arrêt porte sur `n == 0` : la somme vaut alors 0. Sinon, `somme(n)` vaut `n + somme(n - 1)`.
```sq-python
def somme(n):
pass # à compléter
print(somme(5))
#--- correction
def somme(n):
if n == 0:
return 0
return n + somme(n - 1)
print(somme(5))
#--- tests
assert somme(0) == 0, "somme(0) doit valoir 0."
assert somme(5) == 15, "somme(5) doit valoir 1 + 2 + 3 + 4 + 5 = 15."
assert somme(100) == 5050, "somme(100) doit valoir 5050."
#--- sortie
15
```
## Exercice 2 : puissance
Écrivez une fonction récursive `puissance(x, n)` qui renvoie `x` à la puissance `n`, pour un entier `n` positif ou nul.
La condition d'arrêt porte sur `n == 0` : le résultat vaut alors 1. Sinon, `puissance(x, n)` vaut `x * puissance(x, n - 1)`.
```sq-python
def puissance(x, n):
pass # à compléter
print(puissance(2, 10))
#--- correction
def puissance(x, n):
if n == 0:
return 1
return x * puissance(x, n - 1)
print(puissance(2, 10))
#--- tests
assert puissance(5, 0) == 1, "Tout nombre à la puissance 0 vaut 1."
assert puissance(3, 3) == 27, "puissance(3, 3) doit valoir 27."
assert puissance(2, 10) == 1024, "puissance(2, 10) doit valoir 1024."
#--- sortie
1024
```
## Exercice 3 : suite de Fibonacci
Écrivez une fonction récursive `fibonacci(n)` qui renvoie le terme de rang `n` de la suite de Fibonacci. La suite est définie par F(0) = 0, F(1) = 1 et F(n) = F(n − 1) + F(n − 2) pour n ≥ 2.
Cette fonction a deux cas de base et deux appels récursifs.
```sq-python
def fibonacci(n):
pass # à compléter
print([fibonacci(i) for i in range(12)])
#--- correction
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print([fibonacci(i) for i in range(12)])
#--- tests
assert fibonacci(0) == 0, "fibonacci(0) doit valoir 0."
assert fibonacci(1) == 1, "fibonacci(1) doit valoir 1."
assert fibonacci(10) == 55, "fibonacci(10) doit valoir 55."
#--- sortie
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
```
Exécutez ensuite `fibonacci(30)` et notez la durée affichée. Ce calcul effectue 2 692 537 appels : chaque appel en déclenche deux autres, et les mêmes termes sont recalculés de nombreuses fois. L'arbre d'appels du cours montre ce phénomène pour n = 5. Essayez ensuite `fibonacci(32)` : la durée est multipliée par environ 2,6.
```sq-python
import time
debut = time.perf_counter()
print(fibonacci(30))
print(round(time.perf_counter() - debut, 1), "secondes")
```
%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Récursivité/Récursivité|Accueil · Récursivité]]
%% nav-fin %%
---
🗓️ Historique
Dernière mise à jour : `08 novembre 2026`
Rédigé par : [[Julien DUQUENNOY]]