M&A Récursivité

Section 2.2 Récursivité

Une fonction est dite récursive lorsqu'elle contient un appel à elle-même.

Attention, une telle fonction doit prévoir au moins un cas de base sur lequel elle finisse par tomber.

La fonction factorielle \(n!\) est un bon exemple de fonction pouvant être définie de manière récursive :

\begin{equation*} n!= \begin{cases} 1&\text{si}\;n=1,\\ n\cdot(n-1)!&\text{si}\;n\ge 2. \end{cases} \end{equation*}

Par exemple, on a

\begin{equation*} 5!=5\cdot\underbrace{4\cdot 3\cdot 2\cdot 1}_{4!}=5\cdot 4! \end{equation*}

de sorte que \(5!\) s'obtient par la multiplication de \(5\) avec la valeur de la fonction factorielle appliquée à 4, l'entier précédent 5.

Le code qui suit définit une fonction factorielle(n) adoptant ce point de vue récursif. On le teste avec print(factorielle(5)) qui doit afficher \(\text{120}\text{.}\)

Cliquez sur Next autant de fois que nécessaire dans l'application Python Tutor si vous voulez suivre pas à pas l'exécution du code qui précède.

Remarque 2.2.1.

Notez que pour calculer factorielle(5) avec la fonction récursive ci-dessus, il faut descendre jusqu'au cas de base factorielle(1) avant de remonter pour calculer factorielle(2), factorielle(3), factorielle(4) et enfin factorielle(5) dans cet ordre.