DEV/DEV.3.2/cours/2.Récursivité.md

Principe

• Une méthode récursive est une méthode qui s'appelle elle-même.

Pour entrer une récursion sans fin, on doit prévoir dans la méthode :

• Un cas récursif
• Un cas de base
• Un test pour choisir le cas basé sur les informations entrantes Il ne peut pas y avoir de compteur car à chaque appel on refait l'initialisation (repart à 0). Si l'on veut un compteur, ça doit être un paramètre. Typiquement, cela signifie que les arguments d'appel changent à chaque appel. Dans le cas d'un objet, on peut changer ses attributs plutôt que de changer d'objet. Attention à prendre en compte l'objet d'appel.

Ex :

public static int multiply(int a, int b) {
	if(a = 0) {
		return 0 // cas d'arrêt
	} else {
		return multiply(a>>1, b<<1) + // a >> 1 : décale à droite (division par 2), b << 1 : décale à gauche (multiplication par 2) 
			(a&1)?b:0; // Si a est impair (a & 1 teste le bit de poids faible), on ajoute b, sinon on ajoute 0.
	}
}

multiply(5,8) 
	|->multiply(2,16)
	|		|->multiply(1,32)
	|		|		|-> multiply(0,64)
	|		|		|	     |->0
	|->40	|->32	|-> 32 <-|

Dans le cas d'une récursivité simple, on a une "phase ascendante" qui répète le code de la méthode se trouvant avant l'appel récursif, pas une exécution du cas de base, puis une phase descendante qui répète le code placé après l'appel récursif dans le sens inverse.

Ex :

public static int binomial(int n, int k) {
	if ((k == 0) || (k == n)) {
		return 1;
	} else {
		return binomial(n-1,k) + binomial(n-1,k-1);
	}
}