Fonctions récursives

Une fonction récursive est une fonction qui ``s'appelle elle-même'' dans sa définition. Considérons la fonction factorielle :

fact(0) = 1
fact(1) = 1
fact(2) = 1 * 2
fact(3) = 1 * 2 * 3
fact(4) = 1 * 2 * 3 * 4
...

Une définition mathématique possible de la factorielle est la suivante :

Pour tout n entier positif:
  fact (0) = 1
  fact (n) = n * fact (n - 1)

Cette expression signifie ``Quel que soit n, entier positif ou nul, la factorielle de zéro vaut un, et la factorielle de tout autre nombre vaut ce nombre multiplié par la factorielle de ce nombre diminué de un ''.

Cette définition est récursive car la factorielle de tout nombre strictement positif est exprimée en fonction de la factorielle elle-même.

La fonction factorielle pourrait s'écrire en Scheme comme cela :

(define (factorielle n)
 (if (zero? n)
   1
   (* n (factorielle (- n 1)))))

Pour être exact, il faudrait tester si n est bien un entier positif ou nul, et provoquer une erreur dans le cas contraire.

On remarque que le nom factorielle est utilisé dans le corps de la fonction factorielle elle-même, ce qui indique une récursivité.

La plupart des langages de programmation qui possèdent la notion de fonction permettent d'écrire des fonctions récursives. C'est le cas de Pascal, C, Lisp, Scheme, Eiffel. Par contre, Basic, dans les premières versions, ne le permet pas, tout comme les langages d'assemblage classiques.