Aller au menu - Aller au contenu

La récursivité

Pour accéder à cette section
Connectez-vous !
connexion_rpx
Page Précédente  1  2 
Pseudo Commentaire
Page Précédente  1  2 
Hors ligne Pi3R0 # Posté le 31/08/2008 à 01:50:49
Turlututu... ♫
Avatar

Ville : Paris
Pays : France métropolitaine

 J'ai été largué avant la fin ^^

Bravo pour ton travail !
Enjoy :)
 
Hors ligne neamar # Posté le 03/11/2008 à 21:15:05
Just know the rules
Avatar
Flux RSS
close

Études : INSA Lyon

 Bon tuto effectivement...en tout cas, c'est la première fois que je lis quelque chose d'aussi clair sur ce sujet. Je me suis permis d'en rédiger une suite La récursivité : Pour aller plus loin qui intéressera peut-être certaines personnes...

Juste une remarque quand même :
Citation : Tuto

Avancement : 80%
Licence : Copie non autorisée


Je dirais bien qu'il est terminé...
Et en plus :
Citation : Tuto

Ce tutoriel est mis à disposition sous licence creative commons - Paternité - Partage des conditions à l'identique. Ça signifie que vous pouvez librement copier et modifier ce tutoriel, à condition de citer l'auteur original et de conserver cette licence.


Un peu contradictoire tout ça :)

De toute façon personne ne lit les signatures. Ah si toi ? Bon bah personne d'autre que toi alors ;) .
 
Hors ligne yoch # Posté le 17/12/2008 à 02:23:53
Avatar

 Excellent tuto !

Citation : tuto
D'autre part, certaines fonctions ne peuvent pas devenir tail-récursives. Comme nous l'avons vu, une fonction est tail-récursive quand l'appel récursif est la dernière chose effectuée par la fonction. Qu'en est-il des fonctions qui font plusieurs appels récursifs (notre exemple max_pommes par exemple) ? Et bien c'est simple, ces fonctions ne peuvent tout simplement pas être rendues tail-récursives : seul le dernier appel pourrait être converti en appel terminal, et tous les autres appels (dans la boucle for de notre exemple) augmenteront la pile d'appels.
Cela pose-t-il un problème fondamental ? La réponse est non. En effet, la justification de l'optimisation tail-rec des fonctions est d'obtenir les mêmes performances que la version itérative. Pour ce genre de fonctions (récursivité à appels multiples), il n'existe pas de version itérative équivalente qui soit aussi simple. La version récursive est donc la seule manière simple de formuler le problème, et toutes les versions itératives basées sur cet algorithme devront trouver une manière de remplacer la pile d'appels (qui stocke des informations qui nous arrangent), et leurs performances ne seront donc pas meilleures.

Je ne suis pas tout a fait d'accord. Pour des raisons de fiabilité (robustesse), on préférera souvent une version itérative avec gestion manuelle de la mémoire (pile ou autre), car sur des fonctions demandant un très grand nombre d'appels, la pile "explosera" sans probleme et le programme se termine brusquement (car la taille de la pile est généralement assez limitée par défaut, du moins en C).

Exemples qui me sont arrivés : un quick-sort trop naïf, un parcours en profondeur sur un très gros graphe, etc.
Comprendre la messagerie électronique
Introduction à la programmation dynamique
Le backtracking par l'exemple : résoudre un sudoku
Bloquer du contenu avec le fichier hosts - La commande sed
Modifier une application Windows
 
Hors ligne j!pé # Posté le 26/12/2008 à 16:26:47
L'apprenti de service
Avatar
close

Ville : Montévrain
Pays : France métropolitaine

 Tuto très interessant, je ne connaissais pas du tout la récursivité et me voilà maintenant moins bête.
Si j'ai bien compris, on peut se poser la question pour envisager la récursivité à partir du moment ou il y a une boucle while ou for dans une fonction ?
-- La signature que vous avez demandé n'est pas disponible pour le moment, veuillez réessayer ultérieurement. --
 
Hors ligne Zarmakuizz # Posté le 29/12/2008 à 11:56:15
Un réseau social! Vade Retro!
Avatar

 Quand tu as écris que la récursion terminale était possible en C, j'aurais bien aimé voir une fonction récursive terminale écrite en C, même si on quitte un peu le côté théorique du tutoriel. Mais peut-être que ça ne ferait que perdre dans la lecture ceux qui ne manipulent pas de langage ressemblant au php ou au C ...

Ceci dit, très bon tutoriel! Ces heures à écrire entre 11H et 2h du matin se révèlent utile!
OCRemix... pourquoi pas ?
Systèmes d'exploitation :
_Archlinux sans KDE 4
_Ubuntu avec Gnome
_Debian
 
Hors ligne Kev2a # Posté le 17/03/2009 à 21:34:09
Demacia !
Avatar

Ville : Ajaccio
Pays : France métropolitaine
Études : EPITA

 Je crois que j'ai assez compris, mais c'est assez dur, j'étais H.S arrivé aux "détails de la récursivité"...
Mais bon je ne sais pas s'il pourrait être plus simple... C'est un sujet qui a l'air assez compliqué.
Donc je le relirais, jusqu'à ce que je sois sur d'avoir tout compris ;)

Par contre je ne pense pas que le niveau de difficulé (débutant) soit approprié...Il faut tout de même des bases en PHP ou C pour les exemples...
Epita Promo 2014
ING1
Projet de Sup : Team Deity Crew - aMAZEing Escape
Image utilisateur
 
Hors ligne Pewe31 # Posté le 30/04/2009 à 15:48:47

Ville : Toulouse
Pays : France métropolitaine

 Un peut dure a assimiler, mais c'est surtout dut au sujet...
J'ai eu pas mal de souci à comprendre à cause de Ocalm, mais c'est parce que je n'en ai jamais fait.
on peut coder avec des strings, mais il faut faire attention aux dépassements de tampons!
 
Hors ligne elmcherqui # Posté le 22/06/2009 à 18:15:49
la vie est un programme
Avatar

Ville : Casablanca
Pays : Maroc
Études : SUPINFO Maroc à Casablanca

 Merci pour le tuto , tres interessant :)
- La répétition est humaine , la récurrence Divine .
- il faut être fou pour ne pas utiliser la récursivité quand il le faut !

 
Hors ligne Zebrure # Posté le 22/08/2009 à 22:42:24
return EXIT_FAILURE;
Avatar

 Salut, très bon tuto mais tu peux remplacer :
Code : PHP
1
2
3
4
5
6
7
<?php
function fac($n)
{
    if ($n == 1) return 1;
    return $n * fac($n - 1);
}
?>

par :
Code : PHP
1
2
3
4
5
6
7
<?php
function fac($n)
{
    if ($n == 2) return 2; //Pas besoin de retourner 1 qui ne change rien dans une multiplication ;) 
    return $n * fac($n - 1);
}
?>
Hors ligne bluestorm # Posté le 22/08/2009 à 23:03:17
dont ask to ask
Avatar
Groupe : Anciens
Flux RSS
close

Et si on demande fac(1) ?

La vraie définition se fait en mettant 0, et pas 1, en condition d'arrêt, je le signale en remarque.
big tuto algorithmique | tuto récursivité [PHP] | tuto typage | textes divers

Ours & Hippy
— le blog
 
Hors ligne toustesmorts # Posté le 01/11/2009 à 00:47:26
Avatar

 tuto très instructif, même pour le commun des "codeurs".
à ne pas lire à 1h du mat la tête dans le cul u_u
quand on suppose qu'on sait, on ne sait pas forcément
quand on sait, on sait qu'on ne peut pas supposer, on pense qu'on sait
on peut toujours supposer, on sait alors qu'on ne peut jamais savoir qu'on sait
vous pensez savoir? le savoir n'est qu'un mot, tout n'est pas défini,
et encore moins les avis sur les définitions des mots
chacun voit les choses comme il peut. Certains, comme ils veulent
 
Hors ligne keke21410 # Posté le 07/04/2010 à 22:52:27
"Belong to web"
Avatar

Ville : Ancey
Pays : France métropolitaine

 bah je suis pas loins des 1 heures du mat (ah si assez) mais j'avoue ne pas avoir compris le dernier exemple !
Dtoute façon moi les algo, j'ai jamais réussi !
Tuto bien expliqué, merci !
Mais j'ai remarqué un ptite erreur, ou c'est moi qui déconne, j'ai un doute sur :

Citation
Il existe une méthode pour obtenir une fonction tail-rec, qui consiste à... changer la fonction :

Code : OCaml
1
2
3
let rec fac(acc, n) =
    if n = 0 then acc
    else fac(n*acc, n-1)




Que fait cette fonction étrange ? Elle calcule la factorielle d'un entier : fac(1, n) renverra bien la factorielle de n. Voici le déroulement de l'appel de fac(1, 3)

Code : Autre
1
2
3
4
5
6
7
8

fac(1, 3) :
   3 ne vaut pas 0, donc je continue
   fac(1 * 3, 2) : fac(3,2):
   2 ne vaut pas 0, donc je continue
   fac(3 * 2, 1) : fac(6,1) :
   1 ne vaut pas 0, donc je continue
   fac(6 * 1, 0) : fac(6, 0)
   0 vaut 0, je renvoie acc : 6





J'ai un doute, sur les lignes de l'expliquation 3, 5 et 7, ce serait pas :

Code : Autre
1
2
3
4
5
6
7
8

fac(1, 3) :
   3 ne vaut pas 0, donc je continue
   fac(3 * 1, 2) : fac(3,2):
   2 ne vaut pas 0, donc je continue
   fac(2 * 3, 1) : fac(6,1) :
   1 ne vaut pas 0, donc je continue
   fac(1 * 6, 0) : fac(6, 0)
   0 vaut 0, je renvoie acc : 6



C'est pas important, mais je suis une gourde ...
Image utilisateur
#LGDF: Golmote vaincra !
[Projet] Un magazine du zér0 [Projet] site web jeux pokemon
Mon avatar te plais pas ? Cliques ici pour le changer !
Image utilisateur
 
Hors ligne talonneur56 # Posté le 08/03/2011 à 21:41:27
le rugby = école de la vie!!!
Avatar

Ville : Questembert
Pays : France métropolitaine

 bonjour à tous et à toutes,
j'ai trouvé un site qui propose un cours sur la récursivité en vidéo très bien expliqué: lien

vous m'en direz des nouvelles ;)
"Le rugby ne se joue pas en deux, mais en trois temps: avant, la ferveur; pendant, la bravoure; après, la fraternité" (René Crabos)

un jour un grand homme a dit: "l'ignorant affirme, le savant réfléchit et le sage doute"

"Sciences sans consciences n'est que ruine de l'âme" - François RABELAIS

Mon rêve en tant que programmeur amateur? Créer un jeu pokémon en C/SDL!!!! :soleil: :D

http://www.meruvia.fr/


 
Hors ligne pingloveur # Posté le 12/03/2011 à 20:22:26
Le roi des débutants
Avatar

Études : Lycée Déodat de Séverac - Toulouse

 Le ping-pong n'est pas un sport, en tout cas je connais pas.
Cependant, je connais le tennis de table :p
Bon fallait que je fasse la remarque...
Sinon merci pour ton tutoriel. Cela est intéressant à lire.
The Big débutant
Same in english!!!
I'm singing in the rain, and i love...
RTFM= Read the fucking manual
Mon dieu, j'ai dit une bétise^^
C'est parce que la lumière va plus vite que le son qu'on a l'air intelligent avant d'être con :lol:
 
Hors ligne Lomira # Posté le 21/04/2011 à 20:42:52
Avatar

 Très bon tuto en effet. Je me souviens j'ai découvert ce concept en cherchant un algo pour résoudre des tours d'Hanoï, je ne connaissais que l'itératif. J'avais fini par trouver une solution, mais quelle prise de tête à l'époque ! J'avais donc regardé sur le net pour voir si il n'y avait pas plus propre ... et là ... le miracle se produisit ! J'avais beaucoup aimé le fait de pouvoir voir le problème d'un angle different !
Hors ligne blh # Posté le 21/04/2011 à 23:46:46
1 + 1 = 0
Avatar
Flux RSS
close

Pourquoi ne pas écrire n! = n(n-1)(n-2)3 x 2 x 1 à la place de fact(n) , etc ?
Saintes sont les armes quand il n'est plus d'espoir qu'en elles.
 
Hors ligne bluestorm # Posté le 22/04/2011 à 06:30:30
dont ask to ask
Avatar
Groupe : Anciens
Flux RSS
close

Lomira > merci pour ta remarque. Ça fait toujours plaisir que des gens apprécient le tutoriel.

blh > je n'ai pas choisi la notation n! pour deux raisons. D'une part, elle est un peu étonnante pour les gens qui ne l'ont jamais rencontré, en particulier il faut bien penser à écrire (n-1)! et pas n-1! (comme pour l'appel de fonction classique, mais quand on découvre ce symbole pour la première fois la tentation est grande de virer les parenthèses). D'autre part, ça me permet d'avoir une cohérence entre le nom "mathématique" et le nom "informatique" : dans les exemples de code que je donne, je ne pourrai pas utiliser la syntaxe (...)! de toute façon. Autant éviter d'ajouter une différence, une remarque "ah mais en fait c'est la même chose", et une chance de plus que le lecteur soit confus. Je préfère qu'il se concentre sur les idées importantes.
big tuto algorithmique | tuto récursivité [PHP] | tuto typage | textes divers

Ours & Hippy
— le blog
 
Hors ligne Hindioumax # Posté le 24/07/2011 à 15:27:54
Zéro pointé !
Avatar

 Je suis allé et venu plusieurs fois sur ce tuto pour comprendre enfin ce concept de programmation.
Franchement, quel magnifique façon de programmer ! Un peu casse-tête au premier abord, c'est vrai, mais à force de persévérance le déclic se fait.
Ce que j'adore par dessus tout, c'est l'effort de réflexion que l'on doit faire pour énoncer clairement son problème ! Qu'est ce que je veux faire ? ou obtenir ? Quelles sont les informations que j'ai déjà à ma disposition ou les résultats que je connais déjà d'avance ?

Décomposer son problème en sous-problèmes plus simples oblige parfois à revoir son problème sous un angle différent et à réfléchir à une autre manière de procéder pour arriver au résultat final.
Et lorsque la solution pointe le bout de son nez, c'est du bonheur à l'état pur !! Véridique ! :D
Au delà du code lui-même, qui est généralement plus et court et élégant, l'approche récursive m'a permis de réfléchir différemment sur certains problèmes, mais surtout à exposer clairement l'énoncé de ma problématique principale.

Bref, je vous conseille la lecture et la relecture ! ;)

ps: D'ailleurs, je verrais bien un sous-tuto pour apprendre poser et décomposer ses problématiques. C'est finalement bien le plus dur !
La curioZité est un vilain défaut de passionné !
Image utilisateur
 
Hors ligne PyNuts # Posté le 25/08/2011 à 16:15:07
Avatar

Ville : La côte saint andré
Pays : France métropolitaine

 Ton tuto m'intéresse beaucoup mais j'aurai préféré des exemples en pseudo-code plutôt que du PHP :-°
Si une âme charitable pouvait poster le code sur le nombre de matches en Python ça serait franchement sympa :p
Hors ligne bluestorm # Posté le 25/08/2011 à 17:34:17
dont ask to ask
Avatar
Groupe : Anciens
Flux RSS
close

Code : Python
1
2
3
4
5
6
7
8
9
def matches(joueurs):
    if len(joueurs) <= 1:
        return []
    dernier_joueur = joueurs[-1]  #le dernier joueur
    autres_joueurs = joueurs[:-1] #tous les joueurs sauf le dernier
    autres_matches = matches(autres_joueurs)
    for autre_joueur in autres_joueurs:
        autres_matches.append((autre_joueur, dernier_joueur))
    return autres_matches
big tuto algorithmique | tuto récursivité [PHP] | tuto typage | textes divers

Ours & Hippy
— le blog
 
Hors ligne NougatRillettes # Posté le 02/02/2012 à 22:56:04
Tchip !
Avatar

 Comme dit plus haut, tu devrais traiter le problème des tours de Hanoï (qui permet d'utiliser le raisonnement par récurrence). Voir aussi problème 67 du projet Euler.
Sinon, bah, c’est super quoi.
Image utilisateur
 
Hors ligne Lechetemi # Posté le 27/03/2012 à 19:53:35
Avatar

 Bonjour j'ai un problème je doit programmer un algorithme avec une fonction récursive. On me donne le premier terme et je doit afficher tout les termes de U0 a Un.
Sachant que Un+1=f(Un) et que f=x-x²
Hors ligne snitch_xellos # Posté le 10/04/2012 à 21:59:49
Avatar

Avis : Très bon

Études : USTHB

 malheureusement que je connais pas comment programmer en PHP :(
Merci c'est magnifique
Hors ligne eazyzero # Posté le 22/04/2012 à 00:57:25
Avatar

Avis : Très bon

je comprend un peu mieux la recursivité. Merci pour ce Tuto
Pour accéder à cette section
Connectez-vous !
connexion_rpx