Introduction :

J’ai remarqué qu’en cours d’informatique les étudiants avaient une sainte horreur des fonctions récursives et qu’ils trouvaient ça assez refoulant. Pourtant elles sont plus intéressantes à implémenter.

Définition :

Les algorithmes récursifs et les fonctions récursives sont fondamentaux en informatique. Un algorithme est dit RÉCURSIF s’il s’appelle lui-même. (merci Wiki) Tien ce truc me rappel un certain GNU (GNU is Not Unix) lol

Un simple exemple pour comprendre ce concept:

Imaginez une camera qui vous film par derrière et un téléviseur qui renvois les images de cette même camera.  Que remarquerez-vous? ben l’écran renvois l’image de vous même avec une télé devant vous qui renvois encore et toujours la même chose (à savoir vous et une télé)

Comment parvenir à implémenter une fonction récursive :

Rien de bien difficile, pour cela il suffit de suivre un certain raisonnement et le respect de quelques règles.

1- Déjà nous savon que la fonction récursive fait appel à elle-même.

2- Il nous faut une condition d’arrêt qui stoppera l’appel de la fonction à elle-même (généralement un cas particulier).

Rien ne vaut un petit exemple pour mieux comprendre :

Je cherche à calculer la somme d’une suite de 1 jusqu’à N. S=1+2+3+…+ (N-1) +N.

En temps normal vous aurez fait un truc qui ressemble a ça :

Int Somme(int N)

{ int I;

Int S=0;

For (i=0 ; i<=N ; i++)

S=S+i ;

Return S;

}

Désormais avec la récursivité vous ferez plutôt ça.

Int Somme (int N)

{

if (N==1) return 1

Else return Somme(N-1)+N //la fonction fait appel à elle-même avec un degré en moins

}

Quelques explications s’imposent :

La première ligne veut dire que si on cherche à calculer la somme de n=1 cela donnera 1 (logique non :-p) ceci représente le cas particulier.

Pour l’autre ligne la fonction retournera la somme des éléments précédent N et du coup cela fera appel a la même fonction mais avec n-1 puis avec n-2 puis n-3 ainsi de suite jusqu’à arriver à la condition d’arrêt (soit n=1).

C’est carrément magique .