🔄 Fiche d'exercices – Récursivité

🎯 Objectif

Maîtriser la programmation récursive en implémentant des fonctions qui s'appellent elles-mêmes pour résoudre des problèmes.

💡 Rappel pour tous les exercices

Définir le cas terminal (ou cas de base) qui arrête la récursion
Définir le cas général (comment le problème se réduit à un sous-problème plus simple)
Implémenter la fonction récursive qui s'appelle elle-même

Base 🦊

Exercice 1 – Factorielle

1. Définir le cas terminal pour la factorielle.
2. Écrire une fonction factorielle(n) récursive.
3. Tester avec n = 5 et n = 0.
Indice : le cas terminal est 0! = 1.

# Cas terminal : 0! = 1
# Cas récursif : n! = n × (n-1)!

def factorielle(n: int) -> int:
    if n == 0:
        return 1
    return n * factorielle(n - 1)

Base 🦊

Exercice 2 – Suite de Fibonacci

1. Définir les cas terminaux de la suite de Fibonacci.
2. Écrire une fonction fibonacci(n) récursive.
3. Tester avec n = 6 et n = 0.
Indice : les cas terminaux sont F(0) = 0 et F(1) = 1.

# Cas terminaux : F(0) = 0, F(1) = 1
# Cas récursif : F(n) = F(n-1) + F(n-2)

def fibonacci(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

Base 🦊

Exercice 3 – Somme des chiffres

1. Définir le cas terminal pour la somme des chiffres d'un entier.
2. Écrire une fonction somme_chiffres(n) récursive.
3. Tester avec n = 245 et n = 1001.
Indice : le cas terminal est n = 0.

# Cas terminal : n = 0
# Cas récursif : somme_chiffres(n) = (n % 10) + somme_chiffres(n // 10)

def somme_chiffres(n: int) -> int:
    if n == 0:
        return 0
    return (n % 10) + somme_chiffres(n // 10)

Facile 🌟

Exercice 4 – Puissance d'un nombre

1. Définir le cas terminal pour a^b.
2. Écrire une fonction puissance(a, b) récursive.
3. Tester avec a = 2, b = 5 et a = 3, b = 0.
Indice : le cas terminal est b = 0 car a^0 = 1.

# Cas terminal : exposant = 0, a^0 = 1
# Cas récursif : a^n = a × a^(n-1)

def puissance(a: int, n: int) -> int:
    if n == 0:
        return 1
    return a * puissance(a, n - 1)

Facile 🌟

Exercice 5 – Inversion de chaîne

1. Définir le cas terminal pour inverser une chaîne de caractères.
2. Écrire une fonction inverse_chaine(s) récursive.
3. Tester avec s = "NSI" et s = "informatique".
Indice : le cas terminal est une chaîne vide ou d'un caractère.

# Cas terminal : chaîne vide ou un seul caractère
# Cas récursif : inverse_chaine(s) = s[-1] + inverse_chaine(s[:-1])

def inverse_chaine(s: str) -> str:
    if len(s) <= 1:
        return s
    return s[-1] + inverse_chaine(s[:-1])

Intermédiaire 🔥

Exercice 6 – Liste chaînée (POO)

1. Créer une classe Noeud avec valeur et suivant.
2. Définir le cas terminal pour calculer la longueur d'une liste chaînée.
3. Écrire longueur_liste(noeud) récursive : longueur d'un noeud = 1 + longueur du suivant.
4. Créer une liste de 4 noeuds et tester.
Indice : le cas terminal est un noeud None.

# Cas terminal : noeud est None (liste vide)
# Cas récursif : longueur = 1 + longueur du reste de la liste

class Noeud:
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant

def longueur_liste(noeud: Noeud) -> int:
    if noeud is None:
        return 0
    return 1 + longueur_liste(noeud.suivant)

Intermédiaire 🔥

Exercice 7 – Recherche dans une liste

1. Définir le cas terminal pour la recherche d'une valeur.
2. Écrire recherche(liste, valeur) récursive.
3. Tester avec liste = [2, 5, 8, 10] et valeur = 5.
Indice : le cas terminal est une liste vide.

# Cas terminal : liste vide (élément non trouvé) ou élément trouvé
# Cas récursif : chercher dans le reste de la liste

def recherche(liste: list, element) -> bool:
    if len(liste) == 0:
        return False
    if liste[0] == element:
        return True
    return recherche(liste[1:], element)

Intermédiaire 🔥

Exercice 8 – Somme des éléments d'une liste

1. Définir le cas terminal pour la somme d'une liste.
2. Écrire somme_liste(liste) récursive.
3. Tester avec liste = [1, 2, 3, 4, 5].
Indice : le cas terminal est une liste vide.

# Cas terminal : liste vide
# Cas récursif : somme = premier élément + somme du reste

def somme_liste(liste: list) -> int:
    if len(liste) == 0:
        return 0
    return liste[0] + somme_liste(liste[1:])

Avancé 🚀

Exercice 9 – Palindrome

1. Définir le cas terminal pour vérifier si une chaîne est un palindrome.
2. Écrire est_palindrome(s) récursive.
3. Tester avec s = "radar" et s = "NSI".
Indice : le cas terminal est une chaîne vide ou à un caractère.

# Cas terminal : chaîne vide ou un seul caractère
# Cas récursif : premier = dernier ET le milieu est un palindrome

def est_palindrome(s: str) -> bool:
    if len(s) <= 1:
        return True
    if s[0] == s[-1]:
        return est_palindrome(s[1:-1])
    else:
        return False

Bonus 🦊

Exercice 10 – Dessin de motifs (bonus)

1. Définir le cas terminal pour le dessin d'un triangle.
2. Écrire triangle(n) récursive.
3. Tester avec n = 5.
Indice : le cas terminal est n = 0.

# Cas terminal : n = 0
# Cas récursif : afficher n étoiles puis appel récursif avec n-1

def triangle(n: int) -> None:
    if n == 0:
        return
    print('*' * n)
    triangle(n - 1)