[Récursivité] Recherche basique dans un tableau

Bonjour.
J'ai beaucoup de mal avec la récursivité, et notamment la logique qu'il y a derrière. Je sais qu'en principe à chaque fois qu'on a une boucle on peut la remplacer par un appel à la fonction. Donc je me suis essayé à un exo simple, et très classique, recherche du maximum dans un tableau. Ici l'exemple classique d'une itération :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

static void rechercheMax(int unTab []) { int max = unTab[0];   for (int j = 0; j < unTab.length; j++) { if (unTab[j] > max) { max = unTab[j]; } } System.out.println("Le max est " + max);   }

---

Rien d'exceptionnelle sous le soleil. Par contre là ou ça se corse sérieusement c'est la version récursive que j'ai fait :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

static int rechercheMaxRec(int[] unTab, int j, int max) { if (j < unTab.length-1) { if (unTab[j] > max) { max = unTab[j]; j++; rechercheMaxRec(unTab, j, max); }else { j++; rechercheMaxRec(unTab, j, max); } } return max; }

---

Là où j'hallucine et c'est vraiment un truc de "fou" c'est qu'une fois arrivé à la fin de la boucle, le compteur repart dans le sens inverse. Honnêtement je ne comprends pas, et même pas du tout.
Quand j'appelle ma fonction dans main elle se fait de la façon suivante

Code:

---

1 2 3

.....//il y a bien sur du code avant, int unTab[] = { 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 103, 10, 5, 16, 8, 4, 2, 1 }; System.out.println("Le max dans la recursive est " + rechercheMaxRec(unTab, 0,0));

---

si parmi vous pouvez m'expliquer deux choses, pourquoi que ça ne donne pas le bon résultat, et pourquoi que ce foutu compteur repart dans l'autre sens, c'est un phénomène particulièrement angoissant, parce que ça montre que j'ai rien compris à la récursivité.
Par avance merci.

Bonjour :coucou:

En voilà une série de bonnes questions.
Quelques idées en vrac :

• j < unTab.length-1 ? j < unTab.length ? j <= unTab.length-1 ?
• Avec d'autres langages, on aurait imaginé un tableau toujours plus petit. Mais je comprends que tu n'aies pas envie de reconstruire un tableau plus petit à chaque fois avec ce langage. Alors, allons-y pour l'indice qui change.
• Tu as bien pensé à une condition d'arrêt : quand j est maximum. Le maximum local est donc dans la valeur de la dernière case du tableau.
• rechercheMaxRec(unTab, j, max); ? Ce serait pas plutôt return rechercheMaxRec(unTab, j, max); ? Comment veux-tu qu'elle change ? Ou max=rechercheMaxRec(unTab, j, max); ?
• Perso, je ne comprends pas ta méthode. Le maximum du tableau est le maximum entre la case d'indice j et le maximum du reste du tableau. Et là ! C'est récursif !
  
  Code:

  ---

  1 2 3 4 5 6 7 8 9 10 11 12

  int rechercheMaxRec(int[] unTab, int j) { if (j==unTab.length-1) return unTab[j]; else { reste=rechercheMaxRec(unTab, j+1); if (unTab[j]>reste) return unTab[j]; else return reste; } }

  ---

Je réécris ta procédure, en changeant vraiment très peu de choses. Ça ne change rien sur le fond, ça va juste permettre de mieux voir ce qui se passe (enfin j'espère)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

static int rechercheMaxRec(int[] unTab, int j, int max) { time0 = date() wait(10) System.out.println ( "lancement de la procedure à " + time0 + " j vaut =" + j + " max vaut " + max ) if (j < unTab.length-1) { if (unTab[j] > max) { max = unTab[j]; } j++; rechercheMaxRec(unTab, j, max);   } System.out.println ( "fin de la procedure lancée à " + time0 + " rappel, j vallait " + j + " max vaut " + max ) return max; }

---

J'ai mis 2 fonctions à moi, il faudra probablement les traduire :
date() : fonction qui renvoie date et heure ... pour qu'on voie bien le timing
wait(10) : attendre 10 centièmes de seconde , sinon ça va aller tellement vite qu'on ne verra pas la différence entre les différents lancements de date().

Ainsi tu devrais comprendre pourquoi j augmente de 1 a n, puis redescend de 1 à n.


Dans ta procédure, tu as une instruction return. Tu es bien conscient que cette instruction ne sert à rien . Elle servirait uniquement si tu faisais X =rechercheMaxRec(unTab, j, max);.
Et en l'occurrence, je pense que ta solution, c'est de faire max =rechercheMaxRec(unTab, j, max);.


Une image pour illustrer le fonctionnement.
Tu prends une feuille de papier, et tu écris sur cette feuille de papier les valeurs des différentes variables. Si il y a des opérations (j++) , tu barres la valeur de j, et tu mets la nouvelle valeur
Quand tu as un appel à une fonction, tu prends une nouvelle feuille de papier, qui vient couvrir la feuille actuelle. Et tu écris sur cette nouvelle feuille ce qui se passe : les valeurs de j, de max etc etc.
Quand tu as une instruction return, ou quand une procédure se finit, tu jettes la feuille qui était sur le dessus de la pile, et tu retournes donc sur la feuille qui était utilisée avant.
Et tu peux dérouler tout ton programme comme ça.

Bonjour,

Je pense que la comparaison devrait être j < unTab.length et non j < unTab.length-1. Pour un tableau de n éléments le dernier indice est n-1 or avec j < n-1 le dernier indice est n-2.

Si c'est une fonction, le code doit utiliser le retour de valeur. Par exemple :

Code:

---

1 2 3 4 5 6

static int rechercheMaxRec(int[] unTab, int j, int max) { if (j >= unTab.length) return max; if (unTab[j] > max) max = unTab[j]; j++; return rechercheMaxRec(unTab, j, max); }

---

Bien sûr, il faut appeler la fonction avec i = 0, max = 0x80000000 (en 32 bits).

Ça devrait tomber en marche.

Salutations

Messieurs -et Dames ? S'il y en a- je vous remercie tous pour vos réponses trés rapides. Honnetement, je n'attendais pas à réponses avant aujourd'hui. Je suis à la fois surpris, et content. J'en ai vu meme qui ont répondu le jour meme.
Le problème a été effectivement résolu, en ajoutant à la fonction une valeur de retour. Malgrés tout ça, je ne vous cache pas que j'ai de gros problèmes à faire de la récurisivité. J'ai besoin de faire plus d'exercices, et pour cela je m'adresse à vous. Connaissez vous un bon site web, ou un livre qui me permettrait de m'exercer.
En vous remerciant tous infiniment pour votre aide.

HTTPS://recursivite.developpez.com