Une fonction est dite récursive lorsqu'elle s'appelle elle-même. Bien entendu pour ne pas qu'elle s'appelle indéfiniment il faut construire une condition d'arrêt sinon le programme va boucler.
Si l'on reprend l'exemple précédent :
factorielle(n)=n*factorielle(n-1) <-- appel recursif
factorielle(0)=1 <-- condition d'arrêt
Il ne faut pas abuser de la récursivité en programmation car outre le fait que c'est souvent moins lisible qu'une bonne vielle boucle itérative, le volume occupé en mémoire de la pile des appels récursifs à une forte tendance à gonfler. En effet pour calculer factorielle(3) :
factorielle(3)=3*factorielle(2)
factorielle(2)=2*factorielle(1)
factorielle(1)=1*factorielle(0)
factorielle(1)=1*1 <-- condition d'arret
Comme on connait factorielle 0 on peut remonter la pile des appels
factorielle(1)=1
factorielle(2)=2*1=2
factorielle(3)=3*2=6
On a dû mémoriser la suite d'appel ce qui est mauvais car ici on pouvait mieux faire :
int i,fact=1;
for(i=1;i<=n;++i){
fact=fact*i;
// la seule chose utilisée pour le calcul est le résultat intermediaire (valeur fact)
}
return fact;
La récursivité est employé dans certains cas bien précis : l'exploration d'un arbre (par exemple dans un branch and bound) est sans doute l'exemple le plus représentatif.
Bonne chance
