A propos de récursivité : Différence entre versions

De Sciencinfolycee
Aller à : navigation, rechercher
m
 
(2 révisions intermédiaires par un autre utilisateur non affichées)
Ligne 21 : Ligne 21 :
 
[http://fr.wikipedia.org/wiki/Algorithme_r%C3%A9cursif La définition de wikipedia]  
 
[http://fr.wikipedia.org/wiki/Algorithme_r%C3%A9cursif La définition de wikipedia]  
 
* donne les idées à comprendre et un exemple ... issu de la littérature.
 
* donne les idées à comprendre et un exemple ... issu de la littérature.
 +
 +
[http://www.matheprisma.uni-wuppertal.de/Module/Rekurs/index.htm Les suites récurrentes, sur MathePrisma (en allemand)]]
 +
* Cette ressource pédagogique propose un parcours très progressif depuis les suites arithmétiques jusqu'aux suites de Fibonacci.
  
 
[[La récursivité (site du zéro)]]
 
[[La récursivité (site du zéro)]]
Ligne 36 : Ligne 39 :
 
* Les L-systèmes (L comme Lindenmeyer) sont un bon exemple de structure récursive, dans le domaine de la simulation des formes végétales.  
 
* Les L-systèmes (L comme Lindenmeyer) sont un bon exemple de structure récursive, dans le domaine de la simulation des formes végétales.  
  
[[Catégorie:Sélections_thématiques]]
+
[[Backtracking_(Mathe_Prisma)|Backtracking (Mathe Prisma)]]
 +
* La récursivité apparaît naturellement dans les problèmes de parcours de graphes (ici, de labyrinthe mais c'est pareil).
 +
 
 +
[[Catégorie:PageThématique]]

Version actuelle datée du 27 février 2013 à 10:53

A propos de la récursivité

Un algorithme qui contient se définit en faisant un appel à lui-même est dit récursif. Par exemple une suite récurrente (au sens mathématique) : un = un-1 + a , u0=0 (c'est une suite arithmétique) devient (informatiquement) un tableau défini par :

u[n] = u[n-1] + a , u[0] = 0

mais peut aussi se calculer par une fonction récursive:

u(n) { si n > 0 renvoyer u(n - 1) + a sinon renvoyer 0 }

ou, dans ce cas simple, par une fonction itérative (c'est à dire avec uniquement une boucle):

u(n) { r = 0; pour i de 1 à n faire r = r + a; renvoyer r; }

et même une formule explicite.

Certaines structures de données (par exemple une liste) se définissent aussi utilement de manière récursive.

Toutes les fonctions itératives peuvent s'exprimer de manière récursive, mais l'inverse n'est pas vrai. C'est un domaine très théorique, et au niveau de l'enseignement secondaire, il est sûrement important de :

  • faire prendre conscience de l'existence de la récursivité
  • aider à exprimer un problème concret de manière récursive quand cela est plus aisé
  • montrer les problèmes posés lors d'erreur et de bugs

sans aller trop loin.

Quelques liens :

La définition de wikipedia

  • donne les idées à comprendre et un exemple ... issu de la littérature.

Les suites récurrentes, sur MathePrisma (en allemand)]

  • Cette ressource pédagogique propose un parcours très progressif depuis les suites arithmétiques jusqu'aux suites de Fibonacci.

La récursivité (site du zéro)

  • Les points clés y sont donnés pour programmer des fonctions récursives en «pigeant» ce qui se passe.

La récursivité en programmation

  • Une enseignante développe en trois minutes cette notion à partir de du problème des tours de Hanoï pour donner l'idée clé.

Les tours de Hanoï

  • Un texte introductif sur le site du Zéro.

Les suites de Syracuse sont un autre exemple de situation naturellement récursive.

L-Py

  • Les L-systèmes (L comme Lindenmeyer) sont un bon exemple de structure récursive, dans le domaine de la simulation des formes végétales.

Backtracking (Mathe Prisma)

  • La récursivité apparaît naturellement dans les problèmes de parcours de graphes (ici, de labyrinthe mais c'est pareil).