Récursion
Dans tous les exemples qu'on a vu pour le moment, on a défini des fonctions, puis on les a appelées, que ce soit depuis une autre fonction ou en dehors de toute fonction. On peut également appeler une fonction depuis son propre corps. Une telle fonction, qui s'appelle elle-même, est appelée fonction récursive.
Commençons par voir un exemple pratique où une telle fonction peut s'avérer utile. Supposons que l'on veuille écrire une fonction permettant de calculer la somme $1 + 2 + ... + n$ pour un entier positif n donné. On pourrait utiliser une boucle while pour ce faire et écrire :
Cette fonction est tout à fait correcte et calcule la valeur qu'il faut. On peut également l'écrire différemment, à l'aide d'une fonction récursive, en se rendant compte de la propriété suivante :
$$\sum_{i = 1}^n i = \left( \sum_{i = 1}^{n - 1} i \right) + n,$$qui indique donc que la somme des $n$ premiers entiers positifs correspond à la somme des $n - 1$ premiers entiers positifs à qui on ajoute $n$. De plus, lorsque $n$ vaut 1, on obtient directement la valeur de la somme qui est $1$. Étant donné ces deux observations, on peut réécrire la fonction sum comme suit :
Une fonction récursive agit donc comme une boucle, puisqu'elle se rappelle elle-même un certain nombre de fois. Pour éviter une boucle infinie, il faut que dans un cas, appelé cas de base, la fonction ne se rappelle pas. Dans notre exemple, le cas de base se produit lorsque $n = 1$, et le cas récursif pour $n > 1$. La figure 3 montre l'enchainement des appels récursifs qui se produisent lorsqu'on exécute sum(3).
Les fonctions récursives peuvent parfois grandement améliorer la lisibilité du code, et sont parfois plus facile à concevoir lorsque le problème à résoudre s'y prête bien. Dès lors que la résolution d'un problème peut être faite en résolvant une version simplifiée du problème initial, il y a lieu de penser à la récursion.
Dans notre cas, la somme des $n$ premiers entiers positifs peut être connue en utilisant le résultat de la somme des $n - 1$ premiers nombres entiers, problème plus simple à résoudre.
Prenons un autre exemple, à savoir une fonction qui calcule rapidement la valeur de $a^n$. Pour cela, on va se baser sur les propriétés mathématiques suivantes :
$$a^n = \left\{ \begin{array}{ll} a & \textrm{si $n = 1$} \\ (a^2)^{n/2} & \textrm{si $n$ est pair} \\ a \cdot (a^2)^{(n - 1) / 2} & \textrm{si $n > 2$ et $n$ est impair} \end{array} \right.$$Cette méthode de calcul est appelée exponentiation rapide. Le premier cas correspond au cas de base, et les deux cas suivants sont des cas récursifs. Voici la fonction récursive pow qui traduit directement en code ces trois propriétés :