La récursivité


À la découverte de la récursivité

Calcul dune puissance

Spécification du problème

On souhaite écrire une fonction puissance(a, n) qui prend pour paramètres un nombre \(a\) et un entier naturel \(n\).

En mathématique, il existe plusieurs manières de définir une puissance de ce type. La plus simple, généralement donnée au niveau du collège, est:

\[ a^n = \underbrace{a\times a\times\cdots\times a}_{n\text{ fois}}\]

On a aussi la convention que \(a^0 = 1\) quelle que soit la valeur de \(a\), sauf lorsque \(a = 0\) puisquil nexiste pas de bonne manière de définir \(0^0\) en mathématiques.

Un premier algorithme

Cette définition suggère très naturellement un algorithme utilisant une boucle:

fonction puissance(a, n)
    p = 1
    pour i allant de 1 à n faire
      p ← p * a
    retourner la valeur de p

Assurons-nous que cet algorithme est correct: lorsque \(n = 0\), la boucle nest pas exécutée et la valeur retournée sera bien 1 (remarquons au passage que la fonction renvoie aussi 1 lorsque \(a = 0\), bien que cela nait aucun sens en mathématiques. Nous ne nous soucierons pas de ce point de détail ici).

Dès lors que \(n \geqslant 1\), la boucle sera exécutée exactement \(n\) fois, ce qui signifie que la valeur initiale \(p = 1\) sera multipliée exactement \(n\) fois par \(a\), donnant le résultat attendu.

En python, on peut implémenter cet algorithme de la manière suivante:

def puissance(a, n):
  p = 1.0
  for i in range(n):
    p = p * a

  return p

Paradigmes de programmation

Lalgorithme précédent utilise ce que lon appelle le paradigme de programmation impérative: il est décrit par une séquence dinstructions qui décrivent précisément lévolution des valeurs des variables, à laide de boucles et de conditionnelles.

Cest le paradigme de programmation le plus répandu, mais il en existe dautres: la programmation fonctionnelle, comme son nom lindique, utilise comme ingrédient principal les fonctions.

Un autre paradigme très à la mode est la programmation orientée objets. Nous létudierons plus tard cette année.

Le langage python est un langage multi-paradigme: il permet notamment décrire des programmes utilisant un ou plusieurs des trois paradigmes ci-dessus.

Nous allons à présent nous intéresser à une solution de notre problème de calcul de puissance en utilisant la programmation fonctionnelle.

Une approche fonctionnelle du calcul dune puissance

En programmation fonctionnelle, on utilise essentiellement (voire exclusivement) des fonctions. Idéalement, on essaye déviter au maximum lutilisation de boucles, voire même la modification des valeurs des variables.

Comment, avec de telles contraintes, calculer nos puissances ?

Une première approche pourrait ressembler à ceci:

def puissance_0(a):
  return 1.0

def puissance_1(a):
  return a*puissance_0(a)

def puissance_2(a):
  return a*puissance_1(a)

def puissance_3(a):
  return a*puissance_2(a)

def puissance_4(a):
  return a*puissance_3(a)

def puissance_5(a):
  return a*puissance_4(a)

...

Chaque fonction est dédiée à un exposant particulier. Le point important est que lon peut totalement se passer dune boucle (et donc aussi de la variable p de lalgorithme précédent) parce que chaque fonction utilise celle qui la précede (sauf lorsque lexposat est nul, il faut bien démarrer quelque part).

Cela résulte dune propriété mathématique bien connue:

\[ \begin{aligned} a^n & = \underbrace{a\times a\times\cdots\times a}\_{n\text{ fois}} \\\\ & = a\times \underbrace{a\times a\times\cdots\times a}\_{n - 1\text{ fois}} \\\\ & = a\times a^{n-1} \end{aligned}\]

Il est intéressant dobserver lexécution de notre suite de fonctions à laide de python tutor. On peut y observer que chaque fonction interrompt temporairement son exécution pour appeler celle qui la précède: on constate quil y a un empilement dexécutions de fonctions en attente. Celui-ci sera finalement dépilé dès que la première fonction aura renvoyé sa valeur, permettant de proche en proche dobtenir le résultat final.

Une première fonction récursive

Cette approche est parfaitement valable, mais elle comporte un défaut majeur absolument évident: il est nécessaire décrire autant de fonctions que lexposant maximal dont on aura besoin (ce qui est déjà problématique si celui-ci est très grand), si tant est que ce maximum soit connu (cest rarement le cas).

Et si une idée a priori fort simple permettait de saffranchir de cette limitation ? Pourquoi ne pas inclure lexposant faisant partie du nom de la fonction comme un second paramètre ? On obtiendrait alors ceci:

def puissance(a, n):
  if n == 0:
    return 1.0

  return a*puissance(a, n-1)

La fonction puissance est dite récursive: une fonction est récursive lorsquelle sappelle elle-même, idéalement avec des paramètres correspondant à un problème un peu plus simple que le précédent pour une raison que nous verrons très bientôt (ici cest bien le cas: lexposant étant diminué dune unité, le problème est un peu plus simple).

Observons ce que nous montre python tutor.

Bien quil ny ait quune seule fonction, on constate un empilement denvironnement dexécutions très similaire au précédent, à la différence quil sagit toujours de la même fonction, mais avec des valeurs de paramètres différents (cest finalement ce qui les distingue les uns des autres).

Anatomie dune fonction récursive

Quels sont les principes généraux régissant une fonction récursive ?

  • Une fonction récursive doit contenir une (ou plusieurs) conditions darrêt, sinon lalgorithme bouclera indéfiniment.
  • Les valeurs passées en paramètres pour les appels récursifs doivent avoir des valeurs différentes, sinon la fonction sexécutera toujours de manière identique et on aura encore une boucle infinie.
  • Après un nombre fini dappels, la ou les valeurs passées en paramètres doivent correspondre aux conditions darrêt.
  • Le test de la ou les conditions darrêt doit être effectué avant lappel récursif, sous peine là encore de boucler indéfiniment.

Généralement (mais pas toujours), on aura un des paramètres qui servira à satisfaire ces contraintes. Il peut sagir dune variable entière n qui sera décrémentée de 1 à chaque étape, pour finalement atteindre 0 ou toute autre borne inférieure fixée à lavance. Dans dautres situations, ce rôle peut aussi être tenu de manière implicite par la longueur dune chaîne de caractères ou bien dune liste par exemple.

On peut illustrer ce dernier point sur un exemple classique.

Récursivité et chaînes de caractères

On souhaite écrire une fonction renverse(chaîne) prenant pour paramètre une chaîne de caractères et renvoyant la même chaîne renversée (le dernier caractère devient le premier, lavant dernier le deuxième, etc).

Version impérative

Une version impérative de cet algorithme peut sécrire ainsi:

fonction renverse(chaîne):
    réponse est une copie de chaîne
    début = 0
    fin = longueur de la chaîne - 1
    Tant que début < fin faire:
        échanger les lettres d'indice début et fin dans réponse
        incrémenter début
        décrémenter fin
    retourner réponse

Limplémentation en python nest pas aussi simple (doù lintérêt parfois décrire un algorithme en pseudo-code plutôt quune implémentation directement), pour une raison technique bien connue: les chaînes de caractères sont immuables, il nest donc pas possible den modifier des caractères, et donc a fortiori de les échanger. Les listes permettent par contre de remplir ce rôle.

def renverse(chaîne):
  # On crée une liste (mutable) contenant tous les caractères 
  # de la chaîne.
  réponse = list(chaîne)

  début = 0
  fin = len(chaîne) - 1
  while début < fin:
    réponse[début], réponse[fin] = réponse[fin], réponse[début]
    début = début + 1
    fin = fin - 1

  # On recrée une chaîne à partir de réponse:
  return "".join(réponse)

Version récursive

Lalgorithme récursif est comparativement bien plus simple et élégant. Le seul paramètre étant chaîne, cest la longueur de cette chaîne de caractères qui jouera le rôle du paramètre décroissant satisfaisant aux conditions de la récursivité.

  • Quelles sont les conditions darrêt ? On conviendra que le renversement dune chaîne vide ou bien de longueur 1 est elle-même. On peut très bien choisir comme condition darrêt la chaîne vide, ou bien les deux conditions ensemble. Attention, il nest pas possible de choisir la chaîne de longueur 1 seule, car sinon on aurait une boucle infinie sur un appel avec une chaîne vide.
  • Comment décomposer le problème afin de réappeler la fonction sur un problème plus simple ? Lidée est de réaliser le nouvel appel sur la varialbe chaîne tronquée dun caractère. On aura alors implicitement décrémenté la longueur de la chaîne de 1, ce qui nous amènera au bout dun nombre fini détapes à une condition darrêt.
fonction renverse(chaîne):
    Si la longueur de la chaîne est inférieure ou égale à 1:
        retourner chaîne

    préfixe est le premier caractère de la chaîne
    suffixe est le reste de la chaîne

    appeler renverse sur suffixe, puis placer préfixe après le résultat
    retourner cette valeur

Nous avons besoin de deux ingrédients python essentiels pour réaliser cela:

  • chaîne[0] donne le premier caractère de la chaîne
  • chaîne[1:] donne tous les caractères à partir du deuxième, cest-à-dire la chaîne privée de son premier caractère.

En python, on peut implémenter lalgorithme précédent de manière extrêmement compacte:

def renverse(chaîne):
  if len(chaîne) <= 1:
    return chaîne

  return renverse(chaîne[1:]) + chaîne[0]

Il est comme toujours extrêmement instructif de regarder le déroulé dune exécution à laide de python tutor (attention, les accents ne sont pas acceptés dans la version de python utilisée sur ce site).

Fonctions mutuellement récursives

Dans certaines situations, on utilisera des fonctions qui, techniquement, ne sont pas récursives (elles ne sappellent pas elle-mêmes), mais constitueront néanmoins un algorithme récursif prises globalement.

Un exemple classique est le test de la parité:

def pair(n):
  if n == 0:
    return True

  if impair(n-1):
    return True
  else:
    return False

def impair(n):
  if n == 0:
    return False

  if pair(n-1):
    return True
  else:
    return False

Ces deux fonctions sappellent chacune lune lautre: elles sont dites mutuellement récursives. Notons quil est nécessaire dinclure une condition darrêt dans chacune dentre elle, car chacune peut être appelée avec le nombre 0.

Lors de lexécution avec python tutor, on constate quil y a alternance dempilement denvironnements dexécution pour chacune des deux fonctions dans la pile, jusquà atteindre le nombre 0 pour lune des deux.