La récursivité

Les algorithmes récursifs

Pour utiliser un exemple simple d'un algorithme récursif, prenons l'opération arithmétique factorielle :
La factorielle1 d'un nombre naturel n (notée : n!) est le produit des tous les nombres naturels plus petits ou égal à n.
Ainsi, n!= n x (n-1) x (n-2) x ... x 3 x 2 x 1.
Par exemple, 6! = 6x5x4x3x2x1 = 720. (1!=1, 2!=2, 3!=6, 4!=24, etc.)
L'algorithme du calcul d'une factorielle est simple :
Multiplier n par n-1 ensuite, multiplier le résultat précédent par n-2, etc. jusqu'à multiplier le dernier résultat par 1.

Cette opération peut être définie de façon récursive comme suit :
1! = 1 et n! = n x (n-1)! pour n>1.
La récursivité est dans le fait que pour obtenir la factorielle d'un n>1, il faut obtenir la factorielle de n-1 et si n-1 > 1 il faut obtenir celui de n-1-1 et ainsi de suite jusqu'à ce qu'on arrive à n-1...-1 = 1. Comme on commence nécessairement par un n>1 et qu'on soustrait de 1 à chaque fois, on est sûr de finir par arriver à 1! et donc que l'algorithme va finir par s'arrêter.

Remarque importante : la définition récursive est plus simple, assure l'arrêt de l'algorithme mais est plus abstraite. De plus, l'algorithme qui en résulte est aussi plus complexe.

En effet, si on appliquait cette définition récursive pour calculer 6!, on exécuterait l'algorithme suivant :
6! = 6x(6-1)! = 6x5! : il faut donc noter cette multiplication puis calculer 5!
5! = 5x(5-1)! = 5x4! : il faut donc aussi noter cette multiplication puis calculer 4!
...
2! = 2x(2-1)! = 2x1! : on note cette multiplication puis on calcule 1!
Comme on a 1!=1 on effectue donc 2! = 2x1 = 2 qui est la dernière multiplication notée
Comme on obtient 2!=2 on effectue donc 3! = 3x2 = 6 qui est l'avant dernière multiplication notée
...
Comme on obtient 5!=120 on effectue donc 6! = 6x120 = 720, la première multiplication notée

On constate qu'on prend note des multiplications dans l'ordre de la définition de la factorielle puis on les effectuent dans l'ordre inverse. Il a fallu empiler les notes de multiplication puis les exécuter en les dépilant. Il serait donc absurde de calculer une factorielle de cette manière plutôt compliquée. C'est parce que la définition récursive est plus simple et plus sûre qu'elle est utile en informatique. Nous allons voir comment.

Notes

1. Cette opération est très utilisée pour calculer les probabilités.

Un autre exemple d'un objet mathématique récursif est la suite de Fibonacci :
1, 1, 2, 3, 5, 8, 13, etc. où chaque nombre de la suite est la somme des 2 précédents.
La définition récursive est donc : F(1) = 1, F(2) = 1 et F(n) = F(n-1) + F(n-2) pour n > 2 où le nombre entre parenthèses indique la position dans la suite.
Par exemple : F(6) = F(5) + F(4) = 5 + 3 = 8

L'article "Langages et récursivité" par Hervé Lehning du Hors Série N°52 cité dans les sources ci-après présente un algorithme récursif de tri d'une liste de nombres.

En informatique

Un programme d'ordinateur est un algorithme destiné à être exécuté par un ordinateur.
Pour être exécutées par un ordinateur, ces instructions doivent être écrites dans un langage de programmation compréhensible par l'humain et par l'ordinateur. Il faut savoir que ces instructions sont ensuite "compilées" par l'ordinateur i.e. traduites en instructions que son processeur peut exécuter. Ces instructions en langage machine sont plus élémentaires et ne font pas de récursivité !

Dans un programme dont le langage utilisé n'a pas l'opération factorielle, celle-ci peut être réalisée par une partie du programme qui sera répétée en boucle1. Voici un exemple de programme écrit dans un langage non informatique qu'on appelle du pseudo-code :

1. Obtenir le nombre (que fournit l'utilisateur) et le stocker dans la variable Nbre (i.e. le mettre en mémoire)
2. Vérifier que c'est un nombre naturel {1, 2, 3, ...}
3. Le stocker dans la variable Fact (Fact = Nbre)
4. Si Nbre = 1 alors afficher la valeur de Fact (qui est le résultat)
Sinon
5. Soustraire 1 de Nbre (Nbre = Nbre - 1)
6. Multiplier Fact par Nbre et le stocker dans Fact (Fact = Fact x Nbre)
7. Retourner à l'instruction 4.

On voit que ce programme exécute une boucle (de 4 à 7) qui est une suite d'instructions que l'on répète sous une certaine condition. Ici la condition est que Nbre = 1 ou pas.

En programmation, il arrive souvent qu'on ait besoin d'exécuter une même suite d'instructions à différents endroits du programme. On écrit alors cette suite d'instructions une seule fois dans ce qu'on appelle un sous-programme pour ensuite le faire exécuter aux endroits où on en a besoin.

La partie de l'algorithme précédent qui fait le calcul de la factoriel ferait normalement l'objet d'un sous-programme. Un sous-programme peut être récursif en faisant appel à lui-même. 

Voici un exemple de calcul de factorielle écrit dans le langage de programmation Basic2 en utilisant un sous-programme récursif :
(En Basic, les instructions ("lignes de code") doivent être numérotées pour pouvoir y référer.
Pour simplifier l'exemple, le programme ne vérifie pas que l'utilisateur fournit bien un nombre naturel.)

10 input "nbre : ", nbre
15 fact = nbre
20 gosub 100
30 print fact
99 end
100 if nbre = 1 then goto 999
200 nbre = nbre - 1
300 fact = fact * nbre
400 gosub 100
999 return

L'instruction input ("entrée") demande à l'utilisateur de saisir ce qui est indiqué entre les guillemets et le stocke dans la variable indiquée après la virgule.
L'instruction print ("sortie") affiche ce qui est indiqué après le print.
L'instruction gosub (go to subprogram) signifie "aller au sous-programme" qui débute par le numéro de ligne indiqué et retourne à l'instruction qui suit ce gosub lorsque l'instruction return est atteinte. A l'exécution du gosub, l'ordinateur note son numéro de ligne pour pouvoir aller à l'instruction qui suit ce gosub lorsque le return sera exécuté.
L'instruction if x then y signifie : si x est vrai alors exécute y sinon passe à l'instruction suivante.
L'instruction goto (aller à) fait passer l'exécution du programme à la ligne indiquée.
L'instruction end termine le programme.

On peut remarquer que le gosub qui induit la récursivité, celui de la ligne 400, est la dernière instruction du sous-programme. C'est un cas particulier qu'on appelle la récursivité terminale. Nous y reviendrons.

Voici comment l'ordinateur exécutera ce programme si le nombre saisi est 1 :

10 : mettre 1 dans nbre (nbre=1) ; 15 : mettre ce 1 dans fact (fact=nbre=1)
20 : noter ce numéro de ligne du gosub puis aller à la ligne 100
100 : comme nbre=1 est vrai, aller à 999
999 : aller à la ligne suivante du gosub qui est 30
30 : afficher 1 car fact=1, ce qui est juste car 1! =1
99 : terminer le programme.

Voici comment l'ordinateur exécutera ce programme si le nombre saisi est 3 :

10 : ... nbre = 3 ; 15 : ... fact = 3 (= nbre)
20 : noter l'exécution de ce gosub dans la "pile* des gosub" (Pile=[20]) puis aller à 100
100 : comme nbre=1 est faux (nbre = 3), aller à la ligne suivante
200 : nbre = 2 (nbre-1) ; 300 : fact = 6 (fact x nbre) (3x2)
900 : noter l'exécution de ce gosub dans la pile des gosub (Pile=[900, 20]) puis aller à 100
100 : comme nbre=1 est faux (nbre = 2), aller à la ligne suivante
200 : nbre = 1 (nbre-1) ; 300 : fact = 6 (fact x nbre) (6x1=6)
900 : noter l'exécution de ce gosub dans la pile des gosub (Pile=[900, 900, 20]) puis aller à 100
100 : comme nbre=1 est vrai, aller à 999
999 : supprimer le 1er élément de la pile (900 -> Pile=[900, 20]) puis aller à la suivante de 900
999 : supprimer le 1er élément de la pile (900 -> Pile=[20]) puis aller à la suivante de 900
999 : supprimer le 1er élément de la pile (20 -> Pile=[vide]) puis aller à la suivante de 20
30 : afficher 6 car fact=6, ce qui est juste car 3! = 3x2x1 = 6
99 : terminer le programme.

* Une pile est une mémoire structurée qui stocke des valeurs dans l'ordre inverse où elles y sont ajoutées comme une pile d'assiettes. Ainsi, la dernière valeur ajoutée est mise en premier dans la pile comme la dernière assiette est mise sur le dessus la pile. Lorsqu'un gosub est exécuté, son numéro de ligne est entré dans le dessus de la pile des gosub. Lorsqu'un return est exécuté, il supprime la valeur du dessus de la pile puis l'exécution se poursuit à la ligne qui suit immédiatement celle-ci.

Bien que le sous-programme en Basic soit récursif, il ne l'est pas comme la définition récursive de factorielle qui est : « 1! = 1 et n! = n x (n-1)! pour n>1 ». Ce sous-programme exécute la factorielle selon sa définition arithmétique qui est : « n! = n x (n-1) x (n-2) x ... x 3 x 2 x 1 ». En effet, on peut constater qu'il commence par multiplier n par n-1 puis par n-2 et ainsi de suite jusqu'à 1 alors que selon sa définition récursive, il doit d'abord exécuter la factorielle de n-1 et pour celle-ci exécuter celle de n-2 et ainsi de suite.

Nous allons voir comment les langages modernes permettent 1programmer un sous-programme tel que sa définition récursive en très peu d'instructions.

Notes

1. Les boucles sont très utilisées en programmation comme par exemple, pour exécuter les mêmes instructions sur chaque donnée d'un ensemble. On dit qu'il s'agit d'un processus itératif où chaque exécution de ces mêmes instruction est une itération.

2. Tous les algorithmes de cet article écrit en Basic ont été testés avec Chipmunk Basic (http://www.nicholson.com/rhn/basic/). Une application pour programmer en Basic est facile à utiliser. 

Avec les langages fonctionnels

Une fonction informatique est un sous-programme auquel on donne un nom pour qu'une instruction puisse l'appeler et on y indique les données dites "en entrée" qu'il faut lui fournir ainsi que le type de résultat qu'il retourne à l'instruction qui l'a appelé. Les langages dit "fonctionnels" permettent de programmer des fonctions. Ces langages permettent habituellement que leurs fonctions soient récursives en s'appelant elles-mêmes.

Lorsque le langage de programmation permet les fonctions récursives1, l'opération factorielle peut être programmée selon cet algorithme :

Fonction Factorielle(n) :
    Si n = 1 alors retourner 1
    Sinon retourner n x Factorielle(n-1)

En langage Python, elle est programmée comme suit :
def factorielle(n):
  if n==1: return 1
  else: return (n * factorielle(n-1))
Pour obtenir la factorielle d'un nombre dans un programme en Python, il suffirait d'écrire une instruction comme : fact = factorielle(nbre). Les instructions de cette fonction correspondent exactement à la définition récursive de l'opération :
1! = 1 et n! = n x (n-1)!

On constate que cette fonction récursive est plus simple que le sous-programme 100-999 en Basic. Les fonctions récursives permettent de programmer des boucles plus simplement et d'éviter facilement de programmer une boucle sans fin, ce qui arrive régulièrement.

Cependant, un ordinateur ne peut pas exécuter une fonction récursive telle quelle. Pour être exécutée, la fonction doit être transformée en un sous-programme non récursif en utilisant une pile comme le fait Basic pour les gosub. Par exemple, lorsqu'un programme appelle Factorielle(3), l'ordinateur exécuterait les étapes suivantes :

Factorielle(3) : il ne fait que mettre 3 dans une pile car il a besoin du résultat de Factorielle(2) puis appelle
Factorielle(2) : il met donc 2 dans la pile pour la même raison puis appelle
Factorielle(1) : il retourne 1 qui est le factoriel de 1 puis
Multiplie ce 1 par le 2 de la pile pour exécuter Factorielle(2) qui retourne 2 (2xFactorielle(1)) puis
Multiplie ce 2 par le 3 de la pile pour exécuter Factorielle(3) qui retourne 6 (3xFactorielle(2)).

On peut remarquer que le calcul de la factorielle n'aura été exécutée qu'à partir du moment où on arrive à la factorielle de 1 qui déclenche la série de multiplications comme dans la boucle en langage Basic. Les langages fonctionnels doivent donc transformer la fonction en boucles habituellement non récursives.  Utilisons le langage Basic pour illustrer comment les instructions récursives de la factorielle serait transformées :

10 input "nbre ? : ", nbre
12 dim pile(nbre)
13 nbrin = nbre
20 while nbre > 1
21 pile(nbre) = nbre
22 nbre = nbre-1
29 wend
31 fact = nbre
32 print "factorielle(1) = ",  fact
40 while nbre < nbrin
41 nbre = nbre+1
42 fact = fact * pile(nbre)
49 wend
50 print "factorielle(", nbrin, ") =", fact

L'instruction dim crée une variable à valeurs multiples dont le nombre de valeurs est indiqué entre les parenthèses et dont chacune est identifiée par un index qui va de 1 au nombre de valeurs.
L'instruction while (= "tant que") fait exécuter les instructions qui la suivent jusqu'à l'instruction wend tant que la condition indiquée (ici "nbre > 1") est satisfaite.

L'instruction 12 crée une variable multiple pour servir de pile.
L'instruction 13 garde le nombre saisi par l'utilisateur dans la variable nbrin.
Les instructions 20 à 29 accumulent les nombres dans la pile.
Les instructions 31 et 32 produisent la factorielle de 1 qui est le dernier nombre résultant de la boucles des instructions 20 à 29.
Les instructions 40 à 49 calculent les factorielles des nombres mis dans la pile.

Les compilateurs de langages fonctionnels savent transformer les fonctions en boucles de type "tant que".  Cette transformation traduite en Basic donnerait :

10 input "nbre : ", nbre
20 fact = nbre
30 while nbre > 1
40 nbre = nbre - 1
50 fact = fact * nbre
99 wend
100 print "factorielle = ", fact

Cette boucle avec un while ressemble au gosub récursif du premier exemple. L'avantage du gosub récursif est qu'il peut être appelé à différents endroits du programme comme les fonctions.

Notes

1. L'autre exemple d'objet récursif est la suite de Fibonacci. Il y a 2 fonctions différentes que l'on peut définir pour cette suite :

1) La récursive où elle donne la valeur dans la suite d'une position en particulier :
Pour la position n : F(1) = 1, F(2) = 1 et F(n) = F(n-1) + F(n-2) dont la fonction est :
Fibonacci(n) :
    Si n = 1 alors retourner 1
    Si n = 2 alors retourner 1
    Sinon retourner Fibonacci(n-1) + Fibonacci(n-2)

Celle-ci peut être programmée en Basic* en utilisant un sous-programme récursif comme suit :

10 input "n : ", n
20 if n = 1 then print "Fib(1) = 1" : end
30 if n = 2 then print "Fib(2) = 1" : end
40 dim sfib(n) : sfib(1) = 1 : sfib(2) = 1
50 pos = 2 "pos = position dans la suite"
60 gosub 100
70 print "Fib(", n, ") = ", sfib(n)
99 end
100 if pos = n then return
200 pos = pos + 1
210 pos_1 = pos - 1 : pos_2 = pos - 2
300 sfib(pos) = sfib(pos_1) + sfib(pos_2)
400 gosub 100
999 return

* Les langages Basic qui ont une instruction pour définir une fonction, celle-ci ne peut être qu'une opération arithmétique aussi complexe soit-elle.

2) La non récursive où elle donne toutes les valeurs de la suite jusqu'à l'atteinte d'une valeur maximale :
Pour la valeur n, l'algorithme est :
Fibonacci(n) :
    a = 1, b = 1
    Tant que a < n :
          Retourner a, c = a,  a = b, b = c + b
Pour n = 100, au obtiendrait : 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

Elle peut être programmée en Basic en utilisant une boucle comme suit :

10 input "n : ", n
20 a = 1 : b = 1
100 while a < n
110 print a
120 c = a : a = b : b = c + b
199 wend

Sources

Hors Série N° 52, Mathématiques & informatique, Bibliothèque Tangente, Éditions POLE, juillet 2014
(https://www.poleditions.com/publications.php?collection=Bibliothèque Tangente)

Hors Série N° 29, Processus itératifs Récurrence, récursivité, revue tangente, Éditions POLE, novembre 2020
(https://www.poleditions.com/publications.php?collection=Tangente HS kiosque)

Le site Internet du langage Python : www.python.org

La documentation de Chipmunk Basic : www.nicholson.com

Wikipédia en anglais