𝔼𝕩𝕖𝕣𝕔𝕚𝕔𝕖𝕤 𝕤𝕦𝕣 𝕝𝕒 𝕣𝕖́𝕔𝕦𝕣𝕤𝕚𝕧𝕚𝕥𝕖́ 𝕖𝕟 ℙ𝕪𝕥𝕙𝕠𝕟

Exercice 1 : Factorielle

Écrivez une fonction récursive en Python pour calculer la factorielle d'un nombre \(n\).

def factorielle(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorielle(n - 1)

Testez la fonction avec \(n = 5\) :

resultat = factorielle(5)
print("Factorielle de 5 :", resultat)

Exercice 2 : Somme des éléments d'une liste

Écrivez une fonction récursive en Python pour calculer la somme des éléments d'une liste.

def somme_liste(liste):
    if not liste:
        return 0
    else:
        return liste[0] + somme_liste(liste[1:])

Testez la fonction avec la liste [1, 2, 3, 4, 5] :

resultat = somme_liste([1, 2, 3, 4, 5])
print("Somme des éléments de la liste :", resultat)

Exercice 3 : Calcul de la puissance

Écrivez une fonction récursive en Python pour calculer \(a^n\), où \(a\) est la base et \(n\) est l'exposant.

def puissance(base, exposant):
    if exposant == 0:
        return 1
    else:
        return base * puissance(base, exposant - 1)

Testez la fonction avec \(a = 2\) et \(n = 3\) :

resultat = puissance(2, 3)
print("2^3 :", resultat)

Exercice 4 : Fibonacci

Écrivez une fonction récursive en Python pour calculer le \(n\)-ième terme de la suite de Fibonacci. La suite de Fibonacci commence par 0 et 1, et chaque terme suivant est la somme des deux précédents.

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

Testez la fonction avec \(n = 6\) :

resultat = fibonacci(6)
print("Fibonacci(6) :", resultat)

Exercice 5 : Calcul de la combinaison

Écrivez une fonction récursive en Python pour calculer le coefficient binomial, également appelé combinaison. La combinaison de \(n\) éléments pris \(k\) à la fois est donnée par \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\).

def combinaison(n, k):
    if k == 0 or k == n:
        return 1
    else:
        return combinaison(n - 1, k - 1) + combinaison(n - 1, k)

Testez la fonction avec \(n = 5\) et \(k = 2\) :

resultat = combinaison(5, 2)
print("Combinaison(5, 2) :", resultat)

Exercice 6 : Recherche d'un élément dans un arbre binaire

Écrivez une fonction récursive en Python pour rechercher la présence d'un élément dans un arbre binaire. Utilisez une structure de données représentant un nœud d'arbre binaire :

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

def recherche_arbre_binaire(arbre, element):
    if arbre is None:
        return False
    if arbre.valeur == element:
        return True
    return recherche_arbre_binaire(arbre.gauche, element) or recherche_arbre_binaire(arbre.droite, element)

Créez un arbre binaire et testez la fonction avec un élément existant et un élément inexistant.

Exercice 7 : Tri Récursif

Écrivez une fonction de tri récursif en Python. Vous pouvez choisir parmi des algorithmes tels que le tri fusion ou le tri rapide. Appliquez le tri à une liste non triée :

def tri_rapide(liste):
    if len(liste) <= 1:
        return liste
    pivot = liste[len(liste) // 2]
    inferieur = [x for x in liste if x < pivot]
    egal = [x for x in liste if x == pivot]
    superieur = [x for x in liste if x > pivot]
    return tri_rapide(inferieur) + egal + tri_rapide(superieur)

Testez la fonction avec une liste non triée :

liste_non_triee = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
liste_triee = tri_rapide(liste_non_triee)
print("Liste triée :", liste_triee)

Ces exercices plus avancés vous permettront de renforcer vos compétences en résolution de problèmes récursifs en Python.

Exercice 8 : Inversion d'une Chaîne

Écrivez une fonction récursive en Python qui inverse une chaîne de caractères. La fonction prend une chaîne en entrée et retourne la chaîne inversée :

def inverser_chaine(chaine):
    if len(chaine) == 0:
        return ""
    return chaine[-1] + inverser_chaine(chaine[:-1])

Testez la fonction avec une chaîne :

chaine = "Python"
chaine_inversee = inverser_chaine(chaine)
print("Chaîne inversée :", chaine_inversee)

Exercice 9 : Compte des Voyelles

Écrivez une fonction récursive en Python qui compte le nombre de voyelles dans une chaîne de caractères. La fonction retourne le nombre de voyelles :

def compter_voyelles(chaine):
    if len(chaine) == 0:
        return 0
    if chaine[0] in "aeiouAEIOU":
        return 1 + compter_voyelles(chaine[1:])
    return compter_voyelles(chaine[1:])

Testez la fonction avec une chaîne :

chaine = "Hello, World!"
nombre_voyelles = compter_voyelles(chaine)
print("Nombre de voyelles :", nombre_voyelles)

Exercice 10 : Produit des Éléments d'une Liste

Écrivez une fonction récursive en Python qui calcule le produit des éléments d'une liste. La fonction retourne le produit :

def produit_liste(liste):
    if len(liste) == 0:
        return 1
    return liste[0] * produit_liste(liste[1:])

Testez la fonction avec une liste :

liste = [1, 2, 3, 4]
produit = produit_liste(liste)
print("Produit des éléments :", produit)