Récursivité
Lorsque nous apprenons la programmation, nous traitons souvent les tâches de manière linéaire et directe. Mais que faire si nous rencontrons un problème qui nécessite de le décomposer en problèmes plus petits et similaires ? C'est là que la récursivité entre en jeu.
En termes simples, la récursivité se produit lorsqu'une fonction s'appelle elle-même pendant son exécution. Cela peut sembler créer une boucle infinie, mais si nous concevons correctement notre fonction, elle atteindra finalement un point où elle ne s'appellera plus elle-même.
Imaginez une poupée Matriochka. Chaque fois que vous ouvrez une poupée, il y en a une plus petite à l'intérieur, et vous continuez jusqu'à atteindre la plus petite poupée qui ne peut pas être ouverte. Ce processus d'ouverture des poupées ressemble à la récursivité. Pour atteindre la plus petite poupée, ce qui revient à résoudre le problème le plus complexe, vous le faites en résolvant à plusieurs reprises des versions plus simples du même problème (ouvrir les poupées plus grandes) jusqu'à ce que vous atteigniez un point où le problème ne peut plus être réduit davantage (la dernière poupée).
Le processus consistant à résoudre un grand problème en le divisant récursivement en problèmes plus petits jusqu'à atteindre le plus petit ou le plus simple possible est mieux compris grâce au concept du « saut de foi récursif ».
Le saut de foi récursif
Lorsqu'on implémente une solution récursive à un problème, on crée généralement une fonction qui s'appelle elle-même à un certain moment. Cette partie où la fonction s'appelle elle-même est appelée l'appel récursif.
L'avantage des solutions récursives est que l'on peut supposer que la fonction fonctionne correctement lorsqu'elle est appelée avec des arguments simples, puis implémenter le comportement correct pour les cas plus complexes. Comme lorsque nous utilisons des fonctions comme
sqrt, max, abs, et d'autres que nous avons déjà utilisées, vous pouvez supposer que la fonction fonctionne pour des arguments plus petits ou plus simples et utiliser ces appels pour construire le résultat actuel à partir de ceux-ci.💡
La seule exigence est de s'assurer que la fonction atteindra le cas de base (le cas le plus simple). Sinon, nous aurions une fonction récursive qui s'exécuterait indéfiniment et nous pourrions obtenir un StackOverflow !
Pour illustrer comment effectuer un calcul à l'intérieur d'une fonction récursive, nous pouvons essayer de calculer la somme de tous les nombres de
0, 1, 2, …, n, étant donné un nombre n.Implémentons la fonction
sum étape par étape. La première étape est de s'assurer que la fonction fonctionne correctement pour le cas le plus simple (calculer correctement la somme pour n étant 0 ou 1) :def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0: # Si n est 0 => la somme est 0
return 0 # Arrêter l'exécution de la fonction ici
if n == 1: # Si n est 1 => la somme est 1
return 1 # Arrêter l'exécution de la fonction ici
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> None (comme nous n'avons pas encore implémenté cette partie)Avec cette partie de la fonction, nous pouvons déjà utiliser le fait que
sum(0) retournera toujours 0 correctement, tandis que sum(1) retournera toujours 1. La fonction fonctionnera correctement même si nous appelons la fonction sum avec les arguments 0 ou 1 depuis la fonction sum elle-même.Nous pouvons donc aller un peu plus loin et implémenter la fonction
sum pour n = 2 et n = 3 en utilisant les résultats de sum(1) et sum(0) :def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2: # Si n est 2, nous pouvons ajouter 2 au résultat de sum(1) implémenté ci-dessus
return n + sum(1) # ou n + sum(n - 1)
if n == 3: # Si n est 3, nous pouvons ajouter 3 au résultat de sum(2) implémenté ci-dessus
return n + sum(2) # ou n + sum(n - 1)
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> None (comme nous n'avons pas encore implémenté cette partie)De cette manière, il est évident que la fonction
sum fonctionne correctement pour les petits cas où n est égal à 0, 1, 2 ou 3.Ayant cela, nous pouvons implémenter la fonction pour d'autres valeurs de
n supérieures à 3. La seule exigence est d'atteindre ces valeurs plus petites de n (0, 1, 2 ou 3) lors de l'appel de la fonction sum depuis elle-même. Ainsi, pour des valeurs plus grandes de n, comme 4, 5, 6, etc., nous pouvons implémenter la fonction sum en utilisant le fait que pour calculer sum(4), nous pouvons ajouter 4 au résultat de sum(3), tandis que pour calculer sum(5), nous pouvons ajouter 5 au résultat de sum(4) :def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2:
return n + sum(1)
if n == 3:
return n + sum(2)
# Pour tous les autres cas (4, 5, 6, ...)
return n + sum(n - 1)
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> sum(3) -> sum(2) -> sum(1) -> 10
# ...Les éléments clés d'une fonction récursive sont :
- Cas de base : une condition qui arrête la récursion. Sans cela, la fonction s'appellerait elle-même indéfiniment, provoquant une boucle infinie.
Ici, ce sont
n == 0etn == 1.
- Étape récursive : l'endroit où la fonction s'appelle elle-même, généralement avec un argument différent.
Ici, c'est
sum(n - 1).
Comme les appels pour
n == 1, n == 2 et n == 3 sont exactement les mêmes que pour n == 4, n == 5, etc., nous pouvons même simplifier la fonction sum en ayant seulement un cas de base (pour n == 0) :def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
return n + sum(n - 1)
print(sum(2)) # sum(2) -> sum(1) -> sum(0) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> sum(0) -> 6
print(sum(4)) # sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0) -> 10
# ...De cette manière, en faisant le saut de foi récursif, nous supposons/savons que la fonction fonctionne correctement pour des cas plus petits ou plus simples, et nous construisons le reste de la fonction sur la base de ces cas plus simples. Cela aide à comprendre comment fonctionnent les fonctions récursives et comment elles peuvent être implémentées.
💡
Appeler la fonction de manière récursive, c'est comme appeler une fonction totalement différente dont vous savez avec certitude qu'elle fonctionnera avec les arguments passés.