Voir version :
Pas de dépendances
Télécharger : 
#include <stdio.h> int factorielle(int n) { if (n<=1) return 1; return n*factorielle(n-1); } int main() { printf("Facorielle de 5 = %d\n",factorielle(5)); return 0; }
La récursivité est quelque chose de dur a comprendre.
Déja, mathématiquement :
on appelle factorielle de N et on note N! le nombre entier tel que :
N! = N*(N-1)*(N-2)* ... *1
(on multiplie tous les nombres d'avant entre eux...)
Donc pour l'exemple :
5! = 5 * 4 * 3 * 2 * 1 = 120
c'est bien ce que nous donne le programme...
Mais comment marche cette fonction ?
Il faut savoir que pour boucler, on a 2 modes possibles :
- le mode itératif (avec for ou while)
- le mode récursif (celui étudié ici)
Avec le mode itératif, on aurait pu écrire la fonction factorielle ainsi :
int factorielle(int n)
{
int resultat=1;
int i;
for(i=1;i<=n;i++)
resultat*=i;
return resultat;
}
Ce serait revenu au meme...
Mais une fonction récursive a cette propriété de s'appeler elle meme...
Alors étudions :
On envoie 5 a la fonction :
est ce que n <= 1 ?
NON.
donc on rend 5*factorielle(4)
or qu'est ce que factorielle de 4 ?
On relance la fonction :
On envoie 4 a la fonction :
est ce que n <= 1 ?
NON.
donc on rend 4*factorielle(3)
or qu'est ce que factorielle de 3 ?
On relance la fonction :
On envoie 3 a la fonction :
est ce que n <= 1 ?
NON.
donc on rend 3*factorielle(2)
or qu'est ce que factorielle de 2 ?
On relance la fonction :
On envoie 2 a la fonction :
est ce que n <= 1 ?
NON.
donc on rend 2*factorielle(1)
or qu'est ce que factorielle de 2 ?
On relance la fonction :
On envoie 1 a la fonction :
est ce que n <= 1 ?
OUI.
donc on rend 1
Donc si on remonte :
factorielle(2) = 2*factorielle(1) = 2*1 = 2
factorielle(3) = 3*factorielle(2) = 3*2 = 6
factorielle(4) = 4*factorielle(3) = 4*6 = 24
factorielle(5) = 5*factorielle(4) = 5*24 = 120
Ainsi renvoie factorielle de 5...
La récursivité est TOUJOURS définies par les 2 éléments suivant :
- Une condition d'arret : la résolution du probleme le plus simple.
- Un ou des appel(s) récursif(s) d'un probleme moins compliqué.
Si vous oubliez la condition d'arret, alors le programme bouclera infiniment.
En réalité, le programme doit se souvenir de "par ou il est passé" pour pouvoir remonter
Donc il stocke ce "chemin" dans sa pile (comme une pile de cartes)
Et chaque appel empile un nouveau "souvenir"
Si vous oubliez la condition d'arret, alors il empilera, encore et encore...
Et il va s'arreter : quand il n'aura plus de mémoire !! Ce sera l'erreur...
Cette erreur est courrament appelée "STACK OVERFLOW" --> Debordement de pile.
Donc les fonctions récusives doivent toujours respecter ce schéma.
Dans notre exmple :
- condition d'arret = si le nombre est 1 : la solution est évidente.
- appel récursif d'un probleme moins compliqué : la factorielle du nombre d'avant.
C'est quelque chose de dur a comprendre au début.
Utilités ?
Imaginez l'arborescence de votre disque dur.
Vous avez les fonctions suivantes :
Récuperer_la_liste_des_fichiers
Afficher_un_fichier
Récuperer_la_liste_des_dossiers
Acceder_a_un_dossier
Sortir_du_dossier_courant
Avec cela, faites moi un programme qui affiche tous les fichiers de votre disque dur...
N'oublions pas, qu'il peut y avoir des sous-sous-sous-...-sous répertoires :)
Essayez avec des for, sans récursivité : vous allez devenir fou...
(oui, on peut utiliser des piles ou des files, mais bon, C pas naturel...)
Avec la récursivité : (algorithme rapide pour comprendre, pas a compiler)
Parcours_arborescence(chemin)
{
Acceder_a_un_dossier(chemin)
Récuperer_la_liste_des_fichiers
Pour toute la liste :
Afficher_un_fichier // donc afficher les fichiers du repertoire courant
Récuperer_la_liste_des_dossiers
Pour toute la liste : // ne fera plus rien si la liste est vide : donc si on est dans un rep sans sous dossiers
Parcours_arborescence(chemin+nom_du_dossier)
Sortir_du_dossier_courant
}
Terminé !!!!!
et on l'appelle avec :
Parcours_arborescence("c:\");
Analyse :
- condition d'arret = si la liste des sous dossier générée par Récuperer_la_liste_des_dossiers est vide.
- appel récursif d'un probleme moins compliqué : Appel de Parcours_arborescence avec un sous dossier.
ça pourrait se résumer en français par :
"Analyse mon arbre avec le chemin C:\, affiche les fichier qui sont tout de suite la.
Puis ensuite, tu recommences avec chaque sous dossier, et ainsi de suite, jusqu'a ce que tu aies tout fait..."
Un autre exmple ?
La fonction "pot de peinture dans paint : qui peint des surfaces tordues :
avec un for : ouch !!!
Récursivement :
paint(x,y,blanc,bleu) // on veut colorier la zone blanche, et en bleu jusqu'a qu'on touche les frontieres (pot de peinture)
{
si (x,y) n'est pas blanc : STOP // condition d'arret
colorie (x,y) en bleu // rend le probleme moins compliqué : 1 pixel de moins a colorier.
paint(x+1,y)
paint(x-1,y)
paint(x,y+1) // recommence avec les 4 points voisins
paint(x,y-1)
}
Voila ! celui qui fait plus court avec un for, qu'il m'appelle :)
