Qu'est-ce que la récursivité ? Une définition simple
En informatique, et particulièrement dans ta spécialité Numérique et Sciences Informatiques (NSI), tu vas souvent rencontrer le concept de récursivité. Mais qu'est-ce que c'est exactement ? Imagine une poupée russe. Pour ouvrir la plus grande, tu trouves une plus petite à l'intérieur, identique. Pour l'ouvrir, tu en trouves une encore plus petite, et ainsi de suite. La récursivité, c'est un peu ça : c'est le fait qu'une fonction puisse s'appeler elle-même pour résoudre un problème.
Une fonction récursive est donc une fonction qui, dans sa propre définition, fait appel à elle-même. Cela permet de résoudre des problèmes complexes en les décomposant en sous-problèmes identiques mais plus petits. C'est un outil extrêmement puissant pour manipuler des structures comme les arbres, les listes ou pour implémenter des algorithmes de tri ou de parcours.
Les deux piliers indispensables d'une fonction récursive
Pour qu'une fonction récursive fonctionne correctement et ne tourne pas à l'infini (ce qui provoquerait une erreur de type RecursionError), elle doit absolument respecter deux règles :
1. Le ou les cas de base
C'est la condition d'arrêt. C'est le moment où la fonction ne s'appelle plus elle-même et renvoie un résultat simple, directement calculable. Sans cas de base, ta fonction appellerait sans fin des copies d'elle-même, comme un miroir face à un autre miroir.
2. Le ou les appels récursifs
C'est l'étape où la fonction s'appelle elle-même, mais sur un problème plus petit ou simplifié. L'idée est qu'à chaque appel, on se rapproche inexorablement du cas de base.
Pense à monter un escalier. Le cas de base, c'est quand tu es arrivé à l'étage souhaité (tu ne montes plus de marche). L'appel récursif, c'est « pour monter N marches, monte une marche, puis monte (N-1) marches ».
Exemples classiques en Python pour bien comprendre
Passons à la pratique avec des exemples que tu rencontreras sûrement en NSI.
Exemple 1 : Le calcul de la factorielle
La factorielle d'un entier n (notée n!) est le produit de tous les entiers de 1 à n. Par définition mathématique : n! = n * (n-1)!. On voit déjà la récursivité ! Le cas de base : 0! = 1.
def factorielle(n):
# Cas de base
if n == 0:
return 1
# Appel récursif : le problème (n!) est réduit à (n-1)!
else:
return n * factorielle(n-1)
print(factorielle(5)) # Affiche 120 (5*4*3*2*1)
À chaque appel, n diminue jusqu'à atteindre 0, déclenchant le retour des résultats en cascade.
Exemple 2 : La suite de Fibonacci
Chaque terme est la somme des deux précédents : F(0)=0, F(1)=1, et pour n>1, F(n) = F(n-1) + F(n-2). C'est une définition doublement récursive.
def fibonacci(n):
# Cas de base
if n == 0:
return 0
elif n == 1:
return 1
# Appels récursifs (deux cette fois !)
else:
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(7)) # Affiche 13
Attention ! Cette version, bien que très élégante, est très inefficace pour des valeurs de n un peu grandes car elle recalcule un nombre astronomique de fois les mêmes valeurs. C'est un excellent exemple des pièges de la récursivité naïve.
Récursivité terminale : l'optimisation essentielle
Regarde à nouveau la fonction factorielle. Après l'appel récursif factorielle(n-1), l'ordinateur doit encore faire la multiplication n * .... Il doit donc garder en mémoire (dans la « pile d'appels ») la valeur de n en attendant le résultat de l'appel. Cela consomme de la mémoire.
La récursivité terminale est une technique où l'appel récursif est la dernière opération de la fonction, et où on transmet le résultat partiel en cours de calcul via un paramètre supplémentaire, appelé accumulateur.
def factorielle_terminale(n, acc=1):
# Cas de base : on renvoie l'accumulateur
if n == 0:
return acc
# Appel récursif TERMINAL : plus de calcul après.
# Le résultat partiel (n * acc) est passé au prochain appel.
else:
return factorielle_terminale(n-1, n * acc)
print(factorielle_terminale(5)) # Affiche 120
Pourquoi c'est mieux ? En théorie, un compilateur/ interpréteur optimisé pourrait transformer cette récursivité terminale en une simple boucle (optimisation Tail Call Recursion), évitant de saturer la pile mémoire. Note : Python n'effectue pas cette optimisation, mais c'est une bonne pratique conceptuelle à connaître et à utiliser, car elle clarifie souvent le raisonnement.
Quand utiliser (ou éviter) la récursivité ?
La récursivité est un outil formidable, mais pas une solution universelle.
À privilégier quand :
- Le problème a une définition naturelle récursive (comme les parcours d'arbres, les tours de Hanoï, le tri fusion).
- Les structures de données sont récursives (listes chaînées, arbres, graphes).
- La lisibilité et l'élégance du code sont prioritaires pour un problème de taille maîtrisée.
À éviter quand :
- La profondeur de récursion risque d'être très grande (proche de la limite de la pile Python, ~1000 par défaut).
- La solution itérative (avec une boucle) est simple, évidente et plus performante en mémoire (comme pour Fibonacci simple).
- Les calculs sont redondants (comme dans Fibonacci naïve). Dans ce cas, on peut envisager la récursivité avec mémoïsation (mémoriser les résultats déjà calculés).
En résumé, la récursivité est une façon de penser plus qu'une simple technique de codage. Elle te force à décomposer un problème et à identifier ses cas les plus simples. Maîtrise-la, et tu auras une longueur d'avance en NSI et au-delà !
