1. #1
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    février 2015
    Messages
    18
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 20
    Localisation : France, Seine et Marne (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : février 2015
    Messages : 18
    Points : 13
    Points
    13

    Par défaut Conseils pour la récursivité ?

    Bonjour,

    Je suis étudiant en informatique et j'ai souvent été rebuté par la récursivité en cours et j'ai tendance à me limiter à des solutions itératives. Je sens que c'est une notion fondamentale pour la résolution de certains types de problèmes (difficilement abordable en itératif), mais la récursivité est selon moi trop vite et trop peu abordée pendant mon cursus. C'est pourquoi je fais tous les jours quelques exercices sur la récursivité (factorielle, produit, puissance, division euclidienne...) mais je n'arrive pas toujours à formaliser mon raisonnement. Je trouve la plupart du temps une solution qui fonctionne par intuition et cela me dérange un peu puisque je ne suis pas sûr que se reposer sur de l'intuition marchera tout le temps. La seule étape que je sais indispensable, c'est la condition d'arrêt. Mais faut-il aussi définir la formule de récurrence ? Est ce toujours possible ?

    par exemple pour la factorielle, il est facile de déterminer une formule de récurrence et donc de déterminer la condition d'arrêt:
    n! = n*(n-1)!

    Avez vous une méthodologie de travail pour aborder n'importe quel problème en récursif ? Des étapes clés ?

    Merci d'avance pour votre aide et vos conseils

  2. #2
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Ninja
    Inscrit en
    juillet 2013
    Messages
    1 141
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ninja

    Informations forums :
    Inscription : juillet 2013
    Messages : 1 141
    Points : 6 521
    Points
    6 521
    Billets dans le blog
    43

    Par défaut

    L'une des principales difficultés, à mon sens, dans la représentation mentale d'un déroulement récursif, tient pour une large part au contexte d'exécution qui change à chaque appel, contrairement au cas itératif, où le contexte d'exécution reste invariant à l'intérieur de la boucle.
    Par exemple, dans le cas trivial de la factorielle fact(n), le n passé en paramètre lors du premier appel ne désigne pas le même nombre, ni même la même variable en terme d'allocation mémoire que celui du deuxième appel.
    Il faut surtout s'habituer à raisonner à l'aide d'une pile pour se sentir à l'aise avec les algorithmes récursifs. Les contextes s'empilent lors de la "descente" puis se dépilent lors de la "remonté".

    Pour ce qui est de la modélisation des problèmes, j'aurais tendance à dire que c'est souvent le problème en lui-même qui suggère fortement l'utilisation d'un algorithme récursif. Il faut alors juste déterminer le "noyau" du problème qui correspond aux opérations à réaliser dans le cas le plus trivial, à définir la manière de "descendre" (les appels récursifs à proprement parler), et bien sûr les conditions d'arrêt pour assurer la "remonté".

    Pour le cas de la factorielle.
    • Noyau : multiplication entre deux nombres
    • Descente : n * fact(n-1)
    • Conditions de la remontée : on s'arrête quand n = 0 ou 1 auquel cas on renvoie 1
    Tutoriels et FAQ TypeScript

  3. #3
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    février 2015
    Messages
    18
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 20
    Localisation : France, Seine et Marne (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : février 2015
    Messages : 18
    Points : 13
    Points
    13

    Par défaut

    Merci de ta réponse. Le problème vient peut être également des exercices pour débuter. Je ne les trouve pas forcément adaptés étant donné que l'on force un peu le problème à être raisonner en récursif (Faire une factorielle en récursif, ça n'a pas grand intérêt si on y réfléchit bien).

    Par exemple, un des problèmes qu'il était demandé de résoudre en récursif, est trouvé le quotient de la division euclidienne. J'ai trouvé par intuition le résultat mais transformer la formule de la division euclidienne (a = bq + r avec b>r) en formule récursive, ça m'a pas vraiment parlé sur le coup.
    En faisant a-b = (b-1)q + r, j'ai intuité que la condition d'arrêt "Si (a<b) alors retourner 0"
    avec l'algorithme suivant
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    Fonction DivEuc(a,b: entier): entier
    Début
    Si (a<b) alors retourner 0
    Sinon retourner 1 + DivEuc(a-b,b)
    Fin
    Mais j'ai pas vraiment l'impression que la formule de la division euclidienne même après transformation m'ait donné les billes pour mener à bien l'algorithme.

  4. #4
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Ninja
    Inscrit en
    juillet 2013
    Messages
    1 141
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ninja

    Informations forums :
    Inscription : juillet 2013
    Messages : 1 141
    Points : 6 521
    Points
    6 521
    Billets dans le blog
    43

    Par défaut

    En fait, soit le problème suggère naturellement l'algorithme récursif, soit l'algorithme récursif donne une autre manière de considérer le problème.
    Dans le cas de la division euclidienne, l'algorithme récursif permet de mettre en évidence le fait qu'une division entière revient à compter le nombre de retranchements d'un nombre par rapport à un autre.
    C'est vraiment très proche de l'esprit de la factorielle.
    Tutoriels et FAQ TypeScript

  5. #5
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    février 2015
    Messages
    18
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 20
    Localisation : France, Seine et Marne (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : février 2015
    Messages : 18
    Points : 13
    Points
    13

    Par défaut

    C'est vrai que formalisé comme cela, c'est plus clair. Il faut que je pratique davantage. Merci beaucoup de votre aide.

  6. #6
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 507
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 507
    Points : 3 147
    Points
    3 147

    Par défaut

    Quand on fait une division "à la main, à l'ancienne" (en cherchant à chaque fois le chiffre suivant) ça se prête assez bien aux fonctions récursives.

    En fait en lisant ton premier message, je me suis dit : Exomus n'a absolument pas besoin d'aide.
    Tu as clairement formulé comment marchait un algorithme récursif ... tu maîtrises parfaitement qu'il faut une condition d'arrêt.

    A mon avis, c'est un sujet que tu domines très bien.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  7. #7
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    février 2015
    Messages
    18
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 20
    Localisation : France, Seine et Marne (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : février 2015
    Messages : 18
    Points : 13
    Points
    13

    Par défaut

    Je te remercie de ton commentaire, ça me fait vraiment plaisir d'entendre ça. Alors c'est de l'expérience et un soupçon d'assurance qu'il me manque

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 3
    Dernier message: 01/07/2003, 17h04
  2. Conseils pour developper une application avec Oracle
    Par belugha dans le forum Langages de programmation
    Réponses: 5
    Dernier message: 02/06/2003, 17h03
  3. Cherche conseil pour choisir mon orientation.
    Par AslDice dans le forum Débuter
    Réponses: 6
    Dernier message: 24/04/2003, 18h07
  4. Conseils pour poser votre question...
    Par Community Management dans le forum XMLRAD
    Réponses: 0
    Dernier message: 30/01/2003, 17h58
  5. [web] Cherche un conseil pour un livre perl-tk
    Par Anonymous dans le forum Interfaces Graphiques
    Réponses: 2
    Dernier message: 29/04/2002, 16h35

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo