[FAQ][Algo] - Récursivité
Voici un petit mot sur la récursivité qui pourrait être pratique autant dans une FAQ traitant les algos.
Je ne sais pas si le sujet est déjà abordé dans une autre FAQ mais bon, ca ne coûte pas grand chose de contribuer de toute façon!
Qu'est-ce que la récursivité?
La récursivité est le principe selon lequel une fonction s'appelle elle-même, en boucle, jusqu'à ce qu'une (ou plusieurs) conditions d'arrêt soient respectées.
Elle repose principalement sur les 3 points suivant
- L'expression récursive (auto-appeler la fonction)
- La condition d'arrêt (quand arrête-t-on de boucler?)
- La convergence (ce qui nous amène vers la condition d'arrêt)
Voici un exemple simplet et concret.
Supposons que l'on veut calculer le factorielle d'un nombre positif n (par exemple: le factoriel de 6 est 6*5*4*3*2*1 = 720).
La fonction récursive pourrait ressembler à quelque chose du genre, dans une notation C:
Code:
1
2
3
4
5
| long factorielle(unsigned int n)
{
if (n == 1 || n == 0) return 1l;
return ((long) n * factoriel(n-1));
} |
La condition d'arrêt dans l'exemple ci-haut est (n == 1 OU n == 0)
L'expression récursive est le deuxième return, soit return (n * factoriel(n-1));
La convergence est donc intégré à l'expression récursive dans ce cas-ci (et c'est souvent le cas)
Ainsi, on bouclera les appels à factorielle(int) jusqu'à temps que le nombre passé en paramètre soit 1.
Voila une façon simple et efficace de calculer le factorielle d'un nombre positif en utilisant la récursivité. Imaginez maintenant tout ce que l'on peut faire avec la récursivité ;)
J'espère que ca sera utile à quelqu'un!
EDIT: FAQ algos et non C/C++ ;)
