Introduction à la récursivité en Python

Intéressé par la récursivité en programmation ? Ce guide sur la récursivité en Python est fait pour vous aider à démarrer votre apprentissage.

La récursivité est une technique de résolution de problèmes très puissante pour un développeur. Bien qu’elle puisse sembler complexe au premier abord, la récursivité permet de concevoir des solutions élégantes pour des défis de programmation complexes.

Dans ce tutoriel, nous allons explorer la récursivité en utilisant une approche pratique axée sur le code Python. Nous aborderons les points suivants :

• Les principes fondamentaux de la récursivité
• Le fonctionnement des fonctions récursives
• L’implémentation de fonctions récursives en Python
• La comparaison entre les approches itératives et récursives de résolution de problèmes

C’est parti !

Qu’est-ce que la récursivité ?

La récursivité est une technique de programmation où une fonction s’appelle elle-même de manière répétée pour résoudre un problème.

Fondamentalement, la récursivité est une méthode de résolution de problèmes qui consiste à diviser un problème complexe en sous-problèmes plus simples et semblables. Elle permet de résoudre un problème en le définissant en termes de versions plus petites de lui-même.

Comment implémenter la récursivité dans le code ? Pour cela, il est essentiel de comprendre le fonctionnement des fonctions récursives.

Comprendre les fonctions récursives

Une fonction récursive est une fonction qui s’appelle elle-même dans sa propre définition. Chaque appel récursif traite une version réduite ou simplifiée du problème initial.

Pour que la récursivité se termine, les fonctions récursives doivent comporter un ou plusieurs cas de base, c’est-à-dire des conditions où la fonction cesse de s’appeler et retourne un résultat.

Décomposons ceci plus en détail. Une fonction récursive comprend :

• Cas de base : le cas de base est une ou plusieurs conditions qui déterminent quand arrêter la récursion. Lorsque le cas de base est atteint, la fonction retourne un résultat sans effectuer d’autres appels récursifs. Un cas de base est crucial pour éviter une récursion infinie.
• Cas récursif : le cas récursif définit la manière dont le problème est divisé en sous-problèmes plus petits. Dans cette partie, la fonction s’appelle elle-même avec des données d’entrée modifiées. Chaque appel récursif rapproche de la condition du cas de base.

Voyons ce qui se passe lors de l’appel d’une fonction récursive.

Comment fonctionne la récursivité sous le capot

Lorsqu’une fonction est appelée, un enregistrement de son contexte d’exécution est placé sur la pile d’appels. Cet enregistrement contient des informations telles que les arguments de la fonction, les variables locales, et l’adresse de retour après l’exécution de la fonction.

Dans le cas d’une fonction récursive, lorsqu’elle s’appelle elle-même, un nouvel enregistrement est empilé, mettant en pause l’exécution de la fonction en cours. La pile permet à Python de suivre tous les appels de fonction en attente, y compris ceux résultant des appels récursifs.

La récursion continue jusqu’à ce qu’un cas de base soit atteint. Lorsque le cas de base retourne un résultat, les appels de fonction sont résolus un par un, chaque fonction retournant son résultat au niveau précédent de la pile d’appels. Ce processus se poursuit jusqu’à la fin de l’appel de fonction initial.

Implémentation de la récursivité en Python

Nous allons maintenant étudier trois exemples simples d’utilisation de la récursivité :

• Calcul de la factorielle d’un nombre
• Calcul des nombres de Fibonacci
• Implémentation de la recherche binaire par récursivité

Pour chaque exemple, nous allons expliquer le problème, présenter l’implémentation récursive en Python, et détailler le fonctionnement de l’implémentation.

#1. Calcul factoriel utilisant la récursion

Problème : Calculer la factorielle d’un entier non négatif n, notée n!. Mathématiquement, la factorielle d’un nombre n est le produit de tous les entiers positifs de 1 jusqu’à n.

Le calcul de la factorielle se prête bien à la récursion, comme illustré ci-dessous :

Voici la fonction récursive pour calculer la factorielle d’un nombre n donné :

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

Calculons 5 ! à l’aide de la fonction factorial() :

factorial_5 = factorial(5)
print(factorial(5))
# Résultat : 120

Décortiquons le fonctionnement de la fonction :

• Nous avons un cas de base qui vérifie si n est égal à 0 ou 1. Si cette condition est remplie, la fonction retourne 1. N’oubliez pas que 0! est 1, et que 1! est également 1.
• Si n est supérieur à 1, on calcule n! en multipliant n par la factorielle de n-1. Cela est exprimé par n * factorielle(n – 1).
• La fonction continue d’effectuer des appels récursifs avec des valeurs décroissantes de n jusqu’à ce qu’elle atteigne le cas de base.

#2. Nombres de Fibonacci avec récursion

Problème : Trouver le terme à l’index n de la Suite de Fibonacci. La suite de Fibonacci est définie comme suit : F(0) = 0, F(1) = 1, et F(n) = F(n-1) + F(n-2) pour n >= 2.

def fibonacciSeq(n):
    # Cas de base
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # Récursion : F(n) = F(n-1) + F(n-2)
    else:
        return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)

Exécutons la fonction :

fib_5 = fibonacciSeq(5)
print(fib_5)
# Résultat : 5

Voici comment la fonction opère :

• Commençons par les cas de base. Si n est 0, la fonction retourne 0. Et si n est 1, elle retourne 1. Rappelez-vous F(0) = 0 et F(1) = 1.
• Dans le cas récursif, si n est supérieur à 1, la fonction calcule F(n) en additionnant les termes F(n-1) et F(n-2). Ceci est exprimé par fibonacciSeq(n – 1) + fibonacciSeq(n – 2).
• La fonction continue d’effectuer des appels récursifs avec des valeurs de n décroissantes jusqu’à ce qu’elle atteigne les cas de base.

#3. Implémentation récursive de la recherche binaire

Problème : Implémenter un algorithme de recherche binaire en utilisant la récursion pour localiser la position d’un élément cible dans une liste triée.

Voici l’implémentation récursive de la recherche binaire :

def binarySearch(arr, target, low, high):
    # Cas de base : cible introuvable
    if low > high:
        return -1

    mid = (low + high) // 2

    # Cas de base : cible trouvée
    if arr[mid] == target:
        return mid
    # Cas récursif : recherche dans la moitié gauche ou droite du tableau
    elif arr[mid] > target:
        return binarySearch(arr, target, low, mid - 1)
    else:
        return binarySearch(arr, target, mid + 1, high)

La fonction binarySearch continue de diviser l’intervalle de recherche en deux à chaque appel récursif jusqu’à ce qu’elle trouve la cible ou qu’elle détermine que la cible n’est pas dans la liste.

Voici un exemple d’exécution de la fonction :

arr = [5, 8, 13, 24, 37, 49, 51, 64, 72, 88, 96]
target = 37
idx = binarySearch(arr, target, 0, len(arr)-1)
print(idx)
# Résultat : 4

Analysons ce que fait la fonction :

• Dans l’implémentation récursive de la recherche binaire, nous avons deux cas de base. Premièrement, si low devient supérieur à high, cela signifie que l’élément cible n’est pas dans la liste. Nous retournons donc -1 pour indiquer que la cible n’a pas été trouvée.
• L’autre cas de base vérifie si l’élément situé à l’index médian de l’intervalle de recherche actuel est égal à la cible. S’ils correspondent, nous retournons l’index mid, signalant que nous avons trouvé la cible.
• Dans le cas récursif, si l’élément du milieu est supérieur à la cible, nous recherchons récursivement dans la moitié gauche du tableau en appelant binaireSearch(arr, target, low, mid – 1). Si l’élément du milieu est inférieur à la cible, nous recherchons dans la moitié droite en appelant binaireSearch(arr, target, mid + 1, high).

Approche récursive ou itérative

L’approche itérative (utilisant des boucles) est une autre méthode courante de résolution de problèmes. En quoi diffère-t-elle de la récursivité ? Voyons cela de plus près.

Tout d’abord, comparons les solutions récursives et itératives pour un problème commun : le calcul de la factorielle d’un nombre.

Voici l’implémentation récursive du calcul factoriel :

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

Sachant que la factorielle d’un nombre non négatif est le produit de tous les nombres de 1 jusqu’à n, on peut également écrire une implémentation itérative à l’aide de boucles.

def factorialIter(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

Ces deux implémentations donnent les mêmes résultats.

factorial_5 = factorialRec(5)
print(factorial_5)
# Résultat : 120

factorial_5 = factorialIter(5)
print(factorial_0)
# Résultat : 120

Une approche itérative est-elle préférable à la récursivité ? En cas de récursion profonde (avec de nombreux appels de fonctions), vous risquez des erreurs dues à un dépassement de la profondeur de récursion. Les boucles sont plus adaptées aux problèmes où l’implémentation récursive nécessite trop d’appels de fonction pour atteindre le cas de base.

Résumons les différences entre les implémentations itératives et récursives :

Conclusion

Dans cet article, nous avons débuté par la définition de la récursivité et la conception de fonctions récursives avec des cas de base et des relations de récurrence.

Nous avons ensuite écrit des exemples de code Python avec des implémentations récursives pour des problèmes de programmation courants. Enfin, nous avons exploré les différences entre les approches itératives et récursives, ainsi que leurs avantages et inconvénients respectifs.

Pour approfondir vos connaissances, vous pouvez consulter cette liste de questions d’entretien Python.