à l'aide de Grav par Pascal Grossé.
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.
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 pAssurons-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 pL’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.
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.
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).
Quels sont les principes généraux régissant une fonction récursive ?
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.
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).
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éponseL’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)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é.
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 valeurNous avons besoin de deux ingrédients python essentiels pour réaliser cela:
chaîne[0] donne le premier caractère de la chaînechaî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).
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 FalseCes 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.
à l'aide de Grav par Pascal Grossé.