Les fonctions récursives permettent de simplifier l'écriture de nombreux problèmes. Nous présentons ici leur fonctionnement et une méthodologie d'écriture et d'analyse de ces fonctions.

IIntroduction à la récursivité

Une fonction récursive est une fonction qui s'appelle elle-même. Voici un premier exemple classique.

Cette fonction implémente simplement une façon (récursive) de définir la puissance d'un nombre $a\ne 0$ : $a^0=1$ et $a^n=a\times a^{n-1}$.

On remarque que la fonction commence par une condition d'arrêt qui traite le cas de base. Pour étudier le fonctionnement interne de cette fonction, on peut réécrire la fonction précédente :

IIPile d'exécution

Lors de l'appel d'une fonction récursive, une structure de pile est utilisée en interne.

Une pile fonctionne comme un empilement d'objets (l'image d'une pile d'assiettes est adaptée) : on peut empiler un objet en haut de la pile et enlever le sommet de la pile (on dit dépiler), mais on ne peut pas accéder à un objet qui n'est pas en haut de la pile.

La pile utilisée, appelée pile d'exécution, est de taille limitée. Au-delà d'un certain nombre d'appels récursifs, 1 000 par défaut en Python, il y a une erreur de dépassement de la taille de la pile (stack overflow). Cette pile contient une trace de tous les appels de fonction qui ne se sont pas encore terminés.

Concrètement, un appel récursif à expo(2, 3) donne, de manière très simplifiée :

Évolution de la pile d'exécution, puis dépilement pour évaluer :

IIIÉcriture d'une fonction récursive

Une fonction récursive simple s'écrit sous la forme :

Pour écrire une fonction récursive on :

− détermine le type de données à renvoyer ;

− détermine pour quelle(s) valeur(s) de l'argument le problème est résolu et on écrit la condition d'arrêt ;

− détermine de quelle manière la taille du problème est réduite (argument entier qui décroît strictement, liste dont la taille diminue, etc.) ;

− écrit l'appel récursif en prenant garde à ce que le type de données qu'il renvoie soit cohérent avec celui renvoyé par la condition d'arrêt.

IVÉtude de la complexité d'une fonction récursive

On note $T_n$ le nombre d'opérations nécessaires pour évaluer une fonction récursive sur un problème de taille $n$. Pour évaluer $T_n$ on cherche une relation de récurrence impliquant $T_n$, puis on résout la relation de récurrence.

Exemple : nombre d'opérations pour le calcul de la puissance d'un nombre. On a $T_0=1$ et $T_{n+1}=T_n+1$. On reconnaît une suite arithmétique, d'où $T_n=n+1$.

Voici quelques complexités classiques :