Cours

La récursivité #

À la découverte de la récursivité #

Calcul d’une 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$ puisqu’il n’existe 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 n’est 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 n’ait 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 #

L’algorithme précédent utilise ce que l’on appelle le paradigme de programmation impérative: il est décrit par une séquence d’instructions qui décrivent précisément l’évolution des valeurs des variables, à l’aide de boucles et de conditionnelles.

C’est le paradigme de programmation le plus répandu, mais il en existe d’autres: la programmation fonctionnelle, comme son nom l’indique, 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 d’une puissance #

En programmation fonctionnelle, on utilise essentiellement (voire exclusivement) des fonctions. Idéalement, on essaye d’éviter au maximum l’utilisation 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 l’on peut totalement se passer d’une boucle (et donc aussi de la variable p de l’algorithme précédent) parce que chaque fonction utilise celle qui la précede (sauf lorsque l’exposat est nul, il faut bien démarrer quelque part…).

Cela résulte d’une 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 d’observer l’exécution de notre suite de fonctions à l’aide 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 qu’il y a un empilement d’exé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 d’obtenir 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 l’exposant 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 (c’est rarement le cas).

Et si une idée a priori fort simple permettait de s’affranchir de cette limitation ? Pourquoi ne pas inclure l’exposant 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 lorsqu’elle s’appelle 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 c’est bien le cas: l’exposant étant diminué d’une unité, le problème est un peu plus simple).

Observons ce que nous montre python tutor.

Bien qu’il n’y ait qu’une seule fonction, on constate un empilement d’environnement d’exécutions très similaire au précédent, à la différence qu’il s’agit toujours de la même fonction, mais avec des valeurs de paramètres différents (c’est finalement ce qui les distingue les uns des autres).

Anatomie d’une 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 d’arrêt, sinon l’algorithme bouclera indéfiniment.
  • Les valeurs passées en paramètres pour les appels récursifs doivent avoir des valeurs différentes, sinon la fonction s’exécutera toujours de manière identique et on aura encore une boucle infinie.
  • Après un nombre fini d’appels, la ou les valeurs passées en paramètres doivent correspondre aux conditions d’arrêt.
  • Le test de la ou les conditions d’arrêt doit être effectué avant l’appel 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 s’agir d’une 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 à l’avance. Dans d’autres situations, ce rôle peut aussi être tenu de manière implicite par la longueur d’une chaîne de caractères ou bien d’une 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, l’avant 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

L’implémentation en python n’est pas aussi simple (d’où l’intérêt parfois d’écrire un algorithme en pseudo-code plutôt qu’une implémentation directement), pour une raison technique bien connue: les chaînes de caractères sont immuables, il n’est donc pas possible d’en 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 #

L’algorithme récursif est comparativement bien plus simple et élégant. Le seul paramètre étant chaîne, c’est 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 d’arrêt ? On conviendra que le renversement d’une chaîne vide ou bien de longueur 1 est elle-même. On peut très bien choisir comme condition d’arrêt la chaîne vide, ou bien les deux conditions ensemble. Attention, il n’est 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 ? L’idée est de réaliser le nouvel appel sur la varialbe chaîne tronquée d’un caractère. On aura alors implicitement décrémenté la longueur de la chaîne de 1, ce qui nous amènera au bout d’un nombre fini d’étapes à une condition d’arrê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, c’est-à-dire la chaîne privée de son premier caractère.

En python, on peut implémenter l’algorithme 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é d’une exécution à l’aide 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 s’appellent 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 s’appellent chacune l’une l’autre: elles sont dites mutuellement récursives. Notons qu’il est nécessaire d’inclure une condition d’arrêt dans chacune d’entre elle, car chacune peut être appelée avec le nombre 0.

Lors de l’exécution avec python tutor, on constate qu’il y a alternance d’empilement d’environnements d’exécution pour chacune des deux fonctions dans la pile, jusqu’à atteindre le nombre 0 pour l’une des deux.