Discussion:Récursivité dans l'algorithmique et la programmation

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche


"On évite ce genre de fonction"... ahem ! Un adepte de la programmation fonctionnelle et en particulier d'OCaml ne peut pas laisser passer cela !

"On" évitera parfois ces fonctions quand le style de programmation ne s'y prête pas où lorsque l'algorithme sous-jacent s'y plie très mal, mais je pense qu’il est aventureux de généraliser.

Pourrait-on reformuler cela ?

--86.73.156.27 19 juillet 2007 à 23:30 (UTC)

Bonjour,

je trouve la définition maladroite et ne définissant que la récursivité directe. Si l’on dispose de n procédures , , ..., telles que appelle , appelle , ... , appelle , appelle , il s'agit aussi de récursivité (indirecte).

L'attention pourrait être attirée sur la notion diviser pour régner, découpage d'un problème en problèmes similaires mais de tailles inférieures ...

Cette méthode est élégante, mais il est nécessaire de rappeler que, dans la pratique, elle reste néanmoins couteuse en termes d'espace sur la pile, et qu’il est toujours possible de transformer une version récursive d'un algorithme en une version itérative (ce qui en pratique revient parfois à implémenter un mécanisme de pile sur le tas).

La condition permettant la fin des appels récursifs est en général appelée condition d'arrêt, il arrive aussi que pour un algorithme donné il y ait plusieurs conditions d'arrêts.

Il serait judicieux de donner l'exemple trivial du calcul de la factorielle (récursivité directe, une variable), du pgcd (récursivité directe, deux variables), des ou de fibonnaci simple (récursivité directe, plusieurs appels récursifs), un exemple de type Pair/Impair pour la récursivité indirecte.

À un niveau plus avancé, donner les méthodes pour dérécursiver une fonction récursive peut être intéressant, cela permettrait d'amener les notions de récursion terminale/non terminale.

Comme exemple réel, montrer une version récursive puis itérative d'un même algorithme de type quicksort ou tours de Hanoï serait une introduction intéressante à la notion de complexité.

En espérant avoir été utile, je reste à votre disposition.

--F. Nouvier 5 août 2007 à 21:54 (UTC)

Niveau de la leçon[modifier le wikicode]

Salut à tous,

Je pense que cette leçon est une leçon de niveau 0 dans le sens où c’est une leçon de base d'informatique. En effet, les niveaux scolaire sont difficiles à adapter à l'informatique puisque l'enseignement de l'informatique est très différent en fonction des pays et des cursus (université, grandes écoles, filières courtes...).

Vous en pensez quoi ?

Julien1311 discuter 1 février 2008 à 19:52 (UTC)