C4 : Récursivité
💚 Vocabulaire

Caractéristique d'une fonction récursive

Une fonction récursive s’appelle elle-même.

Principe

Pile d'appels

Lors d’une récursivité, les instructions (ou portions d’instructions) en attente sont placées dans la pile d'appels (ou pile d'exécution) puis dépilées.

C’est pour cela que la récursion peut nécessiter beaucoup de mémoire (En Python, par défaut, la pile est de taille 1000 au maximum).

Terminaison de la récursivité

Pour qu'un programme qui appelle une fonction récursive se termine, il est nécessaire que la fonction récursive contienne une condition, dite condition d'arrêt :

• - si la condition d'arrêt est vérifiée, la fonction n'est pas rappelée et le code correspondant au cas de base est exécuté ;
• - si la condition d'arrêt n'est pas vérifiée, le code contenant l'appel récursif à la fonction est exécuté.