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

De Sciencinfolycee
Aller à : navigation, rechercher
m
m
Ligne 3 : Ligne 3 :
 
Un algorithme qui contient se définit en faisant un appel à lui-même est dite récursif. Par exemple une suite récurrente:
 
Un algorithme qui contient se définit en faisant un appel à lui-même est dite récursif. Par exemple une suite récurrente:
 
:<tt> u[n] = u[n-1] + a , u[0] = 0</tt>
 
:<tt> u[n] = u[n-1] + a , u[0] = 0</tt>
se définit ainsi et oeut se calculer opar une fonction récursive:
+
se définit ainsi et peut se calculer opar une fonction récursive:
 
: <tt> u(n) { si n > 0 renvoyer u(n - 1) + a sinon renvoyer 0 }</tt>
 
: <tt> u(n) { si n > 0 renvoyer u(n - 1) + a sinon renvoyer 0 }</tt>
ou, dans ce cas simple, par une fonction itérative:
+
ou, dans ce cas simple, par une fonction itérative (c'est à dire avec uniquement une boucle):
 
: <tt> u(n) { r = 0; pour i de 1 à n faire r = r + a; renvoyer r; }</tt>
 
: <tt> u(n) { r = 0; pour i de 1 à n faire r = r + a; renvoyer r; }</tt>
 
et même une formule explicite.
 
et même une formule explicite.
 +
 +
Certaines structures de données (par exemple une liste) se définissent aussi utilement de manière récrusive.
  
 
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 :
 
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  
+
* faire prendre conscience de l'existence de la récursivité
 +
* aider à exprimer un problème concret de manière récursive quand celà est plus aisé
 +
* montrer les problèmes posés lors d'erreur et de bugs
 +
sans aller trop loin.
 +
 
 +
[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.
 +
 
 +
[[La_récursivité_en_programmation]] Un enseignant développe en trois minutes cette notion pour donner l'idée clé.
  
 
[[Catégorie:Sélections_thématiques]]
 
[[Catégorie:Sélections_thématiques]]

Version du 9 février 2012 à 17:32

A propos de récursivité

Un algorithme qui contient se définit en faisant un appel à lui-même est dite récursif. Par exemple une suite récurrente:

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

se définit ainsi et peut se calculer opar 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écrusive.

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 celà est plus aisé
  • montrer les problèmes posés lors d'erreur et de bugs

sans aller trop loin.

La définition de wikipedia donne les idées à comprendre et un exemple . . issu de la littérature.

La_récursivité_en_programmation Un enseignant développe en trois minutes cette notion pour donner l'idée clé.