Discussion :

[Exomus]

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

[yahiko]

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

[Exomus]

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.

[yahiko]

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.

[Exomus]

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

[tbc92]

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.

[Exomus]

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