Discussion :

[zarohn]

Bonjour,

Je suis en train de faire un programme très basique qui cherche à inverser un string de façon récursive...

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class test {
 
  private static void inversion (String s, String sInverse, int size) {
  	if (size > -1) {
  	    sInverse = sInverse + s.charAt(size);
  	    inversion(s, sInverse, --size); 
        }
  }
 
  public static void main (String[] args) {
        String sInverse = new String();
 
  	inversion(args[0], sInverse, args[0].length() - 1);
  	System.out.println(sInverse);
  }
}

Le principe est que dans mon main je crée un string qui contiendra le résultat puis j'appelle la fonction inversion en donnant le string a inverser, le string pour le résultat ainsi que la taille-1 du string a inverser. Puis inversion ajoute le char situé en size (le dernier caractère au premier appel) et elle s'appelle elle même en décrémentant size ce qui permettra d'ajouter dans le string de résultat l'avant dernier char.... etc jusqu'à ce qu'on ait traité tous les char (ca s'arrête quand size vaut -1).

Quand je regarde le contenu de sInverse avec le debugger quand size vaut -1, mon string contient bien le bon résultat. Seulement, au retour dans le main, celui ci est vide ... C'est bizarre car je pensais que les variables étaient par référence donc comment expliquer que si a la sortie de inversion mon string est bien rempli, celui ci soit vide au retour dans le main

C'est une question de débutant.
Merci d'avance à tous ceux qui pourront m'aider à résoudre et surtout à comprendre ceci.

[unknow0]

Bonjour,

oui c'es bien par référence et c'est justement la le problème:
quand tu fait

Code :

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

sInverse = sInverse + s.charAt(size);

ca instencie une nouvelle String et donc une référence différente.
tu devrais plutot metre des StringBuilder (ou StringBuffer)

Cordialement

[zarohn]

Effectivement c'était ça le souci. Je viens de convertir le String en StringBuffer avec ajout dans celui par la méthode Append() et ça fonctionne :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class test {
 
  private static void inversion (String s, StringBuffer sInverse, int size) {
  	if (size > -1) {
  		sInverse.append(s.charAt(size));
  		inversion(s, sInverse, --size);
  	}
  }
 
  public static void main (String[] args) {
    StringBuffer sInverse = new StringBuffer();
 
  	inversion(args[0], sInverse, args[0].length() - 1);
  	System.out.println(sInverse);
  }
}

Merci beaucoup

Maintenant j'essaye de comprendre. Si comme vous le dite sInverse = sInverse + s.charAt(size) crée une nouvelle instance. Dans ce cas pourquoi ne se souvient t'il pas de la dernière crée ? Qui pourtant avait l'air de contenir le bon résultat ...

[adiGuba]

Salut,


Il n'y a pas de passage par référence en Java, mais uniquement par copie. Mais comme on manipule des références (on copie donc uniquement les références et non pas les valeurs des objets).

En gros cela s'apparente au passage par pointeur du C++.


Dans ton cas il serait plus approprié de retourner le résultat.
De même l'utilisation de l'opérateur + et de la récursion est une mauvaise idée, puisque cela va générer un très grand nombre d'objet temporaire...


A noter enfin l'existence de la méthode StringBuilder.reverse() qui fait exactement ce que tu veux...

a++

[unknow0]

parceque java fait un passage par recopie de la référence donc dans la méthode appelante la référence n'a pas changer.
c'est un peu le même problème avec les pointeur en c si tu veux changer la valeur d'un pointeur tu doit passer un pointeur sur le pointeur mais comme en java on ne peu pas passer de pointeur il faut en general passer une classe englobante ou mutable.

[zarohn]

dans la méthode appelante la référence n'a pas changer.

Merci, maintenant je comprend le pourquoi du comment.

Dans ton cas il serait plus approprié de retourner le résultat.

Un retour a la fin de inversion ? Quel intérêt si je peux construire mon StringBuilder justement par référence
(enfin par copie de référence comme vous dites) ...

[adiGuba]

Un retour a la fin de inversion ? Quel intérêt si je peux construire mon StringBuilder justement par référence
(enfin par copie de référence comme vous dites) ...

C'est plus dans la philosophie de Java, alors que ton code me fait plus penser à du C !

Pour utiliser ton code il faut :

• Lui fournir la chaine original (OK ca c'est logique)
• Lui fournir le buffer de travail, en paramètre in/out ce qui est déjà plus limite.
• Lui fournir la taille initial de la chaine original ! Là on est carrément hors-course.

Il est impératif de connaître le fonctionnement de ta méthode afin de l'utiliser correctement... Et tout cela pourquoi ? Pour utiliser un code récursif très gourmand en ressources



En retournant le résultat on obtient une signature bien plus simple :

Code :

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

1
2
3
	public static String reverse(String source) {
		return new StringBuilder(source).reverse().toString();
	}

a++

[zarohn]

ton code me fait plus penser à du C

Effectivement je faisait du C avant, et la je débute en Java. Ceci explique cela.

Sinon oui, je suis d'accord avec votre constat sur le fait que le faire en récursif est très gourmand et qu'il suffirait d'utiliser simplement la méthode reverse(). Mais je dois le faire en récursif, ça m'est imposé. Sachant cela aurais-je pus faire différemment ? Il me semble que je dois absolument lui passer size en paramètre car c'est justement lui qui marque la condition d'arrêt de ma récursivité ...

[thelvin]

Il me semble que je dois absolument lui passer size en paramètre car c'est justement lui qui marque la condition d'arrêt de ma récursivité ...

Avec un seul StringBuilder, en effet, tu n'as pas le choix... Et pour être honnête, pour construire des String dans le monde réel il vaut mieux un StringBuilder. Mais pour les besoin de l'exercice, faire des return de String était possible et permettait de se passer de size :

Code :

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

1
2
3
4
5
6
7
8
9
public static String inverse(String s) {
  if(s.length() == 0) {
    return s;
  } else {
    char head = s.charAt(0);
    String tail = s.substring(1);
    return inverse(tail) + head;
  }
}

[adiGuba]

Il me semble que je dois absolument lui passer size en paramètre car c'est justement lui qui marque la condition d'arrêt de ma récursivité ...

Ce que tu peut faire c'est d'utiliser une méthode d'entrée différente, qui instancie le StringBuffer et initialise les paramètres superflu :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
  private static void inversion (String s, StringBuffer sInverse, int size) {
  	if (size > -1) {
  		sInverse.append(s.charAt(size));
  		inversion(s, sInverse, --size);
  	}
  }
 
  public static String reverse(String s) {
    StringBuffer buffer = new StringBuffer(s.length());
    inversion(s, buffer, s.length()-1);
    return buffer.toString();
  }

a++

[zarohn]

Merci beaucoup à tous pour vos conseils et votre aide ... ! Très sympa.
Je passe le sujet en résolu.

[zarohn]

thelvin j'ai testé votre version et elle fonctionne très bien. J'ai compris que le principe est de sauver le premier char puis d'instancier un tail avec ce char en moins, puis on rappelle la fonction en passant le tail comme paramètre.

Seulement j'ai du mal à comprendre comment ca marche au niveau du remplissage du string resultat. J'ai l'impression que le return est exécuté à chaque appel et qu'il renvoi a chaque fois le head qui se stock petit a petit dans un string ce qui fait qu'a la fin ca donne le s a l'envers et qu'il est retourné quand la fonction se finit. Est-ce que c'est comme ça que ca marche ?

Merci.

[thelvin]

Ben c'est récursif, quoi.

Concrètement ce qui se passe, c'est qu'à chaque appel de la méthode, on garde sur la pile le premier caractère de la chaîne, et on rappelle la méthode avec ce qui reste de la chaîne. Donc en gros, tout est stocké sur la pile, caractère par caractère.

Ensuite, quand on commence à tout dépiler, on construit la chaîne résultante par une suite de concaténations : une par appel de méthode. On concatène la chaîne et le caractère qu'on avait gardé.

Tout ça n'est pas très efficace, on est bien d'accord. Mais c'est facile à écrire.

[zarohn]

Merci beaucoup.

[unknow0]

Tout ça n'est pas très efficace, on est bien d'accord. Mais c'est facile à écrire.

on est d'accord tu va instancier 2 String a chaque appelle :s

par contre la méthode d'adiGuba est pas mal du tous utiliser une Méthode d'entrer pour la récursion c'est pas mal, bien même on peu garantir que personne ne fera d'appel incorrecte a la fonction récursive.