Programmer par récursivité

Une définition récursive relie un problème à une ou plusieurs instances du même problème. Elle comprend des cas de base, traités directement, et une règle de réduction. Le cas de base ne signifie pas que tout le programme disparaît : il produit une valeur qui permet aux appels en attente de poursuivre leur calcul. Chaque appel possède ses propres paramètres et ses propres variables locales.

Prenons la somme des entiers de 1 à n, pour n entier naturel. La somme vide, obtenue pour n égal à zéro, vaut zéro. Pour n strictement positif, on ajoute n à la somme jusqu’à n − 1. Le contrat précise l’entrée et la sortie ; il donne aussi la précondition n ≥ 0. Une fonction correcte pour les naturels ne devient pas automatiquement correcte pour un entier négatif.

Pour écrire Python, conserve les deux-points et l’indentation. La première ligne définit la fonction ; le premier return se trouve dans le bloc conditionnel. Le dernier return est aligné avec if, à l’intérieur de la fonction.

Python
def somme(n):
  if n == 0:
    return 0
  return n + somme(n - 1)

Pour prouver l’arrêt, cherche une quantité entière naturelle qui diminue strictement à chaque appel récursif. On l’appelle un variant. Pour somme, cette quantité est n. Si n est positif, n − 1 est encore naturel et strictement inférieur à n ; on atteint donc zéro après un nombre fini de réductions. La présence d’un if n’est pas, à elle seule, une preuve de terminaison : il faut montrer que sa branche terminale sera atteinte.

Avec une entrée négative, le même programme s’éloigne de zéro. Le contrat exclut cette entrée ; on peut aussi ajouter une vérification explicite au début du programme. Remplacer le test n == 0 par n <= 0 change le comportement sur les négatifs, mais ce choix doit être cohérent avec la spécification. Un correctif ne se choisit pas seulement parce qu’il fait disparaître une erreur observée.

La correction est une autre question : la fonction peut terminer et renvoyer une valeur fausse. Pour somme, le cas zéro est correct. Si l’appel plus petit calcule correctement la somme jusqu’à n − 1, l’ajout de n donne exactement la somme jusqu’à n. Ce raisonnement associe une base et une étape de transmission. Il ne faut pas supposer directement que l’appel initial est correct.

Un palindrome est une chaîne qui se lit de la même façon dans les deux sens. Nous comparons ici les caractères exactement, sans ignorer accents, espaces ou majuscules. La chaîne vide et une chaîne d’une lettre sont des palindromes. Pour une chaîne plus longue, il faut que les deux caractères extrêmes soient égaux et que la chaîne intérieure soit elle-même un palindrome.

La réduction porte cette fois sur la longueur, qui baisse de deux. Le test de longueur doit précéder l’accès au premier ou au dernier caractère : l’indice zéro n’existe pas dans une chaîne vide. L’opérateur and évalue son second opérande seulement si le premier est vrai ; des extrémités différentes suffisent donc à renvoyer False sans explorer le centre.

Python
def palindrome(texte):
  if len(texte) <= 1:
    return True
  return (
    texte[0] == texte[-1]
    and palindrome(texte[1:-1])
  )

Pour somme(n), les arguments n, n − 1, …, 0 produisent n + 1 appels. Dans un modèle où une addition coûte une unité, le temps est linéaire en n. Les additions sur de très grands entiers ont un coût propre, laissé de côté dans ce modèle. La profondeur des appels est également linéaire ; Python conserve les contextes des appels en attente dans une pile.

Une boucle peut calculer la même somme avec un accumulateur initialisé à zéro, puis ajouter successivement les entiers de 1 à n inclus. Elle effectue n additions, mais n’accumule pas n contextes de fonction. Elle utilise un nombre constant de variables dans ce modèle. La récursivité n’est donc pas automatiquement plus rapide ; elle exprime surtout une décomposition du problème.

Attention aux sous-problèmes répétés. Dans une définition naïve de Fibonacci, calculer deux appels récursifs peut recalculer plusieurs fois les mêmes valeurs. Le nombre d’appels peut alors croître bien plus vite que la profondeur. Un dessin des appels permet de repérer cette répétition. La programmation dynamique traitera d’autres façons de conserver des résultats déjà obtenus ; elle n’est pas nécessaire pour comprendre la présente leçon.

Pour palindrome, retirer une tranche construit de nouvelles chaînes en Python. La profondeur est proportionnelle à la longueur dans le pire cas, mais on ne doit pas en déduire un temps linéaire sans compter ces copies. Une version utilisant deux indices peut éviter ces tranches ; comparer les algorithmes impose de préciser les opérations réellement effectuées.

Ne pas écrire return devant un appel peut faire perdre sa valeur : appeler une fonction et renvoyer son résultat sont deux actions différentes. De même, print affiche une information mais ne remplace pas return. Une fonction qui atteint la fin sans return explicite renvoie None, ce qui risque de rendre une addition impossible.

Récursivité et boucle peuvent coexister : ce mélange n’est pas une erreur en soi. Il faut examiner ce que la boucle répète et ce que chaque appel réduit. Enfin, une terminaison mathématique ne promet pas que toute entrée tiendra dans la mémoire et le temps disponibles. La profondeur limitée de Python est une contrainte d’exécution distincte de la validité de la définition.