Numérique et Sciences Informatiques > Langages de Programmation > Introduction à un Langage Spécifique (Python par exemple) > Fonctions

Les Fonctions Récursives en Python : Un Concept Avancé

Explorez le concept de récursion en Python, où une fonction s'appelle elle-même pour résoudre un problème. Découvrez des exemples classiques comme le calcul de la factorielle et la suite de Fibonacci, expliqués de manière claire et concise pour les élèves de lycée.

Qu'est-ce que la récursion ?

La récursion est une technique de programmation où une fonction s'appelle elle-même pour résoudre un problème. C'est comme une poupée russe : chaque poupée contient une poupée plus petite, et ainsi de suite, jusqu'à la plus petite poupée. Pour qu'une fonction récursive fonctionne correctement, elle doit avoir une condition d'arrêt. C'est la condition qui indique quand la fonction doit arrêter de s'appeler elle-même et renvoyer une valeur. Sans condition d'arrêt, la fonction s'appellerait indéfiniment, ce qui entraînerait une erreur (dépassement de la pile d'exécution).

Exemple : Calcul de la factorielle

La factorielle d'un nombre entier positif n (notée n!) est le produit de tous les entiers positifs inférieurs ou égaux à n. Par exemple, 5! = 5 * 4 * 3 * 2 * 1 = 120. Voici une fonction récursive pour calculer la factorielle : def factorielle(n): if n == 0: # Condition d'arrêt : la factorielle de 0 est 1 return 1 else: return n * factorielle(n - 1) # Appel récursif print(factorielle(5)) # Affiche : 120 Explication :

  • Si n est égal à 0, la fonction renvoie 1 (condition d'arrêt).
  • Sinon, la fonction renvoie n multiplié par la factorielle de n-1. Cela signifie que la fonction s'appelle elle-même avec une valeur de n plus petite.

Exemple : Suite de Fibonacci

La suite de Fibonacci est une suite de nombres où chaque nombre est la somme des deux nombres précédents. La suite commence généralement par 0 et 1. La suite de Fibonacci : 0, 1, 1, 2, 3, 5, 8, 13, 21, ... Voici une fonction récursive pour calculer le n-ième nombre de Fibonacci : def fibonacci(n): if n <= 1: # Condition d'arrêt : les nombres de Fibonacci pour 0 et 1 sont 0 et 1 respectivement return n else: return fibonacci(n - 1) + fibonacci(n - 2) # Appel récursif print(fibonacci(7)) # Affiche : 13 Explication :

  • Si n est inférieur ou égal à 1, la fonction renvoie n (condition d'arrêt).
  • Sinon, la fonction renvoie la somme du (n-1)-ième et du (n-2)-ième nombre de Fibonacci. Cela signifie que la fonction s'appelle elle-même deux fois avec des valeurs de n plus petites.

Avantages et inconvénients de la récursion

Avantages :

  • Permet d'écrire du code élégant et concis pour certains problèmes.
  • Peut rendre le code plus facile à comprendre pour les problèmes qui se définissent naturellement de manière récursive.
Inconvénients :
  • Peut être moins efficace que les solutions itératives (boucles) en termes de temps d'exécution et d'utilisation de la mémoire.
  • Peut entraîner un dépassement de la pile d'exécution si la profondeur de la récursion est trop importante (c'est-à-dire, si la fonction s'appelle elle-même trop de fois sans atteindre la condition d'arrêt).
  • Peut être plus difficile à déboguer que les solutions itératives.

Ce qu'il faut retenir

  • La récursion est une technique de programmation où une fonction s'appelle elle-même.
  • Une fonction récursive doit avoir une condition d'arrêt pour éviter une boucle infinie.
  • Des exemples classiques de récursion incluent le calcul de la factorielle et la suite de Fibonacci.
  • La récursion peut être élégante et concise, mais elle peut aussi être moins efficace et plus difficile à déboguer que l'itération.

← Les Exceptions : une gestion des erreurs sophistiquée Les Fonctions en Python : Guide Complet pour le Lycée →

FAQ

  • Qu'est-ce qu'une condition d'arrêt dans une fonction récursive ?

    La condition d'arrêt est la condition qui indique quand la fonction doit arrêter de s'appeler elle-même et renvoyer une valeur. Elle est essentielle pour éviter une boucle infinie.
  • Quand est-il préférable d'utiliser la récursion plutôt que l'itération ?

    La récursion est préférable pour les problèmes qui se définissent naturellement de manière récursive et où la concision et la clarté du code sont importantes. Cependant, il faut être conscient des inconvénients potentiels en termes d'efficacité et de débogage.
  • Qu'est-ce qu'un dépassement de la pile d'exécution ?

    Un dépassement de la pile d'exécution se produit lorsque la profondeur de la récursion est trop importante, c'est-à-dire, si la fonction s'appelle elle-même trop de fois sans atteindre la condition d'arrêt. Cela peut entraîner un arrêt brutal du programme.