AcademyGilbak LogoAcademyGilbak

NSI · Terminale

À la découverte de la récursivité : principes et premiers exemples

Comprendre le concept fondamental de la récursivité : analogie de la mise en abyme, constructions géométriques avec Turtle, cas de base, cas récursif, somme et puissances.

À la découverte de la récursivité

Mise en abyme : Jerry peignant Jerry peignant Jerry...Mise en abyme : Jerry peignant Jerry peignant Jerry...

1. Rappels & Découverte par le Dessin (Module Turtle)

En programmation, avant d'aborder formellement la récursivité, observons comment une structure répétitive peut être construite pas à pas. Le module turtle de Python permet de tracer facilement des formes géométriques à l'écran.

On donne ci-dessous un exemple de programme permettant de tracer un carré de côté 100 pixels :

Python
1
2
3
4
5
6
7
8
9
10
11
import turtle
t = turtle.Turtle()
t.speed(3)
# Tracé d'un carré de 100 pixels
for _ in range(4):
t.forward(100)
t.left(90)
turtle.done()
Activité

Activité d'observation

  1. Essayez de prévoir le résultat de l'exécution du programme ci-dessus.
  2. Vérifiez votre hypothèse en exécutant le script dans un environnement Python.
Exercice

Exercice 1 — Formes géométriques de base

  1. Écrire un programme Python qui trace un carré de côté 100 pixels en utilisant les instructions forward et left.
  2. Écrire un programme qui trace un triangle équilatéral de côté 100 pixels (angle de rotation de 120°).
  3. Écrire un programme qui trace un hexagone régulier de côté 100 pixels (angle de rotation de 60°).
Exercice

Exercice 2 — Cercles & Spirales

  1. Dans la console interactive Python, exécutez help(turtle.circle) pour consulter la documentation de l'instruction de tracé de cercle.
  2. Écrire un programme Python permettant de tracer une spirale de carrés respectant le cahier des charges suivant :
  • Le côté du grand carré initial mesure 200 pixels.
  • Le coin inférieur gauche des carrés est l'origine du repère (0, 0).
  • À chaque étape, les carrés tournent de 20° dans le sens direct (left(20)).
  • À chaque étape, le côté du carré diminue de 10% de sa longueur (cote = cote * 0.9).
  • On interrompt la construction lorsque la taille devient inférieure ou égale à 10 pixels.

Spirale de carrés avec TurtleSpirale de carrés avec Turtle

À retenir / Remarque

Pour réaliser le dessin de la spirale ci-dessus, vous avez utilisé une boucle while ou for : votre programme est dit itératif.

Remarquons à présent que cette spirale peut se décomposer en un premier carré, suivi d'une spirale de carrés plus petits. C'est exactement l'essence de la pensée récursive !

2. Définition : Qu'est-ce que la Récursivité ?

Définition

Notion de fonction récursive

La récursivité est un concept fondamental de l'informatique et de l'algorithmique qui désigne la propriété d'une fonction (ou d'une structure) à s'appeler elle-même pour résoudre une version simplifiée ou réduite d'un même problème.

En d'autres termes, une fonction récursive s'auto-appelle de manière répétée jusqu'à ce qu'une condition d'arrêt (le cas de base) soit atteinte pour mettre fin aux appels.

Toute fonction récursive bien conçue est obligatoirement composée de deux parties essentielles :

  1. Le Cas de Base (ou Condition d'Arrêt) : C'est la condition où le problème est si simple qu'il peut être résolu immédiatement sans aucun nouvel appel récursif. Dès que le cas de base est atteint, la cascade d'appels s'arrête et les valeurs commencent à remonter.
  2. Le Cas Récursif (ou Étape de Récursion) : C'est la branche de code où la fonction s'appelle elle-même avec un argument strictement plus proche du cas de base (par exemple n - 1, a + 1, ou une sous-partie de liste/arbre).

Fonctionnement d'une fonction récursive : descente des appels et remontée des résultatsFonctionnement d'une fonction récursive : descente des appels et remontée des résultats

3. Premier Exemple : Somme des entiers entre a et b

On suppose que a ≤ b et on souhaite définir une fonction somme(a, b) qui calcule la somme de tous les entiers consécutifs compris entre a et b inclus :

S = a + (a + 1) + (a + 2) + … + b

Approche 1 : Version itérative (Boucle for)

Python
1
2
3
4
5
6
7
8
def somme_iterative(a: int, b: int) -> int:
"""Calcule la somme des entiers de a à b de manière itérative."""
total = 0
for x in range(a, b + 1):
total += x
return total
print(somme_iterative(3, 6)) # 3 + 4 + 5 + 6 = 18

Approche 2 : Version récursive

Constatons qu'il y a deux cas à envisager :

  • Si a = b (Cas de base) : Il n'y a qu'un seul nombre à additionner : a. On renvoie donc directement a.
  • Si a < b (Cas récursif) : La somme globale est égale à a plus la somme des entiers compris entre a + 1 et b. On écrit donc : a + somme(a + 1, b).
Python
1
2
3
4
5
6
7
8
def somme_recursive(a: int, b: int) -> int:
"""Calcule la somme des entiers de a à b de manière récursive."""
if a == b:
return a # Cas de base
else:
return a + somme_recursive(a + 1, b) # Cas récursif
print(somme_recursive(3, 6)) # Affiche 18

4. Les Puissances Entières Positives

En mathématiques, pour tout nombre a et pour tout entier naturel n ≥ 0, la puissance aⁿ est définie par :

aⁿ = a × a × … × a (avec n facteurs a) et conventionnellement a⁰ = 1

On peut remarquer la relation de récurrence immédiate :

aⁿ = a × aⁿ⁻¹ (pour tout n > 0)

Comparaison des implémentations Python

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Version Itérative
def puissance_iterative(a: float, n: int) -> float:
resultat = 1
for _ in range(n):
resultat *= a
return resultat
# Version Récursive
def puissance_recursive(a: float, n: int) -> float:
if n == 0:
return 1 # Cas de base : a^0 = 1
else:
return a * puissance_recursive(a, n - 1) # Cas récursif : a^n = a * a^(n-1)
print(puissance_recursive(2, 3)) # 2^3 = 8

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 suivantLa pile d'exécution (Call Stack) et mécanisme interne