Discussion :

[Mckinl3y]

Bonjour à tous, j'aurais besoin d'aide sur la compréhension de la compilation d'un petit script java, l'idée est de me retourner le max d'une liste chaînée par récursion.

Comment ( et dans quel ordre) va être compilé ce code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int Maximum(Cellule c){
 
		if (c.suivant != null){
 
			int max = Maximum(c.suivant);
			if(max < c.valeur){
				max = c.valeur;
			}
 
			return c.valeur;
		}
		else 
			return c.valeur;
	}

Je ne comprends pas en ce sens :
selon moi, à chaque appel de Maximum() on recommence le code au départ sans passer au if, ce qui fait donc tourner en rond jusqu'à la fin de la liste où au final on retourne c.valeur par défaut.

pour appuyer mon code, voici le code de ma liste chaînée :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
public class Liste_chaînée {
 
	public Cellule tete;
 
 
	//constructeur
	 Liste_chaînée(){
 
		tete = null;
 
	}

et d'une cellule :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Cellule {
 
	public int valeur;
	public Cellule suivant;
 
	//constructeur
	Cellule(int _valeur){
 
		valeur = _valeur;
		suivant = null;
	}
 
}

je vous remercie d'avance pour votre temps et votre lecture

[Flodelarab]

Bonjour

Comment va être compilé ce code ?

Avec diligence.

Dans quel ordre va être compilé ce code ?

Qu'est-ce que ça peut bien te faire l'ordre de compilation ?
La compilation transforme tes fichiers *.java en fichiers *.class exécutables interprétables par une JVM (Java virtual machine).
Aux moment de l'exécution, tous les objets sont présents et compilés.

selon moi, à chaque appel de Maximum() on recommence le code au départ sans passer au if, ce qui fait donc tourner en rond jusqu'à la fin de la liste où au final on retourne c.valeur par défaut.

Le "sans passer au if " est abusif puisqu'on rentre dedans pour que la méthode s'appelle elle-même.
C'est essentiel. Tu fabriques par ce biais ton point d'arrêt.

Sinon, tu as tout compris.

À la première lecture, il y a quand même quelque chose de choquant dans ton code:
Dans un cas, tu retourne c.valeur et dans l'autre cas, c.valeur !!!
Ne te casse pas le tronc et renvoie directement c.valeur sans condition ...

Moins ironiquement, il me semble que tu veux renvoyer max et non c.valeur.

[anapurna]

salut

il y a quelque chose qui me parait incoherent

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
public int Maximum(Cellule c)
{  if (c.suivant != null)
    { int max = Maximum(c.suivant);
       if(max < c.valeur)
       { max = c.valeur; }
     return c.valeur; // ici tu est sur de retourner c.valeur ?  perso j'aurais mis la valeur de max 
     }
     else 
    return c.valeur;
}

[joel.drigo]

Salut,

Tout d'abord, ta question ne concerne pas la compilation (transformation du code source en bytecode exécutée par la JVM pour Java, et plus généralement transformation du code source en code exécutable dans une passe préfiliminaire à une exécution ultérieure, par opposition à du code interprété, donc en quelque sorte compilé au fur et à mesure de son exécution). ([EDIT]et puis il n'y a pas de script en Java, du moins pas encore; mais ça c'est une autre histoire). Elle concerne plutôt l'ordre d'exécution à priori.

Ensuite, en Java, comme dans tous les langages structurés, le code s'exécute en séquence : il suffit donc de suivre les lignes une à une pour connaitre l'ordre d'exécution. La récursivité n'y change rien : simplement, on appelle la fonction dans elle-même. Le plus important étant d'avoir une condition d'arrêt qui n'appelle pas la fonction elle-même, afin de ne pas avoir un nombre infini d'appels récursifs, ce qui ferait que le programme ne s'arrête jamais (sauf si on le force, évidemment).

1. On commence donc par exécuter if (c.suivant != null){ (je passe l'appel initial de la méthode)
2. si la condition testée par ce if est vrai, alors on exécute la première ligne du bloc :
   
   1. soit int max = Maximum(c.suivant); donc on recommence, mais pour la valeur suivant c
   2. puis on exécute if(max < c.valeur)
   3. si la condition est vrai, on exécute max = c.valeur;,
   4. puisreturn c.valeur;
   
   
3. sinon on exécute la première ligne du bloc du else
   
   1. soit return c.valeur;
   
   

La logique qu'on cherche à implémenter dans l'algorithme est de dire que la valeur maximum d'une liste de valeurs, c'est la valeur la plus grande entre la première valeur de la liste et le maximum des autres valeurs (ou particulièrement pour une liste chainée, la valeur la plus grande entre la première valeur et la plus grande des valeurs qui suivent). La condition d'arrêt étant de dire le maximum d'une liste de une valeur c'est l'unique valeur elle-même.

En gros :

Code logique :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
 max( valeur )  = valeur
max( valeur1, valeur2, valeur3...valeurn ) = max ( valeur1, max( valeur2, valeur3...valeurn) )

Soit, pour une liste chainé

Code pseudocode :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
fonction max
si valeur n'a pas de suivant
   valeurmax<- valeur
sinon
   valeurmax= max( valeur, max ( suivant de valeur ) )
fin si
return valeurmax

ou encore (en inversant pour être dans la logique du code que tu montres)

Code pseudocode :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
si valeur a un suivant
    truc = max  ( suivant de valeur )
    si truc plus grand que valeur 
        valeurmax = truc
    sinon 
        valeurmax = valeur
    finsi
sinon
   valeurmax = valeur
fin si
return valeurmax

Tu vois où je veux en venir ? [EDIT]Voir le message de @anapurna pour la réponse

[Mckinl3y]

Je vous remercie pour vos rapides réponses,

pardonnez moi en effet pour le côté "compilation", au lieu de l'ordre d'exécution.

Flodelarab,
Je faisait plutôt référence au second if, nous n'entrons pas dedans concernant l'appel de la méthode

Anapurna,
yes merci, c'est logique en effet

Joel.drigo
Merci beaucoup pour l'explication,
j'avais essayé d'éxécuter le code sur papier sans voir l'évidence, mais oui !
Une fois la dernière boucle de la méthode Maximum() effectuée par récursion, le max ne sera pas renvoyé en résultat final mais en résultat au

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

int max = Maximum(c.suivant);

,

Merci pour votre temps et bon code !