AcademyGilbak LogoAcademyGilbak

NSI · Terminale

Algorithmes classiques : factorielle et suite de Fibonacci

Étude détaillée de la factorielle (récursion simple, trace de pile) et de la suite de Fibonacci (double récursion, complexité et arbre d'appels).

Algorithmes Classiques : Factorielle & Fibonacci

Dans ce chapitre, nous explorons deux algorithmes récursifs fondamentaux au programme de Terminale NSI : le calcul de la factorielle et la suite de Fibonacci.

1. Étude Détaillée : Le Calcul de la Factorielle (n!)

En mathématiques, la factorielle d'un entier naturel n (notée n!) est le produit de tous les entiers strictement positifs inférieurs ou égaux à n :

n! = n × (n - 1) × (n - 2) × … × 1 et par définition 0! = 1

Exemples :

  • 3! = 3 × 2 × 1 = 6
  • 4! = 4 × 3 × 2 × 1 = 24
  • 5! = 5 × 4 × 3 × 2 × 1 = 120

On observe la relation de récurrence naturelle :

n! = n × (n - 1)! (pour tout n > 0)

Activité

Activité — Fonction Factorielle Récursive

Python
1
2
3
4
5
6
7
8
def fact(n: int) -> int:
"""Calcule n! de manière récursive."""
if n == 0:
return 1 # Cas de base : 0! = 1
else:
return n * fact(n - 1) # Cas récursif
print(fact(4)) # 24

Déroulement pas à pas de l'appel fact(4) :

  1. fact(4) appelle 4 * fact(3) (empilement)
  2. fact(3) appelle 3 * fact(2) (empilement)
  3. fact(2) appelle 2 * fact(1) (empilement)
  4. fact(1) appelle 1 * fact(0) (empilement)
  5. fact(0) atteint le cas de base et renvoie 1 (dépilement)
  6. fact(1) reçoit 1 → renvoie 1 * 1 = 1 (dépilement)
  7. fact(2) reçoit 1 → renvoie 2 * 1 = 2 (dépilement)
  8. fact(3) reçoit 2 → renvoie 3 * 2 = 6 (dépilement)
  9. fact(4) reçoit 6 → renvoie 4 * 6 = 24 (résultat final)

2. La Suite de Fibonacci : Récursion Double

La célèbre suite de Fibonacci modélise une croissance où chaque terme est la somme des deux précédents :

u₀ = 0, u₁ = 1

uₙ = uₙ₋₁ + uₙ₋₂ (pour tout n ≥ 2)

Les premiers termes sont :

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

Activité

Activité — Implémentation de la suite de Fibonacci

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Version Récursive (Double récursion)
def fibonacci(n: int) -> int:
"""Retourne le n-ième terme de la suite de Fibonacci."""
if n == 0:
return 0 # 1er cas de base
elif n == 1:
return 1 # 2nd cas de base
else:
return fibonacci(n - 1) + fibonacci(n - 2) # Deux appels récursifs
# Version Itérative (Efficace en O(n))
def fibonacci_iteratif(n: int) -> int:
if n == 0:
return 0
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
print([fibonacci(i) for i in range(8)]) # [0, 1, 1, 2, 3, 5, 8, 13]

Arbre d'appels pour fibonacci(4) :

Remarquez que la récursion arborescente effectue plusieurs fois les mêmes calculs (par exemple fib(2) est calculé 2 fois) :

Python
1
2
3
4
5
6
7
fib(4)
/ \
fib(3) fib(2)
/ \ / \
fib(2) fib(1) fib(1) fib(0)
/ \
fib(1) fib(0)
À retenir / Remarque

Visualiser l'arbre de Fibonacci sur le simulateur

Observez l'arbre d'appels complet et testez différentes valeurs de n : Simuler la suite de Fibonacci dans le Simulateur→

Avez-vous compris et assimilé ce cours ?

+50 XP

Étudiez le contenu activement pendant au moins 45 secondes pour pouvoir débloquer la validation au mérite.

Temps d'étude actif :0s / 45s
Chapitre précédentLa pile d'exécution (Call Stack) et mécanisme interneChapitre suivantTerminaison et synthèse de la récursivité