public class Iter2Rec { public static void calcul(int n) { System.out.println(n); } // Un calcul itératif (répétition d'un calcul pour chaque valeur de la // variable d'itération) public static void fIter() { for (int i=0; i<10; i++) { calcul(i); } } // L'itération peut être traduite en récursion (terminale) // Récursion terminale: appel récursif immédiatement suivi d'un retour public static void fRec(int i) { if (i<10) { calcul(i); fRec(i+1); // appel récursif terminal return; } } // Mais dans l'autre sens: passer d'une récursion à une itération ? // Pas possible dans le cas général, mais dans le cas particulier // de la factorielle, ça devrait... // Définition récursive (non terminale) public static int fact(int n) { if (n==0) return 1; return n*fact(n-1); } // Explicitation du caractère non terminal de l'appel récursif // Entre l'appel et la retour, il y a des calculs à faire (la multiplication) public static int fact2(int n) { System.out.println("fact2("+n+")"); if (n==0) return 1; int r = fact2(n-1); r = n*r; System.out.println("retour="+r); return r; } // En utilisant la propriété de commutation de la multiplication on doit // pouvoir transformer les calculs effectués en remontant (1*2*3*4...) // par des calculs descendants (n*(n-1)*(n-2)...) public static int fact2accumulee(int n,int r) { System.out.println("fact2accumulee("+n+","+r+")"); if (n==0) return r; r = n*r; return fact2accumulee(n-1,r); // appel récursif terminal! } // On peut donc éliminer l'appel puisque rien ne se passe entre // l'appel et le retour, les variables peuvent être librement réutilisées // on transforme donc n en n-1 puis on fait une boucle arrière au début de // la fonction public static int fact2accumuleeIter(int n,int r) { while (true) { if (n==0) return r; r = n*r; n = n-1; } // return fact2accumuleeIter(n-1,r); } public static void main(String []a) { fIter(); fRec(0); fact2(6); fact2accumulee(6,1); System.out.println("Par iteration="+fact2accumuleeIter(6,1)); } }