Introduction générale à la programmation/Récursivité

Début de la boite de navigation du chapitre

La récursivité est le phénomène de faire appel à soi même.

fin de la boite de navigation du chapitre

Dans la programmation, la récursivité est très utilisée, notamment dans les fonctions.

En effet, une fonction est une procédure qui retourne une valeur. Cette spécificité permet donc de créer une fonction qui s’appelle elle-même en passant en paramètre le résultat du traitement effectué, et bien sûr ce second appel pourra lui-même appeler la fonction une troisième fois, et ainsi de suite.

On obtient donc un empilement d'appels, chacun réalisant une étape d’un traitement (souvent une manipulation de chaine de caractère).

Lorsqu'on arrive au bout du traitement, la dernière fonction fille appelée retourne une valeur qui se propagera jusqu'à la fonction mère par le même procédé. C’est de cette façon qu'une fonction récursive se termine.

Il est donc nécessaire de retenir deux points importants caractérisant la récursivité :

• la pile mémoire est abondamment utilisée par la récursivité (la plupart des erreurs de programmation récursive génèrent un dépassement de pile) ;
• une fonction récursive doit impérativement avoir une condition de fin qui provoquera le dépilement.

Voir aussi la leçon « Récursivité dans l'algorithmique et la programmation ».

Exemple

L'exemple qui suit est particulièrement inutile, dans la mesure où l'opération effectuée par la procédure pourrait être réalisée bien plus efficacement, et sans utiliser de fonctions — il s'agit donc avant tout d'une illustration de ce principe :

Début de l'exemple

Exemple

On pose la fonction suivante :

fonction inutile(entier a, entier n)
    si n = 0 alors
        retourner a
    sinon
        retourner inutile(a + n, n - 1)
    fin si
fin de fonction

Il s'agit là du prototype d'une fonction « récursive » : elle fait appel à elle-même (cinquième ligne). On peut chercher à comprendre ce qu'elle effectue comme calculs :

• si n est nul, elle renvoie a sans effectuer d'opérations ;
• si n est non nul, elle s’appelle elle-même avec de nouveaux arguments.

On voit facilement que cette fonction renvoie en fin de compte :

a + n + (n-1) + (n-2) + ··· + 3 + 2 + 1

(Rappelons, encore une fois, qu'effectuer le calcul en utilisant une fonction n'a aucun intérêt.)

Fin de l'exemple

Récursivité et fonctions

Quelques exemples classiques de mise en œuvre de la récursivité :

• Calcul de n!
• Résolution de la tour de Hanoï.
• Vérification d’un palindrome.

En outre, on peut aussi appeler une fonction depuis cette même fonction.