Bonjour bonjour,
J'ai contacté il y a quelque temps cysboy pour son tutoriel. Il est beaucoup mieux que le premier ( il m'a même permis de reussir la partie cour de mon DS de ce matin alors merci bien ). Je lui ai demandé s'il été question de recursivité dans son tutoriel, il m'a dit qu'il n'y avait pas pensé, mais qu'il le ferait surement.
En attendant je vous demande si vous n'avez pas quelques liens qui expliquerait bien comment ca fonctionne.
Attention : j'ai déjà fait quelques recherches, mais rien de bien concluant, puisque je ne trouve pas exactement pour java, ou alors les explications ne sont pas super super.
Je sais vous allez me dire que ca ne change pas vraiment, mais bon java c'est mieux quand on fait du java
En fait j'ai déjà lu le sujet sur le tri rapide dans les tutoriels non officiels, mais je n'arrive pas à bien l'adapter.
Je ne cherche pas exclusivement le tri rapide, mais quelque chose qui me permettent de faire une fonction recursive comme je fais un if ou un while, c'est à dire sans y penser mais naturellement
Je vous remercie de vos réponses, et je fais partie des premiers a ouvrir le forum JAVA, j'espere ne pas etre le dernier
Ici, il y a une classe Maillon qui a une valeur et un sous maillon.
Une méthode permet de décrire l'ensemble d'une chaîne qui peut être constituée de plusieurs maillons.
La méthode toString de la classe Maillon sera appelé de façon récursive si une instance de maillon a un sous maillon.
Mais teste et explore ce code :
public class Maillon {
private Maillon sousMaillon;
private String nom;
public Maillon(String str, Maillon sousMaillon){
nom = str;
this.sousMaillon = sousMaillon;
}
//Méthode toString qui, ici sera appelé de façon recursive.
//Cette possède un objet qui peu, lui aussi, appelé la méthode toString
//Ce qui fait que la pile d'invocation grandi jusqu'au denier maillon
//Celui-ci atteint, la JVM dépile les invocations de toString pour arriver jusqu'au premier objet invocateur
//Ce qui a pour effet de retourner différents élément selon l'endroit de la chaine de maillon
public String toString(){
return this.nom + ((this.sousMaillon != null) ? ", " + this.sousMaillon.toString() : "" );
// CECI REVIENT A FAIRE :
/*
if(this.sousMaillon != null)
return this.nom + this.sousMaillon.toString();
else
return this.nom;
*/
}
}
Et la classe pour tester :
public class Chaine {
public static void main(String[] args){
Maillon one = new Maillon("Maillon1", null);
Maillon two = new Maillon("Maillon2", one);
Maillon three = new Maillon("Maillon3", two);
System.out.println("Description de maillon 3 : " + three.toString());
System.out.println("Description de maillon 2 : " + two.toString());
System.out.println("Description de maillon 1 : " + one.toString());
}
}
Et voici ce que j'obtient :
En espérant t'avoir aidé.
PS : En fait la récursivité c'est le fait d'invoqué la même méthode, mais la particularité c'est que l'appel se fait dans cette même méthode. Cela joue sur la pile d'invocation (CF chapitre sur les threads dans la partie 3, bientôt disponible).
Merci de vos réponses.
Ce matin au ds dont j'ai parlé brievement dans mon premier post, on a eut un exercice sur les piles ( premier entré, dernier sortie ) ca ressemble un peu a ca. mais il n'y avait qu'une question sur la recursivité ( que je n'ai pas fait bien sur )
En gros l'exercie proposait ceci :
une classe Carte, une classe CelluleCarte, et une classe PileCarte
PileCarte est constitué de cellulescartes qui est lui meme constitué de cartes. On ne peut acceder qu'au premier élément ( attribut dessus )
moi en fait je vidais ma pile dans une pile temporaire pour avoir acces a tous les elements, puis je reconstituais la pile de base, c'est possible en recursif ? ca doit etre plus optimisé non ?
Pour ton histoire de pile l'approche itérative est encore la meilleur... le problèeme vient probablement de la méthode utilisée... On est pas sensé avoir besoin d'accéder à tout les membres d'une pile sinon la pile doit être capable de le faire.
J'imagine que as dû faire ta propre classe de pile alors tu n'as qu'à ajouter un fonction d'accès aléatoire (avec un nombre index). C'est moins rapide qu'avec un tableau mais si ne n'est utiliser dans des cas rares alors il n'y a pas de problème.
L'accès aléatoire est possible en approche itérative ou récursive mais attention au débordement possibles avec l'approche récursive. Là-dessus je ne peux te dire comment Java s'en occupe.
Nan c'etait pas ce but, c'etait a mon avis mpour nous tester si on savait parcourir une pile, parce que ca n'a pas vraiment d'interet, autant faire un tableau, mais la, c'etait pour nous tester.
Attends je te lis la question sur la recursivité :
ecrire la methode getHauteur() ( retourne la hauteur de la pile ) de facon recursive. Cette methode retourne le nombre de carte de la pile.
J'ai bien un code pour le tri rapide, mais je crois que si je prends un tableau de 15000 cases il range pas ^^'
A la limite je peux le poster pour voir ce qui va pas
Moi aussi j'ai eu quelques soucis à comprendre la récursivité au début et j'ai toujours un peu de mal aujourd'hui.
Je vais tenter de t'exposer un autre exemple malgré tout :
Je veux faire une fonction Factorielle qui retourne le factorielle d'un nombre entier passé en paramètre.
Je rappelle que le factorielle se calcul comme ça :
public static int Factorielle (int n) {
int Fact;
if(n<=1)
Fact=1;
else
Fact=n*Factorielle(n-1);
return Fact;
}
Quelques explications :
Si ton n est inférieur ou égal à 1, son factorielle vaut 1, ça je suppose que tu l'avais compris
Imaginons que l'on prend n=3, c'est donc supérieur à 1.
Fact va donc retourner 3*Factorielle(2)
Factorielle(2) qui lui retourne 2*Factorielle(1)
Factorielle de 1 qui retourne 1.
Ca nous fait donc 3*2*1 = 6
Il faut savoir que si tu fais un appel récursif, il te faut obligatoirement une condition de sortie (comme une boucle), sinon tu t'arrête jamais...
Excuse moi, mais ton code est un peu laid.
Pourquoi déclarer une variable intermédiaire qui ne sert à rien ?
public static int Fac (int n) {
if (n <= 1) return 1;
else return n * Fac(n-1);
}
C'est d'ailleurs une traduction du code PHP que j'ai proposé :
<?php
function fac($n)
{
if ($n == 1) return 1;
return $n * fac($n - 1);
}
?>
Je ne comprends pas très bien comment on peut comprendre le code Java sans comprendre le code PHP, mais encore une fois, si vous voulez proposer des exemples équivalents en Java, ne vous gênez pas.
J'ai créé une variable pour éviter les deux return, ça me paraissait plus clair.
J'avais pas vu ton code php, je ne savais pas qu'il était basé sur le même principe.
Perso je ne le trouve pas laid sont code, sa variable permet d'avoir un return unique à la fin de sa condition au lieu de deux return en plein milieu. C'est une peu selon ses préférences personnelles en fait.
public static int Factorielle (int n) {
int Fact;
if(n<=1)
Fact=1;
else
Fact=n*Factorielle(n-1);
return Fact;
}
la seule chose qui me choque particulièrement, c'est bien les majuscules pour le nom de la méthode et pour celui de la variable Ce qui ne respecte absolument pas les conventions et rend, je trouve, le code illisible.
version plus correct :
public static int factorielle( int n ) {
int fact;
if( n <= 1 )
fact = 1;
else
fact = n * factorielle(n-1);
return fact;
}
Et un poil plus optimisée :
public static int factorielle( int n ) {
if( n <= 1 )
return 1;
return n * factorielle(n-1);
}
sinon je trouve qui cet exemple illustre bien la récursivité !
Pourquoi pas, mais je ne vois pas vraiment l'intérêt du pseudo-code, étant donné que ça revient à utiliser un langage "fait maison" en espérant que tout le monde le comprenne, au lieu d'utiliser un langage déjà existant en espérant que tout le monde le comprenne.
Je pourrais essayer de faire du pseudo-code à la place, mais ce serait surtout pour des raisons psychologiques : on dirait que les gens voient "PHP", se disent "bouh je connais pas, donc je vais jamais comprendre le code".
La solution générique du pseudo-code est séduisante mais je crains que le résultat ne soit le même ("pseudo-code ? bouh connais pas ça").
Moi à ta place, je pense que je laisserais PHP partout, mais que j'écrirais en gros quelque part au début que ça vaut pour la plupart des langages de programmation (en citant ceux qui supportent la récursivité).
A la rigueur, tu peux aussi décliner le premier exemple de code en plein de langages différents pour prouver que c'est quasiment pareil. Mais juste le premier, après ce sera trop lourd.
Je pense que les exemples non-triviaux (par exemple dans ce tuto la fonction "matches") pourraient profiter de versions spécialisées : à partir du moment où on utilise un peu la bibliothèque du langage ou des expressions idiomatiques comme le $foo[] = $bar du PHP, je peux comprendre que les gens trouvent ça louche.
De plus, la nouvelle balise "secret" permet de rajouter du contenu sans trop alourdir visuellement l'ensemble du tuto.
Perso je ne le trouve pas laid sont code, sa variable permet d'avoir un return unique à la fin de sa condition au lieu de deux return en plein milieu. C'est une peu selon ses préférences personnelles en fait.
edit: ben on a répondu avant moi ^^'
C'est pas une question de preferences mais de rapidite et d'optimisation.
Avoir une variable en trop, c'est de l'espace memoire gache pour rien, sans compter l'opertation d'affectation qui prend du temps de processeur encore une fois pour rien.
Alors je vois gros venir le "ouais mais avec les ordinateurs d'aujourd'hui y'a assez de memoire et les cpu sont uber puissants"
Bah justement, calcule-moi la factorielle de 10 000 avec les deux methodes, tu verras une sacree difference.
Donc non, c'est n'est pas un confort de style, surtout quand on prend en compte la relative lourdeur du principe de la vm.
Au delà de la rapidité gagné (je suis d'ailleurs entièrement d'accord avec toi), on cherche ici à faire comprendre un principe.
Si je devais utiliser cette méthode, je ferais 2 return sans créer de variable mais là il m'a paru plus simple de compréhension, de part la clarté, de procéder avec une variable temporaire.
De toute façon la variable temporaire n'aide en rien à la lisibilité, elle alourdit inutilement la fonction.
On pourrait même dire qu'un programmeur va chercher son utilité (car quand on lit du code on pense d'abord que les choses sont utiles et qu'elles ont une raison, et après seulement on se demande si ce n'est pas inutile), ce qui lui fait perdre du temps. C'est pas vraiment déterminant sur une fonction aussi simple, mais à grande échelle la déclaration inutile de variables peut avoir des effets pervers.
Si un programmeur qui lit le tuto de récursivité a un problème avec le fait de faire plusieurs retours dans une fonction, c'est pas la récursivité qu'il devrait revoir, mais la programmation. C'est pas vraiment un concept compliqué, il est largement à la portée de l'ensemble des zéros.
mota > pour ma part je préfère l'approche conceptuelle (recherche de simplicité et de sobriété) à l'approche "performances". En particulier, "calculer la factorielle de 10 000" n'a pas vraiment de sens pour des raisons de dépassement d'entiers.
Au passage, rz0 m'a proposé une troisième version, équivalente à la mienne mais bien plus élégante (peut-être moins habituelle, par contre) :
public static int fac(int n) {
return n <= 1 ? 1 : n * fac(n-1);
}
Perso je ne le trouve pas laid sont code, sa variable permet d'avoir un return unique à la fin de sa condition au lieu de deux return en plein milieu. C'est une peu selon ses préférences personnelles en fait.
edit: ben on a répondu avant moi ^^'
C'est pas une question de preferences mais de rapidite et d'optimisation.
Avoir une variable en trop, c'est de l'espace memoire gache pour rien, sans compter l'opertation d'affectation qui prend du temps de processeur encore une fois pour rien.
Alors je vois gros venir le "ouais mais avec les ordinateurs d'aujourd'hui y'a assez de memoire et les cpu sont uber puissants"
Bah justement, calcule-moi la factorielle de 10 000 avec les deux methodes, tu verras une sacree difference.
Donc non, c'est n'est pas un confort de style, surtout quand on prend en compte la relative lourdeur du principe de la vm.
Ma réaction n'allais pas du tout dans ce sens là.Je sais bien que la métode avec les deux return sera plus éfficace et dans ce cas là j'aurais d'ailleur utilisé deux return également mais je vois pas en quoi on peu dire que le code d'Aragonas est "laid" . Evidement dans ce cas-ci on ne peu pas dire que l'un est moins façile que l'autre mais quans je vois parfois des codes avec des boucles multiples qui contiennent des return et des rutures partout en plein millieu ça fait peur .
Peut-être qu'à l'exécution ce sera plus rapide oui mais quand il faut relire le code c'est carrément le contraire
Mias bon faut savoir d'adapter au circonstances en fait c'est tout et puis niveau lisibilité c'est pas parce que qu'un code et plus lisible pour nous que c'est la cas pour tout le monde. Il suffit de regarder les manière de code entre des personnes qui ont commencé en asm, en pascal, en C voir en basic...
Joli débat mais on s'ecarte du sujet la ...
La formule de la recursivité je la connais, j'ai compris la recursivité qui va avec, mais ce n'est pas le probleme. On me presente une fonction recursive, je vais dire : mais oui c'est evident, mais je n'arrive pas a la faire moi meme.
Je n'ai pas le raisonnement logique qui suit.
Je vais vous poster ma fonction sur le tri rapide ( qui ne marche pas )
Le raisonnement qu'il m'a fallu pour le faire, m'a pris 2h avec l'aide de mon prof qui détaillé a peu pres tout au tableau
public class TableauTri
{
public static int[] creerTableau(int taille, int nombreMax )
{
int tab[];
tab = new int [taille];
for ( int i = 0; i < taille; i++)
{
tab[i] = (int) (Math.random()*nombreMax);
}
return tab;
}
public static void triRapide(int tab[], int debut, int fin)
{
int indicePivot;
if(debut<fin)
{
indicePivot = placerPivot(debut, fin , tab);
triRapide(tab, debut,indicePivot-1);
triRapide(tab, indicePivot+1, fin);
}
}
//renvoie l'indice du pivot
public static int placerPivot(int debut,int fin, int tab[])
{
int temp;
int indicePivot = debut;
debut ++;
while(debut <= fin)
{
if( tab[debut] < tab[indicePivot])
{
//Echange de debut et pivot
temp = tab[debut];
tab[debut] = tab[indicePivot];
tab[indicePivot] = temp;
indicePivot = debut;
debut++;
}
else
{
//echange de debut avec fin
temp = tab[debut];
tab[debut] = tab[fin];
tab[fin] = temp;
fin --;
}
}
return indicePivot;
}
//toString marche
public static String toString(int tab[])
{
String chaine = "";
int taille = tab.length;
for(int i = 0; i<taille; i++)
{
chaine = chaine + tab[i] + " ; ";
}
return chaine;
}
public static void main(String args[] )
{
int tab[] = creerTableau(15, 100);
System.out.println(toString(tab));
long temps1 = System.currentTimeMillis();
triRapide(tab, 0, 14);
System.out.println(toString(tab));
long temps2 = System.currentTimeMillis();
long diff = temps2 - temps1;
System.out.println(diff +"ms");
}
}
mais je vois pas en quoi on peu dire que le code d'Aragonas est "laid"
Il est laid parce qu'il est inutilement long et compliqué. Quand on peut faire sobre et proche de la définition mathématique, une version alambiquée et éloignée de cette définition (la notion d'assignation n'existe pas en mathématiques) est "lourde" (à la fois conceptuellement et au moment de l'exécution), et c'est pour ça que je dis qu'elle est "laide", car c'est plus rapide que "inutilement compliquée et qui porte à la confusion".
Mokette > le problème n'est pas un problème de récursivité. La partie "récursive" de ton code est bien placée et fait ce qu'elle doit faire (je ne suis pas tout à fait sûr de la condition (debut < fin), ce ne serait pas (debut < fin - 1) ?).
Le problème dans ton code (s'il y en a un, je dois dire que j'ai la flemme de tester) vient sûrement soit du code de test (peu probable), soit de la fonction placerPivot, ce qui serait classique puisque c'est la partie délicate.
En tout cas, ce n'est pas à priori un problème lié à la récursivité.
mota > pour ma part je préfère l'approche conceptuelle (recherche de simplicité et de sobriété) à l'approche "performances". En particulier, "calculer la factorielle de 10 000" n'a pas vraiment de sens pour des raisons de dépassement d'entiers.
Ouais, je vois ce que tu veux dire mais bon, les deux concepts sont étroitement liés. Plus tu fais simple, moins tu fais lourd.
Enfin on a deux approches différentes en général mais qui se recroisent bien souvent ^ ^
edit: y'a pas un moyen de désactiver ces saletés de smilies dans les posts ?
Recursivité
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
If you'd like to join us, read "How do we work at OpenClassrooms"! :)