Récursivité
Récursivité
Récursivité
Récursivité
Décembre 2020
Licence 2 d’informatique
Exemple 1
On appelle fonction récursive toute fonction qui, dans sa définition, fait appel à
son propre identificateur. On peut ainsi définir la fonction somme comme suit :
0 si n = 0
somme(n) =
n + somme(n − 1) si n > 0
On pourrait donc décrire la fonction somme de la manière suivante :
0 si n = 0
multiplication(x , n) =
x + multiplication(x , n − 1) si n > 0
on aurait donc :
multi(4, 3) = 4 + multi(4, 3 − 1) = 4 + multi(4, 2)
= 4 + 4 + multi(4, 2 − 1) = 8 + multi(4, 1)
= 8 + 4 + multi(4, 1 − 1) = 12 + multi(4, 0)
= 12 + 0 = 12
Ce qu’on traduira en C par :
Ou encore
int pair ( int x ) int impair ( int x )
{ {
if ( x == 0) return 1; if ( x == 0) return 1;
else return impair ( x - 1); else return pair ( x - 1);
} }