Récursivité de la fonction Tri-Fusion

Version imprimable

Bonjour,

Je suis débutant, et je ne comprends vraiment pas la fonction "Tri-Fusion" tirée de l'algorithme qui s'y rapporte. Je comprends la logique générale, mais j'ai beaucoup plus de mal avec l'implémentation.

J'ai écrit la fonction comme suit :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 int A[] = {5,1,3,7}; public static void triFusion(int A[], int p, int r) { int q; if(p < r){ q = ((p+r)/2); triFusion(A, p, q); triFusion(A, q+1, r); Fusion(A, p, q, r); } }
Je ne comprends pas l'ordre d'appel des fonctions triFusion(A, p, q), triFusion(A, q+1, r) et Fusion(A, p, q, r). Quelqu'un peut-il m'expliquer ce qui se passe concrètement ?

Merci.

07/07/2016, 13h43
joel.drigo
Salut,
1. public static void triFusion(int A[], int p, int r) { on appelle triFusion avec en paramètre un tableau, un index de début (p) dans ce tableau, un index de fin (r)
  Donc, on va traiter une sous partie du tableau A, de l'élément p, à l'élément r (exclu, comme généralement)
2. if(p < r){ si p est inférieur strictement à r donc pas si p==r surtout (le cas r>p étant absurde, mais également éliminé par ce test, donc pas d'erreur ensuite)
3. q = ((p+r)/2); on chercher l'index médian, celui situé au milieu de l'intervalle [p,r[
4. triFusion(A, p, q); puis on rappelle triFusion récursivement pour le tableau A, pour l'intervalle [p,q[...
5. triFusion(A, q+1, r);... puis pour l'intervalle [q,r[
  Donc, en résumé, pour traiter une partie de tableau, on va la traiter en deux fois, la première moitié d'abord, puis la seconde, et ça récursivement, donc à la deuxième récursion, on traitera la première moitié en deux fois, sa première moitié d'abord, sa second ensuite, sa première moitié étant traité en 2 fois, sa première moitié d'abord, sa seconde ensuite, et ainsi de suite,
  jusqu'à ce que le test if (p<r) soit faux. Ce test consitue la condition d'arrêt de la récursivité)
6. Fusion(A, p, q, r); ici on appelle une autre méthode qui doit probablement rassembler les résultats des 2 appels sur les deux moitiés de partie de tableau
Quand on appelle la méthode triFusion(a, 0, a.length) on commence à traiter le tableau a entier (du début à la fin), ce qui traitera sa première moitié et sa seconde, et ainsi de suite selon la récursivité décrite ci-dessus.
07/07/2016, 15h05
HansCastorp

Merci pour cette réponse !

Je viens de me rendre compte que je n'avais pas très bien compris cette histoire de récursivité.

Je n'avais pas remarqué que, lors du deuxième appel (et des appels suivants) à triFusion, le premier appel triFusion était mis en "pause" en attendant le retour des autres appels internes...

Je pense avoir mieux compris le fonctionnement, merci encore !

Ce n'est pas que c'est mis en pause, c'est que les appels sont par défaut séquentiels, donc consécutifs, et un appel ne commence que quand le précédente est terminé (il faut faire quelque chose de spécial pour que 2 appels soient parallèles, ce que tu verras plus tard).

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Exemple {
 
   private static void print(int n) {
         System.out.println("Compte : " + n);
         if ( n>0 ) {
              print( n-1 );
         }
   }
 
   public static void main(String[] args) {
         print(10);
   }
 
}

Cette récursion peut être convertie dans la séquence suivante :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Exemple {
 
   public static void main(String[] args) {
         int n=10;
         System.out.println("Compte : " + n);
         // 10>0
         n = n - 1; // n=9
         System.out.println("Compte : " + n);
         // 9>0
         n = n - 1; // n=8
         System.out.println("Compte : " + n);
         // 8>0
         n = n - 1; // n=7
         System.out.println("Compte : " + n);
         // 7>0
         n = n - 1; // n=6
         System.out.println("Compte : " + n);
         // 6>0
         n = n - 1; // n=5
         System.out.println("Compte : " + n);
         // 5>0
         n = n - 1; // n=4
         System.out.println("Compte : " + n);
         // 4>0
         n = n - 1; // n=3
         System.out.println("Compte : " + n);
         // 3>0
         n = n - 1; // n=2
         System.out.println("Compte : " + n);
         // 2>0
         n = n - 1; // n=1
         System.out.println("Compte : " + n);
         // 1>0
         n = n - 1; // n=0
         System.out.println("Compte : " + n);
         // 0>0 faux : arrêt
   }
 
}

Ou sous forme de boucle :

Code:

1
2
3
4
5
6
7
8
9
public class Exemple {
 
   public static void main(String[] args) {
         for(int n=10; n>=0; n = n - 1) {
             System.out.println("Compte : " + n);
         }
   }
 
}