Adhérer ou faire un don

La récursivité ou l’algorithmique sans boucle

Roger Cuppens

Cuppens Roger

Résumé de l’article

L’algorithmique est essentiellement l’étude des boucles de calcul. Après avoir montré qu’il existe une méthode pour "calculer sans boucle", initiée par Alonso Church, l’article donne plusieurs exemples : la factorielle, la puissance, la suite de Fibonacci, le calcul du PGCD, les listes, la récursivité en arithmétique avec l’arithmétique de Peano. Il explicite le modèle simple de numération appelé "système buchettes", réalisable avec l’ordinateur, puis il passe à quelques algorithmes irrationnels : le calcul des décimales de e, la méthode de Newton, la racine carrée. Pour les calculs avec machine il donne en exemple la factorielle, le nombre e, la suite de Fibonacci, l’algorithme d’Archimède, la méthode de Newton, l’algorithme de Héron. Si cette méthode est très souvent applicable, néanmoins certains algorithmes simples peuvent donner des calculs trop longs. On note aussi que pour certains problèmes simples à priori il n’existe pas d’algorithme.

Plan de l’article

  • Introduction
  • 1. Le calculable
  • 2. Premiers exemples
  • 3. Les listes
  • 4. La récursivité en arithmétique
  • 5. Quelques algorithmes irrationnels
  • 6. Les calculs avec une machine
  • Conclusion
  • Bibliographie

- Télécharger l’article en pdf dans son intégralité

(Article mis en ligne par Armelle BOURGAIN)