La récursivité en Python

LaRecursivite

La récursivité est une technique qui conduit à des solutions élégantes aux problèmes qui sont difficiles à programmer à l’aide de boucles simples.

Supposons que vous voulez trouver tous les fichiers dans un répertoire contenant un mot particulier. Comment pouvez-vous résoudre ce problème? Il y a plusieurs façons de le faire.

Une solution intuitive et efficace est d’utiliser la récursivité en recherchant les fichiers dans chaque sous-répertoire récursivement.

Utiliser la récursivité c’est programmer une fonction qui fait appel à elle-même.
La récursivité est une technique de programmation utile. Dans certains cas, il vous permet de développer une solution naturelle et simple à un problème difficile. Ce chapitre présente les concepts et les techniques de programmation récursive et présente des exemples qui vous montrent comment «penser récursivement ».

Étude de cas: calculer la factorielle

De nombreuses fonctions mathématiques sont définies en utilisant la récursivité. Commençons par un exemple simple. La factorielle récursive d’un nombre n est définie comme suit:

0! = 1;
n! = n * (n - 1)! pour n > 0

Comment trouvez-vous la valeur de n! pour un nombre n donné? Trouver 1! est facile, parce que vous savez que 0! est 1 et 1! = 1 × 0 !. En supposant que vous savez (n – 1) !, vous pouvez obtenir n! immédiatement à l’aide de n × (n – 1) !. Ainsi, le problème du calcul du n! est réduit au calcul de (n – 1) !.

Lors du calcul de (n – 1) !, vous pouvez appliquer la même idée récursive jusqu’à ce que n est réduit à 0. Soit factorielle (n) la fonction de calcul de n!. Si vous appelez la fonction factorielle() avec n = 0, il retourne immédiatement le résultat. La fonction sait comment résoudre le cas le plus simple, qui est défini comme le cas de base ou de l’état d’arrêt.

Lors de l’appel de la fonction factorielle, avec n> 0, on réduit le problème à un problème secondaire qui consiste à calculer la factorielle de n – 1. Le problème secondaire est essentiellement le même que le problème initial, mais il est plus simple ou plus petit. Parce que le sous-problème a la même propriété que le problème d’origine, vous pouvez appeler la fonction avec un paramètre de taille différente. Dans ce cas cet appel est dit « appel récursif ».

L’algorithme récursif pour calculer factoriel (n) peut être simplement décrit comme suit:

if n == 0:
   return 1
else:
   return n * factorial(n - 1)

Un appel récursif peut entraîner de nombreux appels récursifs de plus, parce que la fonction continue à diviser un sous-problème en nouveaux sous-problèmes. Pour qu’une fonction récursive s’arrête de faire nouveaux appels récursif, le problème doit finalement être réduit à un cas d’arrêt, à quel point la fonction renvoie un résultat au lieu de faire un nouvel appel récursif.

Dans ce cas, la fonction effectue un calcul et renvoie le résultat à son appelant (par exemple, factorielle(n) est l’appelant de factorielle(n-1) et ainsi de suite). Ce processus se poursuit jusqu’à ce que le résultat est transmis à l’appelant d’origine factorielle(n). Le problème initial peut maintenant être résolu en multipliant par n le résultat de factoriel (n – 1).

def main():
   n = eval(input("Enter a nonnegative integer: "))
   print("Factorial of", n, "is", factorial(n))

# Return the factorial for the specified number
def factorial(n):
   if n == 0: # Base case
      return 1
   else:
      return n * factorial(n - 1) # Recursive call

main() # Call the main function

La fonction factorielle (lignes 6-10) est essentiellement une traduction directe de la définition mathématique récursive pour la factorielle en Python. La fonction factorielle() est récursive parce qu’elle appelle lui-même. Le paramètre passé à factorielle est décrémentée jusqu’à ce qu’il atteigne le cas de base de 0.

Maintenant que vous avez vu comment écrire une fonction récursive, nous allons voir comment fonctionne la récursivité. La figure suivante illustre l’exécution des appels récursifs, en commençant par n = 4.

RecursivitePython

Si la récursivité n’a pas réduit le problème d’une manière qui lui permet de converger finalement vers le cas de base, alors une récursivité infinie est produite.

Par exemple, supposons que vous avez écrit la fonction factorielle comme suit:

def factorial(n):
   return n * factorial(n - 1)

La fonction est exécutée infiniment et provoque une erreur d’exécution.

Résolution de problèmes en utilisant la récursivité

Si vous pensez d’une façon récursive, de nombreux problèmes peuvent être résolus en utilisant la récursivité.

Toutes les fonctions récursives ont les caractéristiques suivantes:

  • La fonction est implémentée en utilisant un if-else ou un if-elif-else qui mène à des cas différents.
  • Un ou plusieurs cas de base (le cas le plus simple) sont utilisés pour arrêter la production de nouveaux appels récursifs.
  • Chaque appel récursif réduit le problème d’origine de façon qu’il devienne de plus en plus proche du cas de base jusqu’à ce qu’il devienne ce cas.

En général, pour résoudre un problème par récursivité, vous le divisez en sous-problème. Chaque sous-problème est presque le même que le problème initial, mais il est de taille plus petite. Vous pouvez appliquer la même approche à chaque sous-problème pour le résoudre de manière récursive.

Récursivité vs. Itération

La récursivité est une autre structure de contrôle. Il permet essentiellement la répétition d’un traitement sans utiliser une boucle.

Lorsque vous utilisez des boucles, vous spécifiez un corps de la boucle. La répétition du corps de la boucle est contrôlée par la structure de contrôle (for ou while). Dans la récursivité, la fonction elle-même est appelée à plusieurs reprises. Une instruction if doit être utilisée pour permettre un appel récursif ou non.

Tout problème résolu de manière récursive peut être résolu avec des itérations non-récursives.

Alors, qu’elle est la valeur ajoutée de la récursivité?
Dans certains cas, utilisant la récursivité nous permet d’écrire une solution claire, simple pour un problème fondamentalement récursif qui serait autrement difficile à résoudre en suivant une approche itérative. Par exemple, le problème de parcours d’une arborescence de répertoires, les tours de Hanoi, et le problème des fractales sont assez lourds à résoudre sans l’aide de la récursivité.

La décision d’utiliser la récursivité ou l’itération doit être fondée sur la nature et votre compréhension du problème que vous essayez de résoudre. La règle de base est d’utiliser selon l’approche peut mieux développer une solution intuitive qui reflète naturellement le problème. Si une solution itérative est évidente, l’utiliser sera généralement plus efficace qu’une solution récursive.

LAISSER UN COMMENTAIRE

Please enter your comment!
Please enter your name here