Dans cet article, nous allons essayer de comprendre un concept très important en programmation : la récursivité.

Nous donnerons d'abord une définition de la récursivité (en programmation), puis nous verrons comment elle fonctionne, étudierons quelques fonctions récursives et tenterons de comprendre ce qui se passe dans la pile.

In order to understand recursion, one must first understand recursion.

Qu'est-ce que la récursivité (en informatique) ?

On pourrait définir la récursivité comme une méthode de résolution d'un problème où sa solution dépend des solutions d'instances plus petites du même problème. Pour simplifier, une fonction récursive est une fonction qui s'appelle elle-même. Les problèmes qui utilisent la récursivité peuvent généralement être résolus par itération (avec des boucles par exemple), mais nous devons identifier les instances plus petites pour utiliser cette méthode.

Voici un exemple très simple d'une fonction récursive qui imprime une chaîne de caractères :

En prenant "hello" comme str, nous obtiendrions hello, suivi d'un retour à la ligne comme sortie. Ici, nous pouvons voir que la fonction print_string s'appelle elle-même, donc nous avons bien une fonction récursive.

Comme mentionné précédemment, un problème qui utilise la récursion peut également être résolu par itération, comme montré ci-dessous :

Si nous exécutons ce programme, nous obtiendrons la même sortie (hello).

Bien, maintenant que nous avons quelques notions sur la récursivité, voyons comment elle fonctionne...

Comment fonctionne la récursivité ?

Lorsqu'on écrit une fonction récursive, nous devons faire attention aux boucles infinies. Celles-ci se produisent lorsque la fonction ne cesse jamais de s'appeler elle-même et peuvent causer une erreur appelée débordement de pile (nous verrons la notion de pile plus tard). Pour éviter cela, il faut définir une condition d'arrêt.

Avec une condition d'arrêt, nous pouvons identifier deux parties dans notre fonction récursive : le cas récursif et le cas de base. Le cas récursif est lorsque la fonction s'appelle elle-même (les arguments changent généralement à chaque appel) et le cas de base est lorsqu'elle cesse de s'appeler elle-même.

Illustrons cela... Nous prendrons comme exemple une fonction qui affiche les nombres à partir de n :

Exécuter ce programme donne la sortie suivante :

Nous pouvons constater qu'un débordement de pile s'est produit car nous n'avions pas de cas de base. La fonction s'appelle elle-même et prend comme argument n + 1 mais elle ne sait pas quand arrêter de s'appeler elle-même !

Ajoutons un cas de base : lorsque n est égal à 15 :

Maintenant nous obtenons :

Nous pouvons voir, grâce à cet exemple, que le cas de base est très important lors de la création d'une fonction récursive. Voici une petite représentation de cette fonction :

D'accord, nous avons maintenant une meilleure idée de ce qu'est la récursivité en programmation, mais il serait préférable d'approfondir le sujet...

Que se passe-t-il dans la pile lors de l'utilisation de fonctions récursives ?

Dans cette partie, nous allons essayer de voir ce qui se passe dans la pile lorsque nous utilisons une fonction récursive. Pour ce faire, nous prendrons comme exemple la fonction récursive _pow_recursion définie ci-dessous, qui renvoie l'opération puissance entre deux nombres flottants x et y :

(Nous pouvons noter que nous avons identifié le cas de base et les cas récursifs)

Tout d'abord, définissons la pile. Cette notion est très importante car les fonctions récursives utilisent la pile pour résoudre des problèmes. En fait, une pile est une structure de données linéaire qui suit un ordre particulier dans lequel les opérations sont effectuées. Cet ordre est LIFO, qui signifie Last In First Out (ou FILO qui signifie First In Last Out) et les principales opérations que nous pouvons effectuer sur une pile sont push (ajouter un élément au sommet de la pile) et pop (retirer l'élément au sommet de la pile).

Si nous parlons de pile, c'est parce que, comme mentionné précédemment, les fonctions récursives utilisent la pile pour résoudre des problèmes. Nous appelons généralement cela la "pile d'appels". Cette notion vous donnera une vision plus claire de la récursion. Pour simplifier, chaque fois qu'une fonction (ici, _pow_recursion) est appelée, cette fonction va au sommet de la pile, de sorte que la première fonction appelée sera la dernière à être exécutée.

Expliquons cela avec quelques schémas, en utilisant la fonction _pow_recursion comme exemple...

Pour le premier exemple, nous initialisons x à 3 et y à 3. Notre pile ressemble à ceci :

Maintenant notre fonction va s'appeler elle-même avec x égal à 3 et y égal à y-1 jusqu'à ce qu'elle atteigne le cas de base (y égal à 0). Chaque sous-fonction sera au sommet de la pile :

Ok, donc maintenant que nous avons atteint le cas de base (y égal à 0), nous avons une valeur de retour, qui est 1. Avec cette valeur, nous pouvons obtenir la valeur de retour de _pow_recursion(3, 1) et ainsi de suite...

Voici donc la représentation finale du fonctionnement de cette fonction :

N'oubliez pas de commencer par la partie "ajout à la pile", en bleu, et de terminer par la partie "retour de la valeur", en rouge.

D'accord, c'est mieux maintenant, mais... que se passe-t-il si y est égal à -2 ? (par exemple).

C'est une bonne question que nous allons traiter tout de suite :

Pour ce faire, nous allons procéder de la même manière mais nous allons changer x et y. Cette fois-ci, nous appellerons la sous-fonction avec x égal à 4 et y = y + 1 :

Prenons _pow_recursion(4, -2) comme exemple :

Conclusion

Même si la récursion peut être difficile à lire et à comprendre et peut parfois nécessiter beaucoup d'espace mémoire, elle reste un outil puissant. De plus, elle permet d'écrire des programmes plus propres et plus efficaces car elle permet parfois de réduire la complexité temporelle de l'algorithme. C'est le cas par exemple avec les algorithmes de tri comme le tri rapide, le tri par tas et le tri bitonique.

Maintenant, le principal conseil que je peux vous donner est de vous entraîner et d'écrire beaucoup de fonctions récursives pour devenir un pro !