A propos de récursivité
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.
- donne les idées à comprendre et un exemple ... issu de la littérature.
- 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 pour donner l'idée clé.
