Compréhension de la récursivité  
Considérons la définition suivante:  
 
Une telle définition (où la fonction à définir est utilisée dans le corps de la définition) est une définition récursive.
 
Évaluons, en pas à pas, (! 3)
 
(! 3)  
(if (= 3 1) 1 (* 3 (! (- 3 1))))  
(if false 1 (* 3 (! (- 3 1))))  
(* 3 (! (- 3 1)))  
(* 3 (! 2))
 
(* 3 (if (= 2 1) 1 (* 2 (! (- 2 1)))))
 
(* 3 (if false 1 (* 2 (! (- 2 1)))))
 
(* 3 (* 2 (! (- 2 1))))
 
(* 3 (* 2 (! 1)))
 
(* 3 (* 2 (if (= 1 1) 1 (* 1 (! (- 1 1))))))
 
(* 3 (* 2 (if true 1 (* 1 (! (- 1 1))))))
 
(* 3 (* 2 1))
 
(* 3 2)  
6  
Ainsi, l'évaluation de (! 3) rend 6 qui est bien égal à factorielle de 3.
 
Pourquoi « ça marche »?

1. lorsque n n'est pas égal à 1, n! est égal à n × (n-1)!
    
   (nécessaire car, intuitivement, dans le calcul précédent, nous disons que 3! est égal à 3 × (3-1)! et que 2! est égal à 2 × (2-1)! puisque nous remplaçons 3! par 3 × (3-1)! et 2! par 2 × (2-1)!),
2. 1! est égal à 1 (nécessaire car, intuitivement, dans le calcul précédent, nous disons que 1! est égal à 1 puisque nous remplaçons 1! par 1),
3. n-1 est strictement plus petit que n.
    
   Par exemple, si l'on n'imposait pas cette condition, on pourrait donner comme définition de factorielle:
    
   
   (define (! n)
        (/ (! (+ n 1)) (+ n 1)))
   
   mais alors le calcul serait
    
   (! 2)  
   (/ (! (+ 2 1)) (+ 2 1))  
   (/ (! 3) (+ 2 1))
    
   (/ (/ (! (+ 3 1)) (+ 3 1)) (+ 2 1))
    
   (/ (/ (! 4) (+ 3 1)) (+ 2 1))
    
   ...  
   et on pourrait attendre longtemps le résultat!

Pour en savoir plus: Domaine bien fondé

 
Écriture d'algorithmes récursifs  
Dans cette section, nous étudions comment on peut écrire, en général, une définition récursive. Pour ce faire, nous allons donner deux exemples d'écritures de définitions récursives puis nous synthétiserons une méthode de travail.
 
En fait, les deux exemples sont deux algorithmes différents de la même fonction, la fonction qui, à deux entiers naturels n et m, associe l'entier naturel n^m.
 
Premier algorithme  
Idée de départ: n^m est égal à n × n^m-1. Mais peut-on dire que n^m = n × n^m-1 (sous-entendu pour tout entier naturel n et tout entier naturel m)? Non car l'égalité est fausse lorsque m est égal à 0 (-1 n'appartient pas aux entiers naturels !). Nous devons donc « enlever » de l'appel récursif le cas où m est nul. Pour ce faire nous utilisons une alternative (if (= m 0) ...) et, pour écrire le conséquent, nous remarquons que n⁰ est égal à 1. La définition est donc  
 

 
Remarque: avec cet algorithme, l'évaluation de n^m est effectué avec m multiplications.
 
Second algorithme  
Idée de départ:

• lorsque m est pair, n^m est égal à (n^{m ÷ 2})²,
• lorsque m est impair, n^m est égal à n × (n^{m ÷ 2})²

 
On a ainsi des égalités où les futurs appels récursifs sont effectués sur des valeurs plus petites (m ÷ 2 est plus petit que m). Est-ce que ces égalités sont toujours vraies? Oui. Peut-on écrire
 

comme définition? Non! car pour m nul, m ÷2 est égal à 0 soit à m et n'est donc pas strictement plus petit que m: il faut encore « enlever » 0 du cas général. La bonne définition est donc:  
 

 
avec la fonction carre spécifiée par:  

 

 
et que vous pouvez implanter en exercice.
 
Remarque: avec cet algorithme, lors de l'évaluation de n^m le nombre de multiplications est égal au nombre de fois que l'on peut effectuer l'opération diviser m par 2, puis le résultat obtenu par 2, puis le résultat obtenu par 2... jusqu'à trouver 0: il est, grosso modo, égal au logarithme en base 2 de m, nous dirons qu'il est de l'ordre de lg(n).
 
Terminologie: dans l'appel récursif, on divise par deux une donnée: on dit que l'on travaille par dichotomie.
 

Pour en savoir plus: Encore une autre façon de faire

 
Méthode de travail  
Supposons que l'on veuille implanter la fonction
 
F: X --> Y

F(x) est égal à f(x)

Pour écrire une définition récursive, on doit suivre la méthode suivante:

1. Décomposer la donnée (x étant la donnée, d₁(x)... sont des éléments de X « plus petits » que x).
2. Écrire la relation de récurrence, c'est-à-dire une égalité qui est vraie (presque toujours) entre f(x) et une expression (dite de récurrence) qui contient des occurrences de f(d_i(x)).
3. Déterminer les valeurs (« de base ») pour lesquelles:
   1. l'égalité est fausse; en particulier, regarder quand l'expression de récurrence n'est pas définie;
   2. les valeurs d_i(x) ne sont pas strictement « plus petites » que x; en particulier, regarder si d_i(x) peut être égal à x.
4. Déterminer la valeur de la fonction f pour les valeurs de base.

 
Remarque: Dans les explications précédentes, « f » est une fonction connue, c'est-à-dire que l'on peut, pour toute valeur x de X dire quelle est la valeur de f(x). En général, nous nommerons de la même façon la fonction à implanter. Ici, nous réservons le « f » minuscule pour la spécification et le « F » majuscule pour le nom de la fonction que l'on implante afin de bien voir que l'on raisonne sur la spécification et non sur l'implantation.