Omniprésents dans le domaine de l'intelligence artificielle ou des fractales, les algorithmes récursifs constituent une part importante de l'algorithmique. Nous faisons connaissance avec quelques unes de leurs particularités.

Dans notre introduction à l'algorithmique du mois dernier nous ne nous sommes intéressés qu'à une catégorie bien définie d'algorithmes: les algorithmes itératifs. Ces algorithmes, comme leur nom l'indique, sont codés avec des boucles. Cette approche est la plus évidente pour le débutant en programmation, notamment parce que, traditionnellement, l'apprentissage d'un langage présente le codage des boucles en premier lieu. Ouvrez par exemple un ouvrage d'initiation à C ou Java. Tout l'arsenal des boucles for, while y sera passé en revue et après cela il sera mentionné que le langage supporte la récursivité. Vous y verrez l'inévitable fonction de calcul d'une factorielle, probablement pauvrement codée. Ainsi en vat- il dans le monde des langages impératifs et/ou objets tels que C, C++, C#, Java, etc. Dans le monde des langages fonctionnels, moins largement connus, les choses vont autrement. En effet des langages comme Haskell ou Erlang ne disposent tout simplement pas d'instructions de boucle telles que for ou while. Et même l'affectation de variable est interdite. Ainsi, voudrait on avoir un compteur de boucle i que la ligne de code i=i+1 ne pourrait tout simplement pas exister. Peut-on seulement programmer quelque chose avec un langage qui ne connaît pas les boucles et les affectations ? Cela paraît impossible.