Algorithme récursif

Modèle:SérieLangagesInfo Les algorithmes récursifs ou fonctions récursives sont fondamentaux en informatique et correspondent à l'idée d'une fonction qui s'appelle elle même.

Nous en donnons ici une approche intuitive pour ensuite nous intéresser au formalisme rigoureux qui définit cette notion.

Approche intuitive

Prenons l'exemple de la factorielle. Celle-ci se définit intuivivement pour des entiers positifs par la fonction suivante:

$n!=\prod _{i=1}^{n}i=1\times 2\times 3\times \cdots \times (n-1)\times n$

L'idée de la récursivité est d'utiliser une définition équivalente par une suite récurrente:

$n!={\begin{cases}1{\mbox{ si }}n=0\\n\times fact(n-1){\mbox{ sinon}}\end{cases}}$

Ceci peut alors se traduire par le programme suivant en pseudo-langage:

factorielle(entier k):
si k=0
 alors renvoyer 1
 sinon renvoyer k * factorielle(k-1)
finsi

Tous les langages de programmation modernes proposent une implémentation de la récursivité. Nous en donnons ici un exemple en Caml:

let rec factorielle n=function
|0->1
|n->n*factorielle(n-1);;

Ici, on note que préciser que factorielle(0)=1 est fondamental: sans lui l'algorithme s'appelle indéfiniment. Le cas n=0 est aussi appelé cas de base, sans lui l'algorithme ne peut terminer. On peut programmer ainsi d'autres suites telles que la suite de Fibonacci ou la suite de Syracuse.

Mais les algorithmes récursifs ne se limitent pas à de telles applications et permettent de travailler sur des structures de données définies récursivement, ou plus généralement sur des ensembles munis d'une relation bien fondée.

Définition

Soit $\mathrm {A}$ un ensemble sur lequel est définie une relation d'ordre $\leq$ bien fondée.

Voir aussi