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

	Récursivité dans l'algorithmique et la programmation fait partie de la faculté de Informatique et du projet Informatique. Si vous voulez participer, vous pouvez modifier cette leçon ou visiter la page du projet où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Vous pouvez aussi créer des exercices pour cette leçon.
Presque complet	Cette leçon a été classée comme d'avancement presque complet selon les critères d'évaluation de Wikiversité.

"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 $P_{0}$, $P_{1}$, ...,$P_{n-1}$ telles que $P_{0}$ appelle $P_{1}$, $P_{1}$ appelle $P_{2}$, ... , $P_{n-2}$ appelle $P_{n-1}$, $P_{n-1}$ appelle $P_{0}$, 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 $C_{n}^{p}$ 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

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)