No history yet

Introduction à la récursivité

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

Imaginez que vous êtes face à une série de poupées russes. Pour trouver la plus petite poupée, vous ouvrez la plus grande, qui en contient une légèrement plus petite. Vous répétez ce processus : ouvrir la poupée actuelle pour en trouver une plus petite à l'intérieur, jusqu'à ce que vous arriviez à celle qui ne s'ouvre plus. Vous venez d'appliquer un processus récursif.

En programmation, la récursivité est une technique où une fonction s'appelle elle-même pour résoudre un problème. Au lieu d'utiliser une boucle pour répéter une action, la fonction se rappelle elle-même avec une version légèrement plus simple du problème initial.

Recursion is a programming technique where a function calls itself repeatedly until a specific base condition is met.

Pour qu'une fonction récursive fonctionne correctement et ne s'exécute pas à l'infini, elle doit comporter deux éléments essentiels :

  1. Un cas de base : C'est la condition d'arrêt. C'est le problème le plus simple, celui que la fonction peut résoudre directement sans avoir besoin de s'appeler à nouveau. Dans notre analogie des poupées russes, c'est la plus petite poupée qui ne peut pas être ouverte.

  2. Un appel récursif : C'est l'étape où la fonction s'appelle elle-même, mais en se rapprochant du cas de base. À chaque appel, le problème est simplifié. C'est l'action d'ouvrir une poupée pour en trouver une plus petite.

Avantages et inconvénients

Le principal avantage de la récursivité est sa capacité à simplifier le code pour des problèmes qui sont naturellement récursifs. Des tâches comme la navigation dans des structures en arborescence (comme un système de fichiers) ou le calcul de séquences mathématiques peuvent être exprimées de manière très élégante et concise avec la récursivité.

Cependant, la récursivité a aussi des inconvénients. Chaque fois qu'une fonction s'appelle elle-même, l'ordinateur doit garder en mémoire l'état de l'appel précédent. Cela se fait à l'aide d'une structure de données appelée la "pile d'appels" (call stack).

Si une fonction s'appelle elle-même trop de fois sans atteindre son cas de base, la pile d'appels peut devenir trop grande et déborder. C'est ce qu'on appelle un "débordement de pile" (stack overflow), une erreur qui provoque l'arrêt du programme.

De plus, les fonctions récursives peuvent être moins performantes que leurs équivalents itératifs (utilisant des boucles) en raison de la surcharge liée à la gestion de la pile d'appels. Le choix entre une approche récursive et une approche itérative dépend donc de la nature du problème et des contraintes de performance.

Un exemple : la factorielle

Un exemple classique pour illustrer la récursivité est le calcul de la factorielle d'un nombre entier. La factorielle de nn, notée n!n!, est le produit de tous les entiers de 1 à nn. Par exemple, 4!=4×3×2×1=244! = 4 \times 3 \times 2 \times 1 = 24. La définition mathématique elle-même est récursive :

n!={1si n=0n×(n−1)!si n>0n! = \begin{cases} 1 & \text{si } n = 0 \\ n \times (n-1)! & \text{si } n > 0 \end{cases}

On peut traduire cela directement en une fonction récursive. Voici à quoi cela ressemblerait en pseudocode, un langage simplifié qui décrit la logique d'un algorithme.

FONCTION factorielle(n)
  // Cas de base : si n est 0, la factorielle est 1.
  SI n == 0 ALORS
    RETOURNER 1
  
  // Appel récursif : multiplier n par la factorielle de (n-1).
  SINON
    RETOURNER n * factorielle(n - 1)
  FIN SI
FIN FONCTION

Voyons comment l'ordinateur calcule factorielle(3) avec cette fonction.

La fonction s'appelle elle-même en diminuant la valeur de n jusqu'à atteindre le cas de base (n = 0). Une fois le cas de base atteint, les résultats sont renvoyés en cascade, permettant de calculer le résultat final.

Quiz Questions 1/5

Quelle est la définition principale de la récursivité en programmation ?

Quiz Questions 2/5

Dans l'analogie des poupées russes, que représente le "cas de base" d'une fonction récursive ?