logo

← Chapitre précédent
Chapitre suivant →

Découvrir la Récursivité en Python

Objectifs Pédagogiques
  • Comprendre ce qu’est une fonction récursive.
  • Identifier le cas de base et le cas récursif.
  • Appliquer la récursivité à des problèmes classiques : factorielle, Fibonacci, somme, palindrome.
  • Comprendre les limites et les dangers d’une mauvaise récursion.

1. Qu’est-ce que la Récursivité ?

Définition
La récursivité est une technique où une fonction s’appelle elle-même pour résoudre un problème. Elle repose toujours sur :
  • Un cas de base qui arrête l’appel récursif.
  • Un cas récursif qui réduit le problème à une version plus simple.

2. Exemple classique : la Factorielle

Définition mathématique

La factorielle de n se note n! et est définie comme :

Implémentation Python

def factorielle(n):
    if n == 0:      # Cas de base
        return 1
    else:           # Cas récursif
        return n * factorielle(n - 1)

print(factorielle(5))  # Affiche 120
Exécution pas à pas
  • factorielle(5) → 5 * factorielle(4)
  • factorielle(4) → 4 * factorielle(3)
  • factorielle(3) → 3 * factorielle(2)
  • factorielle(2) → 2 * factorielle(1)
  • factorielle(1) → 1 * factorielle(0)
  • factorielle(0) → 1

3. La Suite de Fibonacci

Définition

Code Python

def fibonacci(n):
    if n <= 1:      # Cas de base
        return n
    else:           # Cas récursif
        return fibonacci(n - 1) + fibonacci(n - 2)

Exemple pour fibonacci(4)

fibonacci(4)
→ fibonacci(3) + fibonacci(2)
→ (fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))
→ (1 + 1) + (1 + 0) = 3

4. Limites de la Récursivité

À retenir
  • Appels infinis : si le cas de base est mal défini, la fonction s'appelle sans fin → RecursionError.
  • Performance : les appels imbriqués consomment beaucoup de mémoire (pile).

5. Exercices Pratiques

Exercices
Exercice 1 : Somme des N premiers nombres

Créer une fonction somme(n) qui retourne la somme de 1 à n.

def somme(n):
    if n == 0:
        return 0
    else:
        return n + somme(n - 1)

print(somme(5))  # 15
Exercice 2 : Compter à rebours

Créer une fonction compter(n) qui affiche tous les nombres de n à 0.

def compter(n):
    if n < 0:
        return
    print(n)
    compter(n - 1)

compter(5)
Exercice 3 : Puissance sans `**`

Créer une fonction puissance(x, n) qui retourne x puissance n.

def puissance(x, n):
    if n == 0:
        return 1
    else:
        return x * puissance(x, n - 1)

print(puissance(2, 3))  # 8
Exercice 4 : Mot Palindrome

Créer une fonction récursive est_palindrome(mot).

def est_palindrome(mot):
    if len(mot) <= 1:
        return True
    if mot[0] != mot[-1]:
        return False
    return est_palindrome(mot[1:-1])

print(est_palindrome("radar"))  # True
print(est_palindrome("python"))  # False

6. Résumé des Notions

Élément Rôle
Cas de base Condition d'arrêt de la récursion
Cas récursif Appel de la fonction à elle-même avec n - 1
return Permet de remonter les résultats des appels
Récursion Alternative aux boucles pour certains problèmes