Introduction à la récursivité en Python

Vous voulez tout savoir sur la récursivité en programmation ? Ce tutoriel sur la récursivité en Python vous aidera à démarrer.

La récursion est une technique de résolution de problèmes très utile à ajouter à la boîte à outils de votre programmeur. Bien qu’au départ il soit souvent difficile de comprendre, la récursivité peut vous aider à trouver des solutions plus élégantes à des problèmes complexes.

Dans ce didacticiel, nous adopterons une approche axée sur le code pour apprendre la récursivité à l’aide de Python. Nous aborderons notamment :

• Les bases de la récursion
• Fonctions récursives et comment elles fonctionnent
• Implémentation Python de fonctions récursives
• Différences entre les approches itératives et récursives de résolution de problèmes

Commençons!

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

La récursivité est une technique de programmation dans laquelle une fonction s’appelle à plusieurs reprises pour résoudre un problème.

À la base, la récursion est une approche de résolution de problèmes qui consiste à décomposer un problème complexe en sous-problèmes plus petits et identiques. Essentiellement, il vous permet de résoudre un problème en termes de versions plus simples de lui-même.

Alors, comment implémenter la récursivité dans le code ? Pour ce faire, comprenons comment fonctionnent les fonctions récursives.

Comprendre les fonctions récursives

Nous définissons une fonction récursive qui s’appelle dans sa définition. Chaque appel récursif représente une version plus petite ou plus simple du problème d’origine.

Pour garantir que la récursion se termine finalement, les fonctions récursives doivent inclure un ou plusieurs cas de base, c’est-à-dire des conditions dans lesquelles la fonction cesse de s’appeler et renvoie un résultat.

Décomposons cela plus en détail. Une fonction récursive consiste en :

• Cas de base : le cas de base est une ou plusieurs conditions qui déterminent le moment où la récursion doit s’arrêter. Lorsque le cas de base est satisfait, la fonction renvoie un résultat sans effectuer d’autres appels récursifs. Un cas de base est essentiel pour éviter une récursion infinie.
• Cas récursif : Le cas récursif définit comment décomposer le problème en sous-problèmes plus petits. Dans cette partie de la fonction, la fonction s’appelle avec des entrées modifiées. Chaque appel récursif est donc une étape vers l’atteinte du cas de base.

Voyons ensuite ce qui se passe lorsque vous appelez 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 comprend des informations sur les arguments de la fonction, les variables locales et l’emplacement à renvoyer une fois l’exécution de la fonction terminée.

Dans le cas de fonctions récursives, lorsqu’une fonction s’appelle elle-même, un nouvel enregistrement est placé sur la pile d’appels, suspendant ainsi l’exécution de la fonction en cours. La pile permet à Python de suivre tous les appels de fonction en attente, y compris ceux provenant d’appels récursifs.

Jusqu’à ce que le cas de base soit atteint, la récursion continue. Lorsque le cas de base renvoie un résultat, les appels de fonction sont résolus un par un, chaque fonction renvoyant 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

Dans cette section, nous explorerons trois exemples simples de récursivité :

Pour chaque exemple, nous exposerons le problème, fournirons l’implémentation récursive de Python, puis expliquerons le fonctionnement de l’implémentation récursive.

#1. Calcul factoriel utilisant la récursion

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

Le calcul factoriel se prête bien à la récursion, comme indiqué :

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

def factorial(n):
# Base case
    if n == 0 or n == 1:
        return 1
# Recursive case: n! = n * (n-1)!
    else:
        return n * factorial(n - 1)

Calculons 5 ! en utilisant la fonction factorial() :

factorial_5 = factorial(5)
print(factorial(5))
# Output: 120

Voyons maintenant comment fonctionne la fonction :

• Nous avons un cas de base qui vérifie si n est égal à 0 ou 1. Si la condition est remplie, les fonctions renvoient 1. Rappelez-vous que 0 ! est 1, et 1 aussi !.
• Si n est supérieur à 1, on calcule n ! en multipliant n par la factorielle de n-1. Ceci est exprimé par n * factoriel (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 : Trouvez le terme au nième index du Séquence de Fibonacci. La séquence 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):
# Base cases
    if n == 0:
        return 0
    elif n == 1:
        return 1
# Recursion: 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)
# Output: 5

Voici comment fonctionne la fonction :

• Commençons par discuter des cas de base. Si n est 0, il renvoie 0. Et si n est 1, il renvoie 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 ajoutant 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 décroissantes de n jusqu’à ce qu’elle atteigne les cas de base.

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

Problème : implémentez un algorithme de recherche binaire utilisant la récursion pour trouver 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):
# Base case: target not found
    if low > high:
        return -1

    mid = (low + high) // 2

# Base case: target found
    if arr[mid] == target:
        return mid
# Recursive case: search left or right half of the array
    elif arr[mid] > target:
        return binarySearch(arr, target, low, mid - 1)
    else:
        return binarySearch(arr, target, mid + 1, high)

La fonction binaireSearch continue de diviser l’intervalle de recherche en deux à chaque appel récursif jusqu’à ce qu’elle trouve la cible ou 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)
# Output: 4

Décomposons 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 renvoyons 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 renvoyons l’index mid, indiquant 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 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 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 approche courante de la résolution de problèmes. Alors, en quoi est-ce différent de la récursivité ? Découvrons-le.

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

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

def factorialRec(n):
# Base case
    if n == 0 or n == 1:
        return 1
# Recursive case: n! = n * (n-1)!
    else:
        return n * factorial(n - 1)

Parce que nous savons que la factorielle d’un nombre non négatif est le produit de tous les nombres de 1 à n, nous pouvons é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 des résultats identiques.

factorial_5 = factorialRec(5)
print(factorial_5)
# Output: 120

factorial_5 = factorialIter(5)
print(factorial_0)
# Output: 120

Mais une approche itérative est-elle préférable à la récursivité ? Lorsqu’il y a une récursion profonde (avec trop d’appels de fonction), vous pouvez rencontrer des erreurs en raison du dépassement de la profondeur de récursion. Le bouclage est une meilleure option pour les problèmes dont 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 :

FonctionnalitéApproche récursiveApproche itérativeStructureUtilise des appels de fonction récursifs et s’appuie sur la pile d’appels.Utilise des boucles pour l’itération sans appels de fonction supplémentaires.Cas de baseNécessite des cas de base explicites pour arrêter la récursion.Utilise généralement des conditions de boucle pour la terminaison.PerformancePeut être moins économe en mémoire en raison de la pile d’appels . Une récursivité profonde peut parfois entraîner des erreurs de débordement de pile. Généralement plus efficace en mémoire et moins sujette aux erreurs de débordement de pile. Débogage Peut être difficile à déboguer en raison de plusieurs appels de fonction et de contextes d’exécution imbriqués. Généralement plus facile à déboguer en raison d’un flux d’exécution linéaire simple .Approche itérative ou récursive

Conclusion

Dans cet article, nous avons commencé par apprendre ce qu’est la récursivité et comment définir des fonctions récursives avec des cas de base et des relations de récurrence.

Nous avons ensuite écrit du code Python, des implémentations récursives de problèmes de programmation courants. Enfin, nous avons appris les différences entre les approches itératives et récursives ainsi que les avantages et les inconvénients de chacune de ces approches.

Ensuite, consultez cette liste de questions d’entretien Python.