Introduction aux fonctions récursives

Dans la programmation en général, il arrive très souvent que l’on doive utiliser des boucles (qu’elles soient de type while ou de type for). Cependant, on a parfois besoin de répéter certaines actions qui nécessitent des boucles plus complexes, plus lourdes et c’est dans ces cas-là qu’il est utile de connaître un type de fonctions assez important : les fonctions récursives.

Quelle utilité ?

Avant de voir comment créer de telles fonctions, il est important de se poser la question de l’utilité. La première fois que l’on voit les fonctions récursives, il arrive que l’on se dise en effet que ça ne sert à rien et pourtant, les fonctions récursives sont indispensables si vous souhaitez dessiner des fractales par exemple et ouvrent d’autres voies pour effectuer d’autres actions, en remplacement des boucles. De plus, dans certains langages comme le Scheme, les boucles n’existent pas et il faut nécessairement les remplacer par des fonctions récursives.

En quoi ça consiste ?

Une fonction récursive est une fonction qui s’appelle elle-même, tout simplement. Il existe bien sûr d’autres types de récursivité avec par exemple une fonction f() qui appelle une fonction g() qui appelle elle-même la fonction f() etc.. Vous vous en doutez : vu comme ça, le processus se répétera à l’infini (enfin jusqu’à la fin du monde qui entraînera la destruction de l’ordinateur faisant tourner votre programme) et il nous faudra donc utiliser une condition d’arrêt.

Récursivité simple

Une fois ces bases vues, il devient nécessaire de voir un exemple afin de bien comprendre le concept et de voir comment ça marche. Cet exemple concerne la factorielle. Pour ceux qui ne connaissent pas, la factorielle est une fonction mathématique utilisée avec les nombres naturels (les entiers positifs). La factorielle d’un nombre entier naturel n nous donne en fait le produit de tous les entiers naturels non nuls inférieurs ou égaux à n et elle se note n! (par exemple 3! = 3 * 2 * 1 = 6, 4! = 4 * 3 * 2 * 1 = 24 ou encore 5! = 5 * 4 * 3 * 2 * 1 = 120 et, par convention 0! = 1).

Programmer une telle fonction peut se faire de plusieurs façons différentes : nous pouvons utiliser les deux types de boucles. Voici par exemple la fonction factorielle écrite avec une boucle de type for :

fonction factorielle(n) {
	fact = 1;
	
	pour (i de 1 à n)
		fact *= i;
	
	retourner fact;
}

Rien de bien compliqué, vous devriez comprendre sans soucis ce bout de pseudo-code. Pour apprendre quelques trucs (parce que c’est quand même le but de cet article), voici donc la même fonction utilisant la récursivité :

fonction factorielle(n) {
	si (n == 0)
		retourner 1;
	
	retourner n * factorielle(n - 1);
}

Là, c’est tout de suite moins classique si on ne connaît pas la récursivité, mais pas d’inquiétudes puisque nous allons voir dès maintenant les explications liées à ce code. La condition au début de notre fonction est notre condition d’arrêt : si le nombre dont on veut la factorielle est égal à 0, alors on retourne 1 (puisque 0! = 1). Si la condition est respectée, la suite de la fonction n’est pas exécutée (puisque une fonction s’arrête lorsqu’elle retourne une valeur), inutile donc d’ajouter un sinon.

Mais que se passe-t-il si la condition d’arrêt n’est pas respectée ? Toute la subtilité de la récursivité est là. En réalité, la façon de procéder est légèrement différente de celle utilisée dans la boucle au-dessus : au lieu d’aller de 1 à n, nous allons de n à 1 (mais le résultat est le même évidemment). Nous retournons une valeur, ça c’est facile à comprendre, mais que retournons-nous ? Il s’agit de n multiplié par le résultat de la factorielle de (n – 1). Et justement, toute la magie est là : factorielle(n – 1) retournera soit 1 si n – 1 = 0, soit (n – 1) * factorielle(n – 2).

Pour bien comprendre, imaginons un exemple : si n vaut 3, factorielle(3) retournera 3 * factorielle(2). Or, factorielle(2) retourne 2 * factorielle(1) et factorielle(1) retourne 1 * factorielle(0) tandis que factorielle(0) retourne 1. Au final, nous nous retrouverons donc avec 3 * 2 * 1 * 1. Notez que ce double « * 1 » peut être évité en modifiant notre condition d’arrêt : au lieu de retourner 1 si n vaut 0, on peut le retourner si n est inférieur ou égal à 1. Ainsi, si n est supérieur ou égal à 2, la récursivité s’arrête à n = 1 et le cas n = 0 est bel et bien traité. Attention cependant : le cas n négatif ou différent d’un entier n’est pas traité, mais ce n’est pas le but ici.

Autres récursivités

La récursivité simple est probablement la plus utilisée mais si vous avez besoin d’autres types, sachez que ce n’est pas plus compliqué. Par exemple, une récursivité double donnerait ça :

fonction f(argument) {
	si (condition)
		retourner constante;
	
	retourner g(argument_modifie);
}

fonction g(argument) {
	si (condition)
		retourner constante;
	
	retourner f(argument_modifie);
}

Ce n’est qu’un exemple, bien sûr mais comme vous pouvez le voir, ce n’est pas plus compliqué que la récursivité simple. Vous pouvez bien sûr adapter tout ça pour utiliser 3, 4 ou même plus de fonctions.