Récursivité : principe, condition d'arrêt et complexité des algorithmes récursifs

En 30 secondes

• Une fonction récursive s'appelle elle-même sur une version plus petite du problème, jusqu'à un cas de base résolu directement.
• La condition d'arrêt détecte le cas de base ; sans elle, les appels continuent indéfiniment (erreur d'exécution).
• Le résultat se construit en remontant les appels empilés, une fois le cas de base atteint.

Ce que tu sauras faire

• Expliquer le principe d'une fonction récursive et le rôle de sa condition d'arrêt.
• Dérouler l'exécution d'une fonction récursive simple, appel par appel.
• Distinguer une fonction récursive correcte d'une fonction sans condition d'arrêt valide.
• Déterminer la complexité en temps et en espace d'une fonction récursive simple à partir du nombre d'appels qu'elle effectue.

Les mots à connaître

Récursivité

le principe de programmation dans lequel une fonction résout un problème en s'appelant elle-même sur une version plus petite ou plus simple de ce même problème.

Récursion

un synonyme de récursivité, désignant le fait pour une fonction de s'appeler elle-même.

Fonction récursive

une fonction qui, dans son propre code, contient un appel à elle-même sur des données modifiées, généralement plus petites que celles reçues initialement.

Le piège classique

Oublier la condition d'arrêt dans une fonction récursive : sans elle, la fonction s'appelle indéfiniment jusqu'à provoquer une erreur.

L'astuce

Une fonction récursive sans condition d'arrêt, c'est un escalier qui descend sans jamais atteindre le sol : elle ne s'arrête jamais.