Exercices corrigés sur la récursivité
La récursivité est une technique fondamentale en programmation où une fonction s'appelle elle-même pour résoudre un problème en le décomposant en sous-problèmes plus petits. Cette section présente une série d'exercices corrigés pour maîtriser ce concept.
Longueur d'une chaîne
Soit une chaîne de caractères, écrire un algorithme récursif permettant de déterminer sa longueur.
La longueur d'une chaîne vide est 0. Sinon, la longueur est 1 + la longueur de la chaîne privée de son premier caractère.
def longueur(ch):
"""
Calcule récursivement la longueur d'une chaîne
"""
if not ch: # cas de base : chaîne vide
return 0
else:
return 1 + longueur(ch[1:])
ch = "Take It Easy"
print(f"La longueur de '{ch}' est : {longueur(ch)}")La longueur de 'Take It Easy' est : 12
Somme des éléments d'une liste
Rendre récursive la fonction somme suivante :
def somme(L):
s = 0
for val in L:
s += val
return sLa somme d'une liste vide est 0. Sinon, la somme est le premier élément + la somme du reste de la liste.
def somme(L):
"""
Calcule récursivement la somme des éléments d'une liste
"""
if not L: # cas de base : liste vide
return 0
return L[0] + somme(L[1:])
L = [1, 2, 3, 4, 5]
print(f"La somme de {L} est : {somme(L)}")La somme de [1, 2, 3, 4, 5] est : 15
Conversion en binaire
Pour convertir un nombre entier positif N de la base décimale à la base binaire, il faut opérer par des divisions successives du nombre N par 2. Les restes des divisions constituent la représentation binaire.
Ecrire une fonction récursive « Binaire » permettant d'imprimer à l'écran la représentation binaire d'un nombre N.
def binaire(N):
"""
Retourne la représentation binaire d'un nombre sous forme de liste
"""
if N == 0:
return []
return binaire(N // 2) + [N % 2]
def afficher_binaire(N):
"""Affiche la représentation binaire d'un nombre"""
bits = binaire(N)
if not bits:
print(0)
else:
print(''.join(str(bit) for bit in bits))
n = 13
print(f"Binaire de {n} : ", end="")
afficher_binaire(n)Binaire de 13 : 1101
Suite de Fibonacci
La suite de Fibonacci est définie comme suit :
$$ F_n = \begin{cases} 1 & n \le 2 \\ F_{n-1} + F_{n-2} & \text{sinon} \end{cases} $$
Ecrire un programme récursif calculant Fib(n).
def Fib(n):
"""
Calcule le n-ième terme de la suite de Fibonacci
"""
if n <= 2:
return 1
return Fib(n-1) + Fib(n-2)
for i in range(1, 11):
print(f"F({i}) = {Fib(i)}")F(1) = 1 F(2) = 1 F(3) = 2 F(4) = 3 F(5) = 5 F(6) = 8 F(7) = 13 F(8) = 21 F(9) = 34 F(10) = 55
Suite définie par récurrence
Soit la suite définie par :
$$ U_n = \begin{cases} 1 & n \le 2 \\ 3U_{n-1} + U_{n-2} & \text{sinon} \end{cases} $$
Ecrire un programme récursif permettant de calculer le n-ième terme de la suite.
def Suite(n):
"""
Calcule le n-ième terme de la suite U_n = 3U_{n-1} + U_{n-2}
"""
if n <= 2:
return 1
return 3 * Suite(n-1) + Suite(n-2)
for i in range(1, 8):
print(f"U({i}) = {Suite(i)}")U(1) = 1 U(2) = 1 U(3) = 4 U(4) = 13 U(5) = 43 U(6) = 142 U(7) = 469
Récursivité mutuelle : Pair / Impair
Un nombre N est pair si (N-1) est impair, et un nombre N est impair si (N-1) est pair.
Ecrire deux fonctions récursives mutuelles pair(N) et impair(N) permettant de savoir si un nombre N est pair et si un nombre N est impair.
def Pair(N):
"""Teste si N est pair par récursivité mutuelle"""
if N == 1:
return False
return Impair(N-1)
def Impair(N):
"""Teste si N est impair par récursivité mutuelle"""
if N == 1:
return True
return Pair(N-1)
# Tests
for i in range(1, 11):
print(f"{i} est pair ? {Pair(i)} - impair ? {Impair(i)}")1 est pair ? False - impair ? True 2 est pair ? True - impair ? False 3 est pair ? False - impair ? True 4 est pair ? True - impair ? False 5 est pair ? False - impair ? True 6 est pair ? True - impair ? False 7 est pair ? False - impair ? True 8 est pair ? True - impair ? False 9 est pair ? False - impair ? True 10 est pair ? True - impair ? False
Maximum d'un tableau
Soit un tableau X de N entiers, écrire une fonction récursive permettant de déterminer le maximum du tableau.
On peut utiliser une approche dichotomique : le maximum du tableau est le maximum entre le maximum de la moitié gauche et le maximum de la moitié droite.
def maximum(T):
"""
Trouve le maximum d'un tableau par dichotomie récursive
"""
if len(T) == 1:
return T[0]
# Principe de la recherche dichotomique
m = len(T) // 2
max1 = maximum(T[:m])
max2 = maximum(T[m:])
return max1 if max1 > max2 else max2
T = [3, 7, 2, 9, 1, 8, 5, 4]
print(f"Tableau : {T}")
print(f"Maximum : {maximum(T)}")Tableau : [3, 7, 2, 9, 1, 8, 5, 4] Maximum : 9
Vérification de tableau trié
Un tableau X est trié par ordre croissant si x(i) ≤ x(i+1), ∀ i. Écrire un algorithme récursif permettant de vérifier qu'un tableau X est trié ou non.
def est_trie(T):
"""
Vérifie récursivement si un tableau est trié par ordre croissant
"""
if len(T) == 0 or len(T) == 1:
return True
if T[0] <= T[1]:
return est_trie(T[1:])
return False
T1 = [1, 2, 3, 4, 4, 5, 7, 8]
T2 = [1, 2, 5, 4, 6, 7]
print(f"{T1} est trié ? {est_trie(T1)}")
print(f"{T2} est trié ? {est_trie(T2)}")[1, 2, 3, 4, 4, 5, 7, 8] est trié ? True [1, 2, 5, 4, 6, 7] est trié ? False
Palindrome
Un mot est un palindrome si on peut le lire dans les deux sens : de gauche à droite et de droite à gauche. Exemple : KAYAK est un palindrome.
Ecrire une fonction récursive permettant de vérifier si un mot est palindrome.
def palindrome(ch):
"""
Vérifie récursivement si une chaîne est un palindrome
"""
if len(ch) <= 1:
return True
if ch[0] == ch[-1]:
return palindrome(ch[1:len(ch)-1])
return False
mots = ["KAYAK", "RADAR", "HELLO", "MADAM", "PYTHON"]
for mot in mots:
print(f"'{mot}' est palindrome ? {palindrome(mot)}")'KAYAK' est palindrome ? True 'RADAR' est palindrome ? True 'HELLO' est palindrome ? False 'MADAM' est palindrome ? True 'PYTHON' est palindrome ? False
Propagation dans une composante connexe (1D)
Soit un tableau d'entiers contenant des valeurs 0 ou bien 1. On appelle composante connexe une suite contiguë de nombres égaux à 1. On voudrait changer la valeur de chaque composante connexe de telle sorte que la première composante ait la valeur 2, la deuxième ait la valeur 3, la 3ème ait la valeur 4 et ainsi de suite.
Réaliser deux fonctions :
- La première fonction n'est pas récursive et a pour rôle de chercher la position d'un 1 dans un tableau.
- La deuxième fonction est récursive. Elle reçoit la position d'un 1 dans une séquence et propage une valeur x à toutes les valeurs 1 de la composante connexe.
def trouver(T):
"""Trouve l'indice du premier 1 dans le tableau"""
for i in range(len(T)):
if T[i] == 1:
return i
return None
def propager(T, x, val):
"""
Propage une valeur à toute la composante connexe
Paramètres:
T: tableau
x: indice de départ
val: valeur à propager
"""
i = trouver(T)
if i is None:
return
T[i] = val
if (len(T) - i + 1) > 2:
if T[i+1] == 1:
propager(T, x, val+1)
else:
propager(T, x, x)
# Test
T = [0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1]
print("Avant propagation:", T)
propager(T, 2, 2)
print("Après propagation:", T)Avant propagation: [0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1] Après propagation: [0, 0, 2, 3, 0, 4, 5, 6, 7, 8, 0, 9, 10]
Propagation dans une image (2D)
Soit une image binaire représentée dans une matrice à 2 dimensions. Les éléments m[i][j] sont dits pixels et sont égaux soit à 0 soit à 1. Chaque groupement de pixels égaux à 1 et connectés entre eux forment une composante connexe (figure). L'objectif est de donner une valeur différente de 1 à chaque composante (2 puis 3 puis 4 etc.)
- Ecrire une fonction récursive propager permettant de partir d'un point (i,j) situé à l'intérieur d'une composante connexe et de propager une étiquette T à tous les pixels situés à l'intérieur de la composante.
- Ecrire une fonction etiqueter permettant d'affecter une étiquette différente à chaque composante connexe.
def propager(M, i, j, val):
"""
Propage une étiquette à toute une composante connexe
Paramètres:
M: matrice
i, j: coordonnées de départ
val: étiquette à propager
"""
if i < 0 or i >= len(M) or j < 0 or j >= len(M[0]) or M[i][j] != 1:
return
M[i][j] = val
# Propager dans les 4 directions
propager(M, i-1, j, val) # haut
propager(M, i+1, j, val) # bas
propager(M, i, j-1, val) # gauche
propager(M, i, j+1, val) # droite
def etiqueter(M):
"""
Étiquette chaque composante connexe avec une valeur unique
"""
L, C = len(M), len(M[0])
val = 2
for i in range(L):
for j in range(C):
if M[i][j] == 1:
propager(M, i, j, val)
val += 1
# Test
M = [
[0, 0, 1, 0],
[0, 1, 0, 1],
[1, 1, 1, 0],
[0, 1, 1, 0]
]
print("Matrice originale:")
for ligne in M:
print(ligne)
etiqueter(M)
print("\nMatrice après étiquetage:")
for ligne in M:
print(ligne)Matrice originale: [0, 0, 1, 0] [0, 1, 0, 1] [1, 1, 1, 0] [0, 1, 1, 0] Matrice après étiquetage: [0, 0, 2, 0] [0, 2, 0, 3] [2, 2, 2, 0] [0, 2, 2, 0]
- Toute fonction récursive doit avoir un cas de base qui termine la récursion.
- Les appels récursifs doivent se rapprocher du cas de base.
- La récursivité mutuelle implique deux fonctions qui s'appellent l'une l'autre.
- La diviser pour régner est une technique puissante qui utilise la récursivité.
- La récursivité peut être coûteuse en mémoire si la profondeur est grande.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.