Les fonctions
Partie 4 sur 6
7La récursivité
Une fonction peut faire appel à elle-même : on parle de fonction récursive. Une mise en garde s’impose : il ne faut pas oublier de mettre une condition de sortie, au risque sinon de ne pas pouvoir arrêter le programme. C’est le principe de la poupée russe : pour ouvrir la poupée, on ouvre la poupée à l’intérieur, jusqu’à la plus petite, qui ne contient plus rien.
L’exemple classique est la factorielle : n! est le produit de tous les entiers de 1 à n (4! = 4 × 3 × 2 × 1 = 24). On la définit ainsi : la factorielle de 1 vaut 1 (c’est le cas de base, la condition de sortie), et la factorielle de n vaut n fois la factorielle de n − 1.
def factorielle(n):
if n <= 1:
return 1 # cas de base : on s'arrête
return n * factorielle(n - 1) # appel récursif sur un problème plus petit
factorielle(4) # 24
7.1La pile d’appels
Comment le système s’y retrouve-t-il ? À chaque appel, il réserve un petit espace en mémoire, appelé cadre, qui contient les paramètres et les variables locales de cet appel, ainsi que l’endroit où revenir. Les cadres s’empilent comme des assiettes : le dernier arrivé est le premier servi. On parle de pile d’appels (voir la mémoire vive). Dans la figure 3, quatre cadres sont empilés avant que le dernier ne rende sa valeur. Chaque appel récursif a ses propres variables : le n de factorielle(3) n’a rien à voir avec celui de factorielle(4). La pile a une taille limitée : si les appels ne s’arrêtent jamais (cas de base oublié ou jamais atteint), elle déborde et le programme s’interrompt avec une erreur de « dépassement de pile » (stack overflow, le nom du célèbre site d’entraide entre programmeurs).
7.2Quand l’utiliser
La récursivité s’impose quand le problème a lui-même une structure en poupées russes. Un cas typique est le parcours d’une arborescence : les fonctions récursives sont indispensables pour parcourir une arborescence, par exemple lister tous les fichiers d’un dossier, y compris ceux de ses sous-dossiers, de leurs sous-dossiers, et ainsi de suite. La fonction liste le contenu du dossier ; pour chaque sous-dossier rencontré, elle s’appelle elle-même.
def lister(dossier):
for element in contenu(dossier):
if est_un_dossier(element):
lister(element) # même travail, un niveau plus bas
else:
print(element)
Elle sert aussi pour les structures arborescentes (une page Web dont les balises contiennent d’autres balises, voir HTML), les algorithmes « diviser pour régner » (recherche dichotomique, tri rapide, voir l’algorithmique) et les parcours de graphes. Pour les problèmes qui se prêtent à une simple répétition (additionner les éléments d’une liste), une boucle est plus claire et plus économe en mémoire. Quelques langages (Scheme, Haskell…) optimisent les appels récursifs terminaux pour qu’ils n’empilent rien ; ce n’est pas le cas de Python, ni de la plupart des autres : la profondeur reste limitée (environ mille appels par défaut en Python).
Pour s’exercer
Exercice 4 : une fonction récursive
Écrivez une fonction récursive somme(n) qui renvoie 1 + 2 + … + n. Identifiez le cas de base. Que se passe-t-il pour somme(3) ?
Voir la réponse
def somme(n):
if n == 0:
return 0 # cas de base
return n + somme(n - 1)
somme(3) = 3 + somme(2) = 3 + (2 + somme(1)) = 3 + (2 + (1 + somme(0))) = 3 + 2 + 1 + 0 = 6. Sans le cas n == 0, les appels descendraient vers les nombres négatifs sans jamais s’arrêter, jusqu’au dépassement de la pile.
Exercice 5 : choisir passage par valeur ou par référence
Une fonction doit échanger les valeurs de deux variables a et b. Pourquoi un passage par valeur ne suffit-il pas ? Que faire en PHP ?
Voir la réponse
Avec un passage par valeur, la fonction reçoit des copies : elle échange les copies, et les variables d’origine ne bougent pas. Il faut passer les références : en PHP, function echanger(&$x, &$y) { $t = $x; $x = $y; $y = $t; }. Dans beaucoup de langages, on préfère une fonction qui renvoie le couple échangé : a, b = b, a en Python.
8Surcharge, signature et fonctions « en ligne »
8.1La surcharge
Un des apports les plus intéressants du C++ par rapport au C, hormis le concept objet, est la possibilité d’appeler plusieurs fonctions avec le même nom, pourvu que leurs arguments diffèrent, en type, en nombre ou en les deux. Ce principe est la surcharge de fonction (overloading). Java l’offre de même pour les méthodes (on parle de « surcharge de méthode »). Elle simplifie l’écriture de fonctions qui font la même chose sur des données de types différents : une fonction afficher pour un entier, une autre pour un texte, une autre pour un décimal, sans avoir à inventer trois noms.
Comment le compilateur choisit-il laquelle exécuter ? Une fonction est déterminée par ce que l’on appelle sa signature, c’est-à-dire son nom, le nombre et le type de ses arguments (et, en Java, pas son type de retour : deux méthodes qui ne diffèrent que par le type de retour sont refusées). À l’appel, il compare les arguments fournis aux signatures disponibles et retient celle qui correspond.
// Java : trois méthodes, un seul nom
static int doubler(int n) { return n * 2; }
static double doubler(double x) { return x * 2.0; }
static String doubler(String s) { return s + s; }
doubler(4); // 8
doubler(2.5); // 5.0
doubler("ab"); // "abab"
Les langages sans types obligatoires (Python, JavaScript, PHP) n’ont pas de surcharge : une fonction par nom. On y obtient un effet voisin par les valeurs par défaut, les arguments nommés ou un test sur le type reçu dans la fonction. Rust et Go n’ont pas non plus de surcharge classique ; ils préfèrent des mécanismes de « généricité » (une fonction écrite une fois pour des types variés).
8.2La fonction « inline »
Le C++ introduit le concept de fonction inline (« en ligne ») en ajoutant le mot-clé inline : le compilateur est invité à insérer le corps de la fonction à l’endroit de l’appel, comme si on l’avait recopié, au lieu de faire un véritable appel. Ces fonctions sont évaluées à la compilation et leur appel ne coûte rien à l’exécution. Ce concept de pseudo-fonction existait déjà en C grâce à la directive de préprocesseur #define, mais celle-ci ne permettait aucun contrôle de type, ce que le mot-clé inline corrige.
#define CARRE(x) x * x /* C ancien : une substitution de texte, sans contrôle */
inline int carre(int x) { return x * x; } /* C++ : une vraie fonction */
L’écart n’est pas qu’une question de type : la macro CARRE(a + 1) devient a + 1 * a + 1, qui ne calcule pas le carré de a + 1 (le texte a été recopié sans parenthèses). C’est une source classique d’erreurs, et l’une des raisons pour lesquelles on évite les macros pour ce genre d’usage. Précision moderne : le mot inline est aujourd’hui une suggestion ; les compilateurs actuels décident eux-mêmes ce qu’il vaut la peine d’insérer, avec ou sans le mot.
Pour s’exercer
Exercice 6 : la surcharge
En Java, on définit int calculer(int a), int calculer(int a, int b) et double calculer(int a). Laquelle de ces trois définitions est refusée, et pourquoi ?
Voir la réponse
La troisième. Elle a la même signature que la première (nom calculer, un argument entier) et ne se distingue que par le type de retour, qui ne fait pas partie de la signature. Le compilateur ne saurait pas laquelle appeler pour calculer(5). La deuxième est acceptée : elle a deux arguments.