Discussion :

[valanscu77]

Bonjour tout le monde,

voila j'ai un problème avec la récursivité. Je suis censé programmer un tri par sélection de manière récursive mai je vois pas du tout comment faire. Est ce que quelqu'un pourrai m'expliquer en gros la logique d'un tel tri?

merci beaucoup

[millie]

Tu peux regarder ici :

http://algo.developpez.com/

Notamment ici :
http://algo.developpez.com/sources/?...#tri_selection

[koala01]

Salut,

La première chose à savoir, c'est que la récursivité peut, tres souvent, etre remplacée intelligemment par une boucle qui fera le travail

Evidemment, si c'est pour un travail scolaire, ou dans d'autres circonstances, on peut aussi etre tenu d'appliquer la récursivité, alors qu'il serait vraissemblablement plus facile de faire sans... Donc... il est peut etre intéressant de rappeler ce qu'est la récursivité, et comment arriver à l'envisager sereinement

La récursivité, c'est quoi c'est tout simplement une fonction qui est en mesure de s'appeler elle-même.

Le problème, c'est que si la fonction s'appelle elle-même, elle risque fort de le faire "ad-vitam", et donc qu'il faut trouver le moyen pour que, quoi qu'il arrive, elle finisse par se trouver dans une situation où elle arretera de le faire.

Cette situation dans laquelle la fonction ne se rappellera plus elle-meme est ce que l'on nomme "le cas de base", et l'ensemble des parametres passés à la fonction n'aura qu'un seul but: atteindre ce "cas de base".

Typiquement, l'action qui sera effectuée dans le cas de base est relativement simple: soit on en fait purement et simplement rien (si la fonction ne doit renvoyer aucune valeur), soit, on renvoit la valeur "de base" (celle qui permettra, de proche en proche, de calculer la suite)

Le gros du travail consiste donc, finalement, à pas grand chose:

• déterminer le cas de base
• déterminer le moyen d'atteindre le cas de base
• savoir comment modifier le cas de base pour pouvoir le renvoyer à l'appel précédent...

L'algorithme générique est du genre de

Code :

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

1
2
3
4
5
6
7
8
9
type_renvoi FonctionRecursive(argument,(...))
|    si( cas de base atteint)
|    |    renvoyer valeur de base
|    sinon
|    |    (actions à prendre avant appel à la récursivité)
|    |    variable= FonctionRecursive(argument modifié,(...))
|    |    (actions à prendre apres appel à la récursivité)
|    |    renvoyer la valeur récupérée modifiée s'il échoit
|    fin si

Deux exemples, parfaitement inutiles (hormis leur coté didactique) de récursivité seraient le calcul de l'élévation à l'exposant N d'une valeur et celui de la factorielle d'un nombre:

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
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
entier Factorielle(entier nombre)
|   @ la factorielle est la multiplication de l'ensemble des chiffres
|   @ non nuls qui précedent le nomre donné (le nombre donné inclu)
|   cas de base: nombre =1
|   si nombre =1
|   |   renvoie nombre
|   sinon
|   |   @ pour atteindre le cas de base, on passe nombre -1 à la fonction
|   |   @ et on se sert du retour de la fonction comme multiplicateur du 
|   |   @nombre
|   |   retour=Factorielle(nombre -1)
|   |   retour= retour x nombre
|   |   renvoie retour
|   fin si
 
 
 
entier Exposant(entier nombre, entier exp)
|   @Pour calculer l'exposant on multiplie nombre par lui meme exp fois
|   @d'affilée
|   @cas de base: exp =0 (n'importe quoi exposant 0= 1 :D)
|    si exp = 0
|    |    renvoie 1
|    sinon
|    |    @pour atteindre le cas de base, on soustrait 1 à exposant
|    |    retour=Exposant(nombre,exp-1)
|    |    @ on multiplie retour par nombre
|    |    retour=retour x nombre
|    |    renvoye retour
|    fin si

Pour le problème qui t'intéresse, il nous manque trois données primordiales pour te répondre correctement: ce que tu dois trier, l'ordre de tri et le critère de tri...

En effet, les actions à mener pour tendre vers le cas de base et le cas de base seront vraissemblablement différentes si tu dois simplement trier un tableau ou si tu dois trier une structure dynamique (liste ou arbre binaire/naire), si tu dois les trier par ordre croissant ou décroissant et si le tri doit s'effectuer sur un critère ou sur plusieurs critères, ce qui influencera fortement l'algorithme à mettre au point...

Si, apres ces explications, la récursivité n'est pas claire pour toi, tu peux toujours passer sur ==>cette page<== où elle est expliquée en long, en large et en travers.

Retiens également que la création de l'algorithme vient apres une étape primordiale: l'expression claire nette et concise des besoins de l'application à concevoir...

Or, tu avoueras que

un tri par sélection de manière récursive

fait un peu léger comme expression de ce qu'il te faut

En plus, il n'est pas d'usage sur ce forum de faire tout le travail à ta place: c'est le pire des services que l'on puisse te rendre, car cela mene bien souvent à faire quelque chose que tu n'aurais peut etre pas compris...

Si tu as un problème de compréhension sur un point bien précis, n'hésite pas à poser la question

Si tu as un problème à un moment bien précis de l'algorithme, montre nous ce que tu as déjà fait, et indique nous le problème que tu n'arrive pas à résoudre

Ce n'est qu'ainsi que tu obtiendras une aide à la fois efficace (pour résoudre ton problème) et utile (pour te permettre de comprendre et d'adapter la solution par la suite

[Rakken]

/me se souvient avec emotion de son premier algo récursif.

C'était a mes débuts en progs, et avec mon binôme de l'époque on devait colorier une zone (pour refaire un paint). Il fallait donc parcourir (et stocker) tous les points pour changer leur couleurs.
C'était en turbo pascal, et ca a été mon premier bug vraiment difficile à corriger "Stack overflow error" . L'algo était nickel sur le papier, mais une fois implémenté, la mémoire explosait pour des images plus grande que... 2cm² sur l'écran. J'ai refait l'algo differement, et on a pu colorier une image un peu plus grande, mais ca explosait toujours dans certains cas (genre colorier une image completement blanche).
Pour finir un prof nous a expliqué que la plupart du temps, un algo récursif peut se faire avantageusement remplacer par un while, et la, plus de soucis de mémoire ;-)

Sinon, pour revenir a ton problème, ben... je crois pas pouvoir en dire beaucoup plus que Koala01. Montre nous ce que tu as déjà ou ce qui te pose problème pour commencer et on verra ce qu'on peut faire ^_^

[naruto70]

Bonjour
Je suis désolé. Je sais que ce post est assez vieux mais c'est exactement ce que je cherche ( ou presque ).
Il faut que je fasse un tri par sélection de manière récursive. Il faut que je tri un tableau à indice simple dans l'ordre croissant.

ce que tu dois trier, l'ordre de tri et le critère de tri...

Je suis pas sur de savoir ce qu'est le critère de tri mais bon...
Je ne recherche pas du code mais plutot la logique. Je ne vois pas ce que peut être le cas de base à retourner. Est-ce que le programme est aussi court que pour calculer une factoriel ( avec un si ... sinon... et 2 instructions seulement ) ? Ou est-ce qu'il faut développer un peu plus ?

Merci

[Rakken]

Je suis pas sur de savoir ce qu'est le critère de tri mais bon...

Le critère de tri, c'est la méthode que tu utilises pour savoir quel élément est supérieur a un autre. Pour faire un cas simple
"aaaa" "b".
Si le critère de tri est l'ordre alphabétique, le "aaaa" arrive en premier.
Si le critère est le nombre de lettres, alors "b" arrive en premier.

Sinon pour revenir plus précisement a ta question, si je me souvient bien de mes cours d'algo, dans un tri par selection, du doit trouver l'élément le plus grand, le mettre a la fin du tableau et recommencer.
Intuitivement, ce que je ferai (ca n'est probablement pas optimal) c'est une fonction avec le tableau a trier en parametre. Premiere itération, je recherche l'élément le plus grand, je le sauve, puis je relance la fonction avec le même tableau moins l'élément que je vient de trouver (genre du peux passer l'élément a -1 si tu ne teste que des entiers positifs, ou autres astuces du genre) puis je continue jusqu'a ce qu'il ne reste plus que les éléments "éliminé" dans le tableau.
Ensuite je dépile, donc je retourne un tableau avec en derniere position l'élément que je viens de trouver (ici on est au niveau le plus profond, donc le tableau ne contient qu'un seul élément, le plus petit du tableau). Puis on remonte d'un niveau, et je retourne le tableau que j'ai récupéré avant, après avoir rajouté en derniere position l'élément trouvé a ce niveau, et ainsi de suite.
Et au final on se retrouve avec un tableau trié par ordre croissant ;-)