Sommaire

Fonctions récursives

1. Qu’est-ce que la récursivité ?

Une notion est dite récursive lorsqu’elle se contient elle-même en partie ou si elle est partiellement définie à partir d’elle-même. La récursivité est appuyée sur le raisonnement par récurrence. Typiquement, il s’agit d’une suite dont le terme général s’exprime à partir de termes qui le précèdent. Par exemple, la factorielle d’un nombre N donné est le produit des nombres entiers inférieurs ou égaux à ce nombre N. Ceci est noté N! avec par définition la factorielle de 0 à 1, ce qui donne :

0! = 1

1! = 1

2! = 1*2

3! =1*2*3

(...)

N! = 1*2*3 ... *(N-1)*N

La notation générale est :

N! = 1 si N = 0

N! = N*(N-1)! si N > 0

et l’on voit que la factorielle de N est définie en fonction d’elle-même (N-1)!, c’est un processus récursif.

2. Une fonction récursive basique

Une fonction récursive est, en programmation, une fonction qui s’appelle elle-même. De ce fait un algorithme récursif va jouer sur les paramètres en entrée de la fonction qui seront modifiés à chaque nouvel appel de la fonction dans son propre corps. Par exemple, dans un tri au départ nous avons un ensemble D et la récursion s’exerce sur des sous-ensembles de D jusqu’à ce qu’il n’y ait plus de sous-ensemble ...