algorithme recursif Fermé

Question

Bonjour,
j'aimerai comprendre comment fonctione les algo recursif.ils sont trop abstrait pour moi.

scriptiz · Answer

Une méthode récursive fait appel à elle même.

Voici un exemple de méthode pour obtenir la factorielle d'un nombre de façon itérative puis récursive (la méthode s'appelle elle même).

// n >= 0
public static int factorielleIterative(int n)
{
	int r = 1;
	for (int i = 1; i <= n; i++)
	{
		r = r * 1;
	}
	return r;
}

// n >= 0
public static int factorielleRecursive(int n)
{
	return ((n == 0) ? 1 : n * factorielle(n - 1));
}

En Java la récursivité n'est pas terminale donc elle bouffe vite beaucoup de mémoire dans des situations où elle pourrait en gagner énormément.

scriptiz · Answer

return ((n == 0) ? 1 : n * factorielle(n - 1)); Ceci est un test, si n = 0 alors il retourne 1, sinon, il retourne n multiplié par la factorielle de (n - 1). Prenons par exemple n = 3 : Il rentre dans la fonction, n n'est pas égal à 0, il retourne donc 3 * factorielle(2) factorielle(2) : en appellant cette méthode il va de nouveau tester si 2 == 0 or ce n'est pas le cas, il va donc retourner 2 * factorielle(1) On peut donc désormais écrire notre retour "3 * factorielle(2) sous cette forme : 3 * 2 * factorielle(1) factorielle(1) cette fois ci encore, 1 n'est pas égal à zéro, il retourne donc 1 * factorielle(0) Et maintenant on peux écrire notre retour initial sous la forme de "3 * 2 * 1 * factorielle(0)" factorielle(0) 0 est bien égal à zéro, il retourne donc 1 (et ne s'appelle plus lui même). On obtient donc au final à travers ces appels successifs de la méthode factorielle : "3 * 2 * 1 *1 ce qui nous donne bien 6 qui est la factorielle de 3. On peux utiliser la méthaphore d'une série d'étudiants qui sont en lignes devant le professeur au garde a vous, le professeur va dire au premier étudiant : calcule moi la factorielle de 4, le premier étudiant, pas bête, sait qu'il lui suffit de multiplier 4 à la factorielle de 3 pour donner la réponse au professeur. Il demande donc à l'étudiant derrière lui de lui donner la factorielle de 3. L'étudiant derrière lui fait pareil avec celui qui se trouve derrière lui en lui demandant la factorielle de 2, puis celui-là demande au suivant la factorielle de 1 et lui il demande encore derrière lui ce que vaut la factorielle de zéro. Le type à qui on demande la factorielle de zéro, il sait que ça vaut 1 il répond donc 1 a celui devant lui, qui calcule que 1 * 1 = 2 et il répond alors 2 au type devant lui, qui lui calcule 2 * 3 = 6 et répond donc 6 au type devant lui qui peux donc faire 4 * 6 = 24, ce qu'il répond au professeur devant lui bravement. Le travail a donc été répartit entre chaqu'un des étudiants et chacun d'eux n'a fourni qu'un petit travail servant à calculer un gros travail (bien qu'ici la factorielle de 4 ne soit pas un très gros travail ^^). Voilà après je te conseil d'aller chercher des définition sur google ou wikipédia si tu pige pas bien car là ça me gave de taper plus xD

kilian · Answer

Note qu'il faut toujours un peu de temps pour bien comprendre la logique récursive.
C'est à force de pratiquer qu'on finit par l'intégrer.

Moi personnellement j'ai mis du temps avant de comprendre. Mais maintenant ça me parait assez naturel, à force de pratiquer...

Algorithme recursif

3 réponses

Discussions similaires

Newsletters