Se connecter / S'enregistrer
Votre question

La récursivité

Tags :
  • Programme
  • Programmation
Dernière réponse : dans Programmation
13 Juin 2010 19:01:36

Bonjour a tous, je viens d'apprendre la récursivité, enfin connaitre la notion, j'ai bien compris comment cela fonctionne avec la fonction factorielle et la suite de Fibonacci. Le problème c'est que j'ai un excercice a faire dans lequel je dois utilisé la recursivité, probleme je coince completement, je ne sais pas par ou commencer, quelles sont les bonnes questions à se poser et je remarque aussi que je ne vois pas du tout l'interet de son utilisation, la suite de fibonacci et la fonction factorielle ne sont pour ma part pas des exemples pertients qui révèle tout l'interet de la recursivité.

J'aimerai que vous m'aidiez à résoudre mes problemes que je vous est exposé ci dessus (les bonnes questions a ce poser pour l'utiliser, comment doit-t-on si prendre etc ...)

Dans l'attente de réponses je vous remercie d'avance

Autres pages sur : recursivite

13 Juin 2010 19:15:01

Bonjour,

Définition : la programmation récursive est une technique de programmation qui remplace les instructions de boucle (while, for, etc.) par des appels de fonction

Exemple simple :

On appel la fonction suivante avec un "boucle(0)".
  1. void boucle(int i)
  2. {
  3. if (i < 100)
  4. {
  5. printf ("Intération n° %i\n") ;
  6. boucle(i+1) ;
  7. } //sinon on ne relance pas => fin du programme
  8. }


C'est équivalent à :
  1. for( int i=0; i<100; i++)
  2. {
  3. printf ("Intération n° %i\n") ;
  4. }


A quoi ça sert : Dans certains cas, on peut écrire un code très court et bien lisible en utilisant une procédure récursive. C'est commode pour pour les opérations qui utilisent une pile, c'est à dire en gros les parcours d'arbres etc.
La procédure récursive n'est jamais plus rapide que la procédure itérative correspondante : fondamentalement, le temps de calcul est surtout déterminé par l'algorithme, et tout algorithme peut s'écrire en itératif ou en récursif. Par contre, la pile système passe en général plus de valeurs que la pile qu'on aurait implémentée (l'adresse de retour, mais aussi les arguments supplémentaires). Elle prend donc un peu plus de temps, et surtout nettement plus de place. Il est très rare qu'on utilise une procédure récursive dans la version définitive d'un programme professionnel.

Attention : Il faut toujours réfléchir à la condition d'arrêt, dans une boucle "for" c'est facile, mais c'est le même problème avec une boucle "while", si on ne fait pas attention, on risque de boucler indéfiniment.
m
0
l
14 Juin 2010 17:31:17

Pour résumer plus clairement, la récursivité c'est une fonction qui s'appelle elle meme.

Et au contraire j'ai toujours entendu dire que les fonctions récursives son bien plus rapide que un autre code qui fait la meme chose sans récursivité.

Comment savoir quand on peut faire appel à la récursivité ?
C'est assez dur à expliquer, en gros c'est quand tu doit reproduire la meme chose un certai nombre de fois.

Par xemple lorsque tu dois parcourrir une arboressence de fichier, tu fais une fonction qui liste tous les élement d'un dossier. Sur cette fonction, lorsque tu tombe sur un dossier, tu peux refaire appel à meme. Du coup tu te retrouve avec une simple fonction assez simple qui ne fait que le parcours d'un dossier mais qui va se réappeler elle meme a chaque fois que tu vas tomber sur un autre dossier.
m
0
l
Contenus similaires
Pas de réponse à votre question ? Demandez !
14 Juin 2010 20:26:36

merci je comprend mieux, elle remplace uniquement les boucles, toutefois il est tres diffcile pour moi de la creer je sais pas pourquoi, avec l'exemple de RedSux sa n'as pas l'air compliqué mais quand il s'agit de repondre a un sujet bien precit la pour moi c'est vraiment insurmontable, auriez vous des conseils a me donné sur comment proceder pour au final faire une fonction recursive qui fonctionne ??

encore merci
m
0
l
14 Juin 2010 20:36:50

Connais tu les arbres en tant que structure de données ? On peut facilement trouver des exemples qui font bien comprendre l'intérêt de la récursivité si c'est le cas.
m
0
l
14 Juin 2010 20:50:59

non dsl sur mon livre j'en suis pas encore a la, je ne connais pas encore cette notion d'arbre mais le chapitre sur mon livre en parle (biennnnn apres la recursivité).
Est ce le meilleur moyen pour voir tout l'interêt de la recursivité ainsi que "comment s'y prendre pour en creer une de fonction recursive" ??
m
0
l
Tom's guide dans le monde
  • Allemagne
  • Italie
  • Irlande
  • Royaume Uni
  • Etats Unis
Suivre Tom's Guide
Inscrivez-vous à la Newsletter
  • ajouter à twitter
  • ajouter à facebook
  • ajouter un flux RSS