A propos de récursivité

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 oeut 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:

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

et même une formule explicite.

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