Qu’est-ce qu’un cas de base dans une fonction récursive ?

Réponse courte

Le cas de base est une situation où une fonction récursive calcule directement son résultat sans effectuer de nouvel appel récursif.

Comprendre

Le point d’arrêt des appels

Une fonction récursive se rappelle pour résoudre une instance plus petite du même problème. Le cas de base décrit une entrée simple dont le résultat est connu directement. Sans cas de base atteint par les appels, les appels continuent et la fonction ne fournit pas normalement de réponse.

Exemple avec une somme

Pour calculer la somme des entiers de 1 à n, on peut définir somme(0)=0. Pour n positif, somme(n) renvoie n + somme(n−1). L’appel somme(3) conduit à somme(2), puis somme(1), puis somme(0). Ce dernier appel renvoie 0 sans s’appeler lui-même ; les appels en attente peuvent alors calculer successivement 1, 3 et 6.

Un cas de base ne suffit pas à prouver l’arrêt : il faut aussi vérifier que, pour toutes les entrées du domaine annoncé, la réduction rapproche effectivement les appels de cette base. Ici, l’entrée doit être un entier naturel. Avec un entier négatif, retrancher 1 ne mènerait jamais à zéro. Une fonction récursive bien conçue précise donc son domaine, son ou ses cas de base et la réduction utilisée pour les autres cas.

Exemples

  • Pour somme(n), somme(0) renvoie 0 directement et constitue le cas de base.
  • Pour palindrome(texte), une chaîne de longueur 0 ou 1 renvoie True sans appel sur une chaîne plus petite.
  • Si une fonction pair(n) retire 2, elle doit traiter directement 0 et 1 ; ces deux bases couvrent les naturels pairs et impairs.

Pièges fréquents

  • Croire que la présence d’un cas de base garantit à elle seule la terminaison : il faut montrer que les appels y arrivent.
  • Oublier une base nécessaire : une fonction qui retire 2 sur les naturels doit traiter aussi le cas 1, pas seulement 0.

Et maintenant ?

Questions proches

← Toutes les questions-réponses