Récursivité

La récursivité en informatique est un moyen simple et élégant de résoudre de nombreux problèmes qui est conceptuellement très proche de la notion de récursivité en mathématiques. Concrètement on dit qu'une fonction est récursive si elle s'appelle elle même.

Exemple simple

On cherche à calculer la valeur x^n (x à la puissance n) avec n un nombre entier. On peut remarquer que:

1. x^0 = 1
2. x^n = x * x^(n-1) , n>0

On sait calculer la puissance de x pour le cas simple n=0. Pour un cas complexe plus complexe (n>0) on sait se ramener à un cas plus simple. On peut donc calculer la puissance d'un nombre par récursivité:

int puissance(int x, int n)
{
if( n == 0 ) // cas simple
return 1;
else return x*puissance(x, n-1);
}