Suite de Fibonacci

Récursivité et mémoïsation

Exercice Intermédiaire · Algorithmique · prepa scientifique et economique (CPGE)

Enonce

Implémenter trois versions : récursif naïf, mémoïsation, itératif.

⚠ Bonus : Comparer les temps pour $n=30$.

Signature attendue

def fib_recursif(n: int) -> int:
def fib_memo(n: int, memo=None) -> int:
def fib_iteratif(n: int) -> int:

Exemples

fib_recursif(10) → 55
fib_memo(30) → 832040
fib_iteratif(30) → 832040

📖 Rappel de cours

$F_0=0,\quad F_1=1,\quad F_n=F_{n-1}+F_{n-2}$

Naïve : $O(\varphi^n)$. Mémoïsation / itératif : $O(n)$.

⚠ Le piège : La version naïve recalcule F(n-2) deux fois, F(n-3) trois fois, et ainsi de suite — d'où le coût exponentiel. Mémoïser revient à ne calculer chaque terme qu'une fois. En itératif, deux variables suffisent : garder tout le tableau ne sert à rien si l'on ne veut que F(n).

← Exercices d'algorithmique en Python — tris, dichotomie, récursivité

Exercices du meme theme

La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.