Les nouvelles technologies pour l’enseignement des mathématiques
Intégration des TICE dans l’enseignement des mathématiques

MathémaTICE, première revue en ligne destinée à promouvoir les TICE à travers l’enseignement des mathématiques.

Récursivité en programmation et récurrence en mathématiques

Cet article propose une réflexion modeste quant à la comparaison et à l’utilisation d’algorithmes en mode itératif ou en mode récursif. Les langages Python 3 et PHP sont utilisés dans cet article afin de programmer les algorithmes.

Article mis en ligne le 1er juillet 2019
dernière modification le 2 septembre 2019

par Fabrice Houpeaux

Cet article peut être librement diffusé et son contenu réutilisé pour une utilisation non commerciale (contacter les auteurs pour une utilisation commerciale) suivant la licence CC-by-nc-sa

Un article du même auteur

Introduction de l’article

À un moment, dans sa vie, on rencontre une situation récursive. De mémoire, en ce qui me concerne, ce fut avec le jeu des échecs : vous avez un état de départ puis vous allez avoir un autre état en fonction des coups joués. Outre les schémas connus de parties jusqu’à certains coups, il convient de dérouler les séquences possibles en fonction de votre coup ou du coup de l’autre. J’ai toujours été un piètre joueur, mon cerveau n’étant pas très enclin à la récursivité.

Lire la suite de l’introduction

La récursivité en algorithmique et la récurrence en mathématiques (l’arithmétique) peuvent être très liées.

Dans cet article, la plupart des exemples seront donnés en langage Python 3 et en PHP.

  • Python 3 : c’est le langage officiel dans l’Éducation nationale au secondaire. C’est un langage lisible, libre, portable et pérenne  ;
  • PHP : ce langage sert très peu pour les mathématiques mais son fonctionnement spécifique à base de formulaire est intéressant, on pourra comparer avec Python 3 pour le calcul numérique  ; de plus, le langage PHP intervient dans la spécialité NSI en classe de première, notamment avec les méthodes GET et POST.

Il n’y aura pas de fioritures dans les programmes :

  • pas de gestion d’erreurs quant à la valeur des données ou des paramètres passés aux fonctions  ;
  • pas de CSS pour les fichiers en PHP, les exemples tiennent, pour chacun, en un seul fichier, fichier contenant la fonction mathématique, le formulaire et le traitement du formulaire  ;
  • quand une liste est attendue en entrée, elle est mise « en dur » dans le programme.

Bien évidemment, si vous voulez tester les exemples en Python 3, il convient d’avoir un environnement Python local ou en ligne et si vous voulez tester les fichiers PHP, il convient d’avoir un serveur web local ou en ligne.

Il peut être intéressant d’utiliser Python tutor afin de comprendre l’exécution de certains programmes au niveau de la pile d’exécution, de la mémoire, du nombre d’instructions.

Les objectifs de cet article sont multiples mais ciblés :

  • retours utiles sur la récurrence en mathématiques  ;
  • quelques exemples de situations en récursivité « simple »  ;
  • récursivité simple et pile d’exécution  ;
  • utilité et fonctionnement de la récursivité terminale.

Quelques remarques en amont de l’article

  • contrairement à Python 3 qui, nativement, travaille en valeur exacte avec des « grands » entiers, ce n’est pas le cas de PHP  ; afin d’arriver à des résultats similaires à Python 3 sur ce point, il convient d’installer la bibliothèque  BCMath qui donne accès à des fonctions plus avancées quant aux calculs avec des grands nombres (de type int ou float). Les deux fonctions qui nous intéresseront dans ces exemples seront bcadd et bcmul qui respectivement additionnent et multiplient les deux nombres passés en paramètres. Aussi ces fonctions de calcul seront-elles utilisées dans les programmes en PHP.
    Par exemple, $product *= $i; ou $product= $product * $i; s’écriront $product=bcmul($product,$i);
  • afin de ne pas alourdir le corps de l’article, seules les fonctions intéressantes y seront copiées en PHP. Tous les programmes copiés, cités ou utilisés en vidéo sont téléchargeables en bas de l’article  ;
  • dans cet article, l’exécution de la plupart des programmes sera montrée en vidéo (si les chiens de mon voisin le permettent)  ;
  • dans les vidéos, il peut y avoir l’utilisation du terme récursivité à la place de récursion : la récursivité est le fait d’être récursif (s’appeler soi-même), la récursion est un appel de la fonction récursive dans la récursivité. On peut donc, par exemple, parler du nombre de récursions dans une récursivité.
  • enfin, depuis Python 3.6, on peut concaténer l’affichage de texte et de variable sans passer par la méthode format() :

n et m étant des variables

print('J'aime bien {chose1} mais je n'aime pas {chose2}.'.format(chose1=n,chose2=m))

peut s’écrire

print(f'J'aime bien {n} mais je n'aime pas {m}.')

C’est le principe des f-strings et c’est plutôt pratique, mais il convient de ne pas oublier le « f » devant la chaîne de caractères.

Quelques exemples de situations en récursivité « simple »

On va partir sur quatre exemples plutôt classiques :

  • la factorielle de $n$ : $u(0) = 1$ et pour $n \geqslant 1$, $u(n) = n \times u(n-1)$  ;
  • le nombre minimal de parties d’échecs à effectuer afin que dans un tournoi, les $n$ joueurs se soient tous rencontrés : pour $n \geqslant 2$ et en notant $P(n)$ le nombre de parties à effectuer, on a relativement facilement que $P(2) = 1$ et pour $n \geqslant 3$, $P(n) = P(n-1) + (n-1)$  ;
  • le PGCD de deux nombres entiers non tous deux nuls  ;
  • la suite de Fibonacci : $u(0) = 0$, $u(1) = 1$ et pour $n \geqslant 2$, $u(n) = u(n-1) + u(n-2)$  ;

Pour la factorielle, les échecs et Fibonacci, on va calculer le terme de rang $n$, pour le PGCD, on va calculer le PGCD, le tout, dans un premier temps, en itératif et en récursivité simple.

La factorielle

En itératif en Python 3

def Factorial(n):
        if n==0:
                return 1
        else:
                product=1
                for x in range(1,n+1):
                        product=x*product
                return product

n=int(float(input('Entrez votre entier positif : \n')))
print(f'La factorielle de {n} est {Factorial(n)}.')

En itératif en PHP

<?PHP  
function Factorial($n) {
        if ($n==0) {
                return 1;
        }
        else {
                $product=1;
                for ($i=1; $i < $n+1; $i++) {$product=bcmul($product,$i);
                }
                return $product;
        }
}

En récursivité simple en Python 3

import sys
sys.setrecursionlimit(1000)

def Factorial(n):
        if n==0:
                return 1
        else:
                return n*Factorial(n-1)

n=int(float(input('Entrez votre entier positif : \n')))
print(f'La factorielle de {n} est {Factorial(n)}.')

En récursivité simple en PHP

<?PHP  
function Factorial($n) {
        if ($n==0) {
                return 1;
        }
        else {
                return bcmul($n,Factorial($n-1));
        }
}
?>

Les parties d’échecs

En itératif en Python 3

def Parties(n):
        if n==2:
                return 1
        else:
                nb_parties=1
                for x in range(3,n+1):
                        nb_parties+=x-1
                return nb_parties

n=int(input('Nombre de joueurs ? \n'))
print(f'Le nombre de parties pour vos {n} joueurs est de {Parties(n)}.')

En itératif en PHP

<?PHP  
function Parties($n) {
        if ($n==2) {
                return 1;
        }
        else {
                $nb_parties=1;
                for ($i=3 ; $i <$n+1 ; $i++) {
                        $nb_parties+=$i-1;
                }
                return $nb_parties;
        }
}
?>

En récursivité simple en Python 3

import sys
sys.setrecursionlimit(1000)

def Parties(n):
        if n==2:
                return 1
        else:
                return Parties(n-1)+(n-1)

n=int(input('Nombre de joueurs ? \n'))
print(f'Le nombre de parties pour vos {n} joueurs est de {Parties(n)}.')

En récursivité simple en PHP

<?PHP  
function Parties($n) {
        if ($n==2) {
                return 1;
        }
        else {
                return Parties($n-1) + ($n-1);
        }
}
?>

Le PGCD

En itératif en Python 3

def Euclide(n,m):
        while m!=0:
                sauv=n
                n=m
                m=sauv%m
        return n

a=int(input('Entrez votre premier nombre : \n'))
b=int(input('Entrez votre deuxième nombre : \n'))

print(f'Le PGCD de {a} et de {b} est {Euclide(a,b)}.')

En itératif en PHP

<?PHP  
function Euclide($n,$m) {
        while ($m!=0) {
                $sauv=$n;
                $n=$m;
                $m=$sauv%$m;
        }
        return $n;
}
?>

En récursivité simple en Python 3

import sys
sys.setrecursionlimit(1000)

def Euclide(n,m):
        if m==0:
                return n
        else:
                return Euclide(m,n%m)

a=int(input('Entrez votre premier nombre : \n'))
b=int(input('Entrez votre deuxième nombre : \n'))

print(f'Le PGCD de {a} et de {b} est {Euclide(a,b)}.')

En récursivité simple en PHP

<?PHP  
function Euclide($n,$m) {
        if ($m==0) {
                return $n;
        }
        else {
                return Euclide($m,$n%$m);
        }
}
?>

Fibonacci

En itératif en Python 3

def Fibonacci(n):
        if n<=1:
                return n
        else:
                init_0=0
                init_1=1
                for x in range(2,n+1):
                        sauv=init_1
                        init_1=init_1+init_0
                        init_0=sauv
                return init_1

n=int(float(input('Entrez un entier positif. \n')))
print(f'Le terme de rang {n} vaut {Fibonacci(n)}.')

En itératif en PHP

<?PHP  
function Fibonacci($n) {
        if ($n<=1) {
                return $n;
        }
        else {
                $init_0=0;
                $init_1=1;
                for ($i=2 ; $i <$n+1 ; $i++) {
                        $sauv=$init_1;
                        $init_1=bcadd($init_0,$init_1);
                        $init_0=$sauv;
                }
                return $init_1;
        }
}
?>

En récursivité simple en Python 3

import sys

sys.setrecursionlimit(1000)
def Fibonacci(n):
        if n<=1:
                return n
        else:
                return Fibonacci(n-1)+Fibonacci(n-2)

n=int(float(input('Entrez un entier positif. \n')))
print(f'Le terme de rang {n} vaut {Fibonacci(n)}')

En récursivité simple en PHP

<?PHP  
function Fibonacci($n) {
        if ($n<=1) {
                return $n;
        }
        else {
                return Fibonacci($n-1)+Fibonacci($n-2);
        }
}
?>

Sur ces quelques exemples, on voit que les algorithmes récursifs ont quelque chose de plus joli dans le sens où il suffit presque de les regarder afin de savoir à quoi ils servent, c’est concis : pas de variables globales, d’affectation de variables… Juste une fonction appelée avec un ou des paramètres et qui retourne ce qui nous intéresse sur l’état initial ou qui s’appelle elle-même avec des paramètres différents en combinant éventuellement des opérations.

Première question : est-ce que ces algorithmes récursifs fonctionnent  ?

On va les faire tourner… Mais dans un premier temps, quelques rudiments du langage PHP.

Le principe des formulaires en PHP

La vidéo en téléchargement : accessible ici.

Comparaison des algorithmes en itératifs et en récursivité simple

La vidéo en téléchargement : accessible ici.

La pile d’exécution des fonctions et la récursivité terminale


Qu’est-ce que la pile d’exécution  ?

En programmation, on parle de pile d’appel ou de pile d’exécution (call stack en anglais).

Dans un programme, lors de l’appel d’une fonction et uniquement lors de l’appel d’une fonction, l’environnement de cette fonction est mis dans un espace mémoire particulier qui s’appelle la pile d’exécution. Cet espace est limité quant à sa taille, ce qui signifie concrètement que le nombre de fonctions qui peuvent s’exécuter simultanément possède une limite à ne pas dépasser. De plus, cette espace réservé à l’exécution des fonctions fonctionne comme une pile (d’où son nom) : une fonction appelante ne pourra se fermer et libérer sa place dans cette pile que lorsque les fonctions appelées par cette appelante se seront fermées. Le dernier entré doit être le premier à sortir.
Le dépassement, le débordement ou la saturation ce cette pile d’exécution provoque généralement une interruption du programme, on parle de stack overflow en anglais… Et cela peut assez souvent se produire avec des programmes contenant des fonctions en récursivité « simple » où la fonction appelante de départ s’appelle elle-même avec un appel récursif qui n’est pas l’appel terminal (le résultat d’une opération contenant l’appel récursif par exemple).

Que contient l’environnement d’une fonction en exécution dans cette pile  ? Les paramètres de la fonction (s’il y en a), les variables locales de la fonction (s’il y en a), l’emplacement du retour éventuel de la fonction dans le programme principal ou l’emplacement du retour pour une fonction appelée vers la fonction appelante… Et d’autres choses.

Vous avez vu un beau stack overflow avec le nombre de parties d’échecs pour 50 000 joueurs en récursivité simple avec Python 3  ; pourtant, le nombre de parties est de 1 249 975 000. Ce n’est pas la taille des nombres en jeu qui pose problème, c’est le nombre de fonctions en excécution dans la pile d’appel. En PHP, c’est pareil  ! Le seuil de tolérance dépend du langage, du processeur, des types de fonctions en jeu, de valeurs dans des fichiers de configuration… Mail il y a toujours un seuil. Quant au terme de rang 50 de Fibonacci en récursivité simple, cela nécessite 40 730 022 147 récursions avec à un moment plus de 33 554 431 fonctions simultanées dans la pile d’exécution… Stack overflow… Et on n’est qu’au rang 50  !

Mais alors, on ne peut pas faire sérieusement de la programmation récursive en Python 3 ou en PHP  ? C’est dommage, c’est plutôt joli d’autant plus que certaines situations se présentent naturellement en récurrence et se prêtent donc plutôt bien à la programmation récursive.

En fait, c’est possible dès que votre situation peut se programmer en récursivité terminale (tail recursion en anglais)… Et la récursivité terminale quand c’est possible, c’est magique  ! C’est beau et les performances sont celles de l’itératif.


Parmi les quatre programmes récursifs précédents, seul l’algorithme d’Euclide est en récursivité terminale, le retour de l’appelante est la récursion elle-même  ; pour les trois autres, la récursion est le résultat d’une opération dont la récursion est un membre. Ci-dessous, je vais :

  • donner les trois programmes en récursion terminale  ;
  • expliquer un schéma possible de compréhension de ce type de programmation  ;
  • expliquer la différence fondamentale de fonctionnement au niveau de la pile d’exécution entre les deux types de récursivité  ;
  • montrer par récurrence sur un ou deux de ces exemples que les programmes retournent bien ce qu’on veut.

La factorielle en récursivité terminale

En Python 3

import sys
sys.setrecursionlimit(1000)

def Factorial(n, a=1):
        if n==0:
                return a
        else:
                return Factorial(n-1, a*n)

n=int(float(input('Entrez votre entier positif : \n')))
print(f'La factorielle de {n} est {Factorial(n)}.')

En PHP

<?PHP  
function Factorial($n,$a=1) {
        if ($n==0) {
                return $a;
        }
        else {
                return Factorial($n-1,bcmul($a,$n));
        }
}
?>

Les parties d’échec en récursivité terminale

En Python 3

import sys
sys.setrecursionlimit(1000)

def Parties(n,a=1):
        if n==2:
                return a
        else:
                return Parties (n-1,a+n-1)

n=int(input('Nombre de joueurs ? \n'))
print(f'Le nombre de parties pour vos {n} joueurs est de {Parties(n)}.')

En PHP

<PHP  
function Parties($n,$a=1) {
        if ($n==2) {
                return $a;
        }
        else {
                return Parties($n-1,$a+$n-1);
        }
}
?>

Fibonacci en récursivité terminale

En Python 3

import sys
sys.setrecursionlimit(1000)

def Fibonacci(n,a=0,b=1):
        if n==0:        # Cette condition sert seulement pour retourner la valeur du premier terme
                 return a
        if n==1:
                return b
        else:
                return Fibonacci(n-1,b,a+b)

n=int(input('Entrez votre rang : \n'))
print(f'Le terme de rang {n} vaut {Fibonacci(n)}.')

En PHP

<?PHP  
function Fibonacci($n,$a=0,$b=1) {
        if ($n==0) {
                return $a; # Cette condition sert seulement pour retourner la valeur du premier terme
        }
        elseif ($n==1) {
                return $b;
        }
        else {
                return Fibonacci($n-1,$b,$a+$b);
        }
}
?>

Nombre d’appels total de Fibonacci en récursivité simple (récursivité terminale)

En Python 3

import sys
sys.setrecursionlimit(1000)

def Appels_Fibonacci(n,a=1,b=1):
        if n==0:
                return a
        if n==1:
                return b
        else:
                return Appels_Fibonacci(n-1,b, a+b+1)

n=int(input('Entrez le rang du terme de la suite de Fibonacci\n'))
print(f'Le nombre d\'appels en récursivité simple afin de\n'
        f'calculer le terme de rang {n} est exactement {Appels_Fibonacci(n)}.')

Déjà, au niveau de l’exécution en Python 3 et en PHP, ces quatre programmes répondent correctement à la problématique de départ : pallier les contraintes de la récursivité simple.

La vidéo en téléchargement : accessible ici.


Un schéma possible de compréhension de la récursivité terminale

  • on utilise un ou des paramètres supplémentaires dans la fonction qu’on initialise aux valeurs de l’état initial qui nous intéressent. Comme on le verra, c’est l’idée magique. Dans les exemples ci-dessus, ce sont les a et les b  ;
  • condition d’arrêt : pour le ou les rangs de l’état initial, on retourne les valeurs, mais en utilisant les paramètres  ;
  • on fait la récursion en appelant la fonction un cran en dessous et avec la relation de récurrence appliquée au(x) paramètre(s). Il est alors important que pour passer d’un état au suivant, la récurrence soit d’ordre 1.

Comparaison de fonctionnement : récursivité simple et récursivité terminale

Récursivité simple

Un organisateur (une instruction dans le programme principal) organise une course d’orientation dans un stade. Le but final de cette course d’orientation est qu’un coureur avec le brassard de capitaine (la première fonction appelante) lui ramène une information bien précise. Pour ce faire, l’organisateur dispose au départ d’individus dans les tribunes, ces individus n’ont aucune mémoire. La seule manière d’avoir une mémoire, c’est d’écrire ce dont on doit se rappeler sur la piste du stade (la pile d’exécution), c’est une mémoire partagée… Et pour avoir une mémoire, il faut être un coureur : avoir été appelé (appel de fonction), avoir des instructions (nom de la fonction dans l’appel) et avoir un numéro de dossard (paramètre de la fonction). Le coureur est une fonction en exécution.

L’organisateur appelle un individu, lui donne les instructions de la fonction Factorielle et le dossard 3, c’est le capitaine de l’équipe, il devient coureur, il entre sur la piste et écrit tout de suite sur la piste l’emplacement de l’organisateur à qui il doit retourner les informations et son numéro de dossard. Il lit ensuite les instructions : si mon dossard est 0, retourner 1 (à l’organisateur) sinon faire un coureur sous-capitaine avec exactement les mêmes instructions que moi et le dossard 2 et retourner mon numéro de dossard multiplié par le retour de ce coureur. Le capitaine écrit sur la piste le calcul qu’il devra retourner et passe le relai au sous-capitaine. Le capitaine s’est fait son petit environnement-mémoire.
Le sous-capitaine écrit sur la piste l’emplacement du capitaine à qui il doit retourner les informations et son propre numéro de dossard, puis… Et ainsi de suite… Jusqu’à ce que le relai arrive au coureur de dossard 0 (la condition d’arrêt). C’est le dernier coureur à entrer sur la piste puisque d’après ses instructions, il doit retourner 1 au coureur de dossard 1, il le fait puis efface son environnement-mémoire puisque cela ne servira plus, il n’est plus coureur.

Le coureur de dossard 1 récupère l’information, lit dans son environnement-mémoire et envoie l’information ($1 \times 1$) au coureur de dossard 2, il efface alors son environnement-mémoire et cesse d’être un coureur… Et ainsi de suite jusqu’à ce que le coureur de dossard 3 envoie ($3 \times 2$) à l’organisateur. Il n’y a plus rien d’écrit sur la piste, plus de coureurs, la course est finie.

Cette course est chronophage, le relai doit aller jusqu’au coureur « condition d’arrêt » puis remonter jusqu’au capitaine… Mais pire, à un moment, les quatre environnements-mémoires sont écrits sur la piste. Avec un capitaine au numéro de dossard 4 000, on aurait eu, à un moment, 4 001 environnements-mémoires écrits sur la piste, c’est trop, il y a saturation, il n’y a pas assez de place sur la piste… Et que dire de l’équipe dont le capitaine est Fibonacci(50)  ? Le capitaine doit faire entrer sur la piste Fibonacci (49) et Fibonacci(48) qui, eux-mêmes, vont faire entrer Fibonacci(48), Fibonacci(47), Fibonacci(47) et Fibonacci(46)… Le nombre de personnes sur la piste augmente de manière exponentielle avec en plus des numéros de dossards identiques qui doivent se rappeler le bon appelant… La piste sature très vite en écriture, un environnement-mémoire d’un coureur peut même être effacé par celui d’un autre par manque de place, le relai est cassé… C’est le stack overflow.

Récursivité terminale

C’est une course d’orientation où on peut faire intervenir bien plus de coureurs que dans la course précédente : en plus du dossard (le paramètre de la récursivité) et de l’adresse de l’organisateur (l’adresse de retour dans le programme principal), le capitaine possède une ou plusieurs boîtes (autres paramètres d’appel, a et/ou b dans les exemples) qui vont servir à garder en mémoire l’information finale en construction à retourner. Le capitaine écrit son environnement-mémoire sur la piste et si son dossard n’est pas la condition d’arrêt, il appelle le sous-capitaine en lui donnant le numéro de dossard fixé par la récursivité, l’adresse de l’organisateur et les boîtes avec le contenu mis à jour. Le sous-capitaine possède toutes les informations nécessaires, le capitaine n’est plus utile, il efface son environnement-mémoire et quitte la piste… Et ainsi de suite… Jusqu’au coureur condition d’arrêt qui retournera le contenu de la boîte ou des boîtes directement à l’organisateur.

Bien évidemment, un capitaine ne peut avoir qu’un seul sous-capitaine, sinon on pourrait avoir différents retours dans le programme principal.

Prenons le capitaine Factorielle(3, a=1) : dossard 3 avec la boîte a contenant le nombre 1  ; ce capitaine appelle le coureur de dossard 2, lui donne l’adresse de l’organisateur, et lui remet la boîte avec comme contenu a = $3 \times 1 = 3$ : le capitaine quitte la piste et il ne reste que le coureur Factorielle(2,3) qui va quitter la piste pour laisser la place au coureur Factorielle(1,6) qui laissera la place au coureur Factorielle(0,6) qui retournera 6 au programme principal et quittera la pile d’exécution.

Avec le capitaine Fibonacci(4, a=0, b=1) : cette fonction va laisser sa place dans la pile à Fibonacci(3, a=1, b=1) qui, elle-même, va laisser sa place à Fibonacci(2, a=1, b=2) puis à Fibonacci(1, a=2, b=3), condition d’arrêt qui retournera 3 au bon endroit dans le programme puisque l’adresse de cet endroit est passée d’environnement-mémoire en environnement-mémoire.

On peut remarquer que dans l’exemple précédent avec la fonction Fibonacci(), le nombre de récursions dans la récursivité terminale est bien moins important que dans la récursivité simple, on passe d’une croissance exponentielle des récursions à une croissance linéaire en fonction du paramètre de récursivité de départ… Mais ce n’est pas réellement cela la magie de la récursion terminale (au niveau nombre de calculs, on perd des récursions mais on doit calculer les nouvelles valeurs des « paramètres-boîtes »)… La vraie magie, c’est que quasiment à chaque instant de la récursivité, vous n’avez qu’une seule fonction en exécution dans la pile et c’est cela qui permet d’obtenir des performances quasiment similaires à celles des algorithmes itératifs.


D’autres exemples de récursivité

L’addition de deux entiers naturels

En notant $s$ l’application successeur dans la théorie de l’arithmétique, les deux axiomes qui définissent l’addition sont les suivants :

  • pour tout $x$ appartenant à $\mathbb N$, on a $x+0 = 0$ (l’addition admet $0$ comme élément neutre) ;
  • pour tout $x$ appartenant à $\mathbb N$, pour tout $y$ appartenant à $\mathbb N$, on a $x+s(y) = s(x+y)$.

Remarques sur ces deux axiomes :

  • en notant $1$, le successeur de $0$, on a $x+1 = x+s(0)=s(x+0) = s(x)$ : ajouter $1$ revient à passer au successeur et le deuxième axiome de l’addition peut donc s’écrire $x + (y+1) = (x+y)+1$ ;
  • avec ces deux axiomes et l’axiome de récurrence, on montre que $+$ est bien une opération sur $\mathbb N$ et que cette opération est associative et commutative.

Ces deux axiomes se traduisent naturellement en récursivité simple.

Récursivité simple en Python 3

def Somme(n,m):
        if m==0:
                return n
        else:
                if n<m:
                        return Somme(m,n)
                return Somme(n,m-1)+1

n=int(input('Entrez votre premier nombre entier : \n'))
m=int(input('Entrez votre deuxième nombre entier : \n'))
print(f'La somme de {n} et de {m} donne {Somme(n,m)}.')

Afin de gagner quelques récursions, la commutativité est utilisée dans le « else » ; sans cette utilisation, c’est une traduction des axiomes.

Pour une récursivité terminale, on peut utiliser le schéma de compréhension donné plus haut, cela s’y prête plutôt bien.

Récursivité terminale en Python 3

def Somme(n,m,a=n):
        if m==0:
                return a
        else:
                if n<m:
                        return Somme(m,n,a=m)
                return Somme(n+1,m-1,a+1)

n=int(input('Entrez votre premier nombre entier : \n'))
m=int(input('Entrez votre deuxième nombre entier : \n'))
print(f'La somme de {n} et de {m} donne {Somme(n,m)}.')

Au niveau algorithmique, cela fonctionne, mais au niveau programmation, cela ne fonctionne ni en PHP ni en Python 3 : avec ces langages, on ne peut pas initialiser un paramètre par une variable ou un autre paramètre ; on peut contourner cette contrainte :

def Somme(n,m,a):
        if m==0:
                return a
        else:
                if n<m:
                        return Somme(m,n,a=m)
                return Somme(n+1,m-1,a+1)

n=int(input('Entrez votre premier nombre entier : \n'))
m=int(input('Entrez votre deuxième nombre entier : \n'))
print(f'La somme de {n} et de {m} donne {Somme(n,m,n)}.')

On peut aussi se passer du paramètre a :

def Somme(n,m):
        if m==0:
                return n
        else:
                if n<m:
                        return Somme(m,n)
                return Somme(n+1,m-1)

n=int(input('Entrez votre premier nombre entier : \n'))
m=int(input('Entrez votre deuxième nombre entier : \n'))
print(f'La somme de {n} et de {m} donne {Somme(n,m)}.')

Pour ce dernier algorithme, on utilise la propriété : $n+m=(n+1)+(m-1)$. Cette propriété se démontre facilement par récurrence sur $m$ en utilisant les deux axiomes de l’addition.

La multiplication de deux entiers naturels

Les deux axiomes qui définissent la multiplication sont les suivants :

  • pour tout $x$ appartenant à $\mathbb N$, on a $x \times 0 = 0$ (la multilplication admet $0$ comme élément absorbant) ;
  • pour tout $x$ appartenant à $\mathbb N$, pour tout $y$ appartenant à $\mathbb N$, on a $x \times (y+1) = x \times y + x$.

Récursivité simple en Python 3

def Prod(n,m):
        if m==0:
                return 0
        else:
                return Prod(n,m-1)+n

n=int(input('Entrez votre premier nombre entier : \n'))
m=int(input('Entrez votre deuxième nombre entier : \n'))
print(f'Le produit de {n} et de {m} donne {Prod(n,m)}.')

Pour une récursivité terminale, on peut utiliser le schéma de compréhension donné plus haut, cela s’y prête bien.

Récursivité terminale en Python 3

def Prod(n,m,a=0):
        if m==0:
                return a
        else:
                return Prod(n,m-1,a+n)

n=int(input('Entrez votre premier nombre entier : \n'))
m=int(input('Entrez votre deuxième nombre entier : \n'))
print(f'Le produit de {n} et de {m} donne {Prod(n,m)}.')

Les tours de Hanoï

Quelques rappels et résultats simples sur les tours de Hanoï : accessible ici.

Cet exemple est intéressant parce qu’il se prête naturellement à la récurrence en mathématiques et donc à la récursivité en algorithmique. Il est montré que tout algorithme récursif peut se « derécursifier », c’est à dire se ramener à un algorithme itératif, mais rien ne dit que c’est toujours simple. On peut donc trouver des algorithmes itératifs pour les tours de Hanoï, ce n’est pas si compliqué, mais cela demande une approche moins naturelle de la situation (la lier à l’écriture des nombres en base 2, par exemple).

Contrairement à la factorielle qu’on programmera plutôt en itératif (plus cohérent avec la définition usuelle en tant que produit), les tours de Hanoï se programmeront plutôt en récursif.

Autre point important, ce n’est pas une récursivité terminale : la fonction récursive est bien la fin de la récursion, mais il y a trois récursions par appels (sauf si condition d’arrêt). Notons qu’au niveau pile, le nombre maximum de fonctions en exécution est égal à n ce qui ne saturera pas la pile dans les situations courantes ; c’est une récursivité peu gourmande. Notons aussi que la récursion n’est pas un « return » de fonction, mais la fonction, elle-même.

Récursivité en Python 3

import sys
sys.setrecursionlimit(1000) # By default, 1000. We can modify here the max authorized number of recursivity ;


def Hanoi(n,debut="T1", pivot="T2", fin="T3"):
        if n==1:
                print(f'Déplacement de {debut} vers {fin}.')
        else:
                Hanoi(n-1,debut,fin,pivot)
                Hanoi(1,debut,pivot,fin)
                Hanoi(n-1,pivot,debut,fin)

def Nombre_de_coups(n,a=1):
        if n==1:
                return a
        else:
                return Nombre_de_coups(n-1,2*a+1)

n=int(input('Entrez votre nombre de disques :\n'))
Hanoi(n)
print(f'Le nombre minimum de coups pour ce déplacement est de {Nombre_de_coups(n)}.')

Récursivité en PHP

<?php  
function Hanoi($n,$debut="T1",$pivot="T2",$fin="T3") {
        if ($n==1) {
                echo 'Déplacement de ' . $debut . ' vers ' . $fin . '. <br />';
        }
        else {
                Hanoi($n-1,$debut,$fin,$pivot);
                Hanoi(1,$debut,$pivot,$fin);
                Hanoi($n-1,$pivot,$debut,$fin);
        }
}
function Nombre_de_coups($n,$a=1) {
        if ($n==1) {
                return $a;
        }
        else {
                return Nombre_de_coups($n-1,2*$a+1);
        }
}
?>

Extrait positifs d’une liste

Énoncé : écrire la fonction récursive liste_des_positifs qui, étant donné une liste d’entiers, construit la liste de tous les entiers strictement positifs de la liste.

Récursivité en Python 3

def liste_des_positifs(ma_list):
        if len(ma_list)==0:
                return []
        else:
                if ma_list[0]>0:
                        return [ma_list[0]]+liste_des_positifs(ma_list[1:])
                return liste_des_positifs(ma_list[1:])

ma_list=[-4,-9,5,4,1,1,1,-10]
ma_list_triee=liste_des_positifs(ma_list)
print(ma_list_triee)

Tri par insertion

Énoncé : le tri par insertion est un algorithme qui permet d’insérer un élément en bonne position dans une liste déjà triée dans l’ordre croissant.

Récursivité en Python 3

def inserer_element_dans_liste_triee(elem,ma_list_triee):
        if len(ma_list_triee)==0:
                return [elem]
        elif elem<=ma_list_triee[0]:
                ma_list_triee.insert(0,elem)
        else:
                ma_list_triee[1:]=inserer_element_dans_liste_triee(elem,ma_list_triee[1:])

        return ma_list_triee

def tri_insertion(ma_list_a_trier):
        if len(ma_list_a_trier)<2:
                return ma_list_a_trier
        else:
                return inserer_element_dans_liste_triee(ma_list_a_trier[0],tri_insertion(ma_list_a_trier[1:]))

ma_list=[-4,-9,5,4,1,1,1,-10]
ma_list_triee=tri_insertion(ma_list)
print(ma_list_triee)

Le tri rapide

Énoncé : le tri rapide est un algorithme de tri très utilisé pour sa relative simplicité et sa rapidité. On peut en donner une solution récursive.

  • si la liste a moins de 2 éléments, c’est fini, la liste est déjà triée
  • sinon
    – on choisit un élément de la liste au hasard qu’on appelle pivot ; ici on prendra le premier élément de la liste pour simplifier ;
    – on partitionne la liste en 2 listes : la liste des éléments qui sont inférieurs ou égaux au pivot et la liste des éléments qui sont supérieurs au pivot ;
    – on trie ensuite ces 2 listes suivant la même méthode (appels récursifs) ;
    – on construit la liste résultat en concaténant les 2 listes triées.

Récursivité en Python 3

def tri_rapide(ma_list):
        if len(ma_list)<2:
                return ma_list
        else:
                pivot=ma_list[0]
                ma_list1=[]
                ma_list2=[]
                for i in ma_list[1:]:
                        if pivot>i:
                                ma_list1.append(i)
                        else:
                                ma_list2.append(i)
                return tri_rapide(ma_list1)+[pivot]+tri_rapide(ma_list2)

ma_list=[4,1,7,15,-9,6,-2,0,4,-5]
ma_list_triee=tri_rapide(ma_list)
print(ma_list_triee)

Autre façon…

def partitionner_pivot(ma_list,a=0,b=1,c=-1):
        if len(ma_list)==0:
                return []
        elif len(ma_list)==1:
                return [ma_list[a]]
        elif len(ma_list)==2:
                if ma_list[a]<=ma_list[b]:
                        return [ma_list[a],ma_list[b]]
                return [ma_list[b],ma_list[a]]
        else:
                ma_list=[ma_list[a]]+partitionner_pivot(ma_list[1:],a,b,c)
                ma_list=partitionner_pivot(ma_list[:-1],a,b,c)+[ma_list[c]]
                ma_list=[ma_list[a]]+partitionner_pivot(ma_list[1:],a,b,c)
                return ma_list

ma_list=[4,3,2,1,-8,5,-7,9,7,-7]
ma_list_triee= partitionner_pivot(ma_list)
print(ma_list_triee)

Quelques compléments intéressants


Retours utiles sur la récurrence en mathématiques

L’ensemble des entiers naturels $\mathbb N$ de notre enfance muni des deux opérations $+$ et $\times$ et de sa relation d’ordre total $\leqslant$ peut être vu comme un modèle d’une théorie axiomatique de onze axiomes. En ne chipotant pas trop, on peut considérer que cette théorie est la théorie axiomatique de l’arithmétique du mathématicien italien Giuseppe Peano (1858-1932). Je noterai GP cette théorie par la suite.

Lire la suite sur l’axiome de récurrence

Hormis le premier axiome de GP qui justifie que $\mathbb N$ est non vide, la plupart des autres utilisent l’existence d’une application de $\mathbb N$ dans $\mathbb N$ : on note souvent s cette application, s comme successeur. $+$ et $\times$ sont définies à l’aide de s et l’ordre est défini à l’aide de $+$ donc à l’aide de s.

On montre ensuite assez facilement que pour tout entier n, $s(n) = n+1$.

Parmi tous ces axiomes, il y en a un, le cinquième par habitude, qui s’appelle l’axiome de récurrence et qui, dans sa forme initiale, ne ressemble pas à la forme qu’on utilise pour démontrer en mathématiques.

Axiome 5 : si une partie de $\mathbb N$ contient 0 et le successeur de tous ses éléments, alors cette partie est égale à $\mathbb N$.

Ensuite, c’est comme pour la médiatrice en géométrie euclidienne : vous avez une définition « La droite perpendiculaire au segment et qui passe par le milieu du segment » et vous montrez une propriété caractéristique, une équivalence, « La médiatrice d’un segment est l’ensemble des points situés à égale distance des extrémités du segment ». Il est alors tout à fait possible d’introduire la médiatrice en intervertissant le statut de ces deux énoncés.

Il n’est pas trop dur mais surtout très joli de montrer que l’axiome 5 de GP est équivalent aux énoncés ci-dessous :

  • toute partie non vide de $\mathbb N$ admet un plus petit élément  ;
  • il n’existe pas de suite infinie d’entiers strictement décroissante  ;
  • on se donne un énoncé P paramétré par les entiers  ; on note P(n) ou Pn cet énoncé lorsque le paramètre est égal à l’entier n.

Si P(0) est vrai et Si, pour tout entier n, P(n) est vrai implique que P(n+1) est vrai Alors tous les P(n) sont vrais.

J’ai encadré le dernier énoncé puisque c’est la forme usuelle d’utilisation de la récurrence en mathématiques.

Comme pour la médiatrice et quitte à réordonner les axiomes, on pourrait remplacer l’axiome 5 par l’une de ces formulations. C’est ce qui fait qu’on peut parler de principe de la démonstration par récurrence (axiome) ou de théorème de la démonstration par récurrence. Par habitude, on considère plutôt la démonstration par récurrence dans sa forme usuelle comme un théorème. Je vais l’appeler un instant « récurrence simple ».

Autre point important : la « récurrence forte » qui dit que « Si P(0) est vrai et Si, pour tout entier naturel n, P(k) est vrai pour tout entier k inférieur ou égal à n implique que P(n+1) est vrai Alors tous les P(n) sont vrais » est équivalente à la « récurrence simple »  ; au niveau logique, elle n’est pas plus forte.

Enfin, ces énoncés usuels peuvent se formuler à un rang initial n0 qui n’est pas forcément 0.

Pour celles et ceux intéressés par ces différentes démonstrations :

Récursivité et récurrence

Comme dit au début de l’article, la récursivité (algorithmique) et la récurrence (arithmétique) sont très liées. Il est à noter que toutes les récursivités traitées dans cet article sont des récursivités qui, au départ, viennent d’une situation mathématique récurrente. Dans ces cas :

  • en récursivité simple, c’est souvent une traduction directe de la situation de récurrence de départ ;
  • en récursivité terminale, parfois, la situation de départ se traduirait plutôt par une récursivité simple et pour pallier la saturation de la pile, on transforme la récurrence initiale afin d’arriver à une récursivité terminale au niveau traduction algorithmique. Dans certains cas, la situation de récurrence initiale se traduit naturellement par une récursivité terminale (Euclide) ;
  • la convergence des algorithmes récursifs peut se montrer par récurrence.

« S’appeler soi-même » est un peu le principe de base de la récursivité et concerne les problèmes dont la résolution peut se ramener à des sous-problèmes de même nature, mais plus simples. En ce sens, la récursivité engloble plus que la récurrence : les récursivités de cet article ne représentent qu’un type d’applications de la récursivité, la récurrence ne représente qu’un type d’applications des mathématiques inductives. Le réel lien est donc la récursivité et les mathématiques inductives. Lorsqu’on travaille sur ce lien, on parle de programmation fonctionnelle et il existe des langages fonctionnels adaptés particulièrement à ce travail : par chauvinisme assumé et modeste, citons OCaml, langage internationnalement reconnu. On entend assez souvent que la programmation fonctonnelle est un « truc de matheux » : c’est sans doute vrai, avant tout parce que c’est très lié à la logique.


Je me permets de faire un petit bloc dépliable non indispensable à la lecture de cet article relatant des avancées mathématiques importantes en logique entre la moitié du XIXe et la moitié du XXe siècle.

Quelques points clés de cette époque

La logique, domaine de la philosophie et des mathématiques, n’avait que peu évolué depuis la Grèce antique. Dans une époque couvrant des personnages comme Nikolaï Lobatchevski, Giuseppe Peano, Gottlob Frege, Ernst Zermelo, David Hilbert, George Boole, Auguste De Morgan, Kurt Gödel, Bertrand Russell et d’autres, la logique devient une branche à part entière des mathématiques avec le rêve presque fou de créer une théorie axiomatique cohérente et complète qui servirait pour toutes les mathématiques.

Une théorie qui permet de faire de l’arithmétique comme celle de Péano ou celle de ZFC est donc, soit incohérente, soit incomplète. Comme disait un grand mathématicien : « les doutes quant à l’incohérence de ZFC sont très douteux. ». Disons qu’avec le temps, on serait sans doute déjà tombé sur une incohérence et qu’il y a donc fort à penser que ZFC est incomplète tout comme GP.

En supposant GP cohérente, elle est donc incomplète et il existe donc des résultats vrais dans cette théorie et non démontrables en restant dans cette théorie. Il est important de noter que cela ne contredit pas le théorème de complétude de Gödel.
Un tel énoncé pourrait ressembler au célèbre théorème de Fermat-Wiles qui, au départ, est une situation arithmétique. La seule démonstration reconnue utilise ZFC, il a donc fallu sortir de GP afin de démontrer que c’était vrai et c’est vrai … Mais ce n’est pas démontré en restant dans GP  ; on pourrait aussi penser à la conjecture de Goldbach et de Syracuse … À moins que ces deux conjectures ne soient des exemples de l’incomplétude de ZFC, tout comme l’ hypothèse du continu de Georg Cantor pour laquelle, par contre, il est prouvé qu’elle est indécidable dans ZFC.

Et si ZFC était contradictoire  ? Et bien, elle le sera et cela ne nous a pas empêché de faire des mathématiques et ne nous empêchera pas d’en faire.

Une dernière précision : le $\mathbb N$ de notre enfance n’est pas le seul modèle de GP … Mais parmi les ensembles ou les sous-ensembles de nombres couramment utilisés, c’est le seul. Pour les modèles non isomorphes à $\mathbb N$, on parle d’entiers non standards.

Une vidéo de vulgarisation (voire plus si vous lisez les billets de complément) de David Louapre sur “Science étonnante” au sujet de l’incomplétude : accessible ici.

J’utilise à titre personnel ou pour mes élèves certaines vidéos de cet auteur dans mes cours ou celle de l’auteur de « e-penser » comme celle sur Ératosthène. Sur ce point du calcul d’un des grands cercles de la Terre par Ératosthène, c’est joli mais cela ne s’est sans doute pas passé comme cela et on peut imaginer que ce problème a été retourné afin de faire de la trigonométrie, la circonférence souhaitée étant connue  !


Les programmes en téléchargement

Accessible ici.

Remerciements et conclusion personnelle

Les exemples choisis dans cet article sont classiques, c’est un choix.
La programmation récursive ou fonctionnelle est une programmation de « matheux », c’est sans doute vrai  ; cela n’enlève pas le fait que c’est intéressant, notamment parce que c’est une approche différente de la programmation itérative et que plus on a d’approches, plus on a de pistes de résolution ; parfois, la programmation récursive est plus naturelle, parfois non voire inutile. Sur ce dernier point, j’y vois un parallèle entre la programmation orientée objet ou non objet. Les différentes « techniques » de programmation ne sont pas toujours exclusives et peuvent bien souvent se compléter et s’entraider.

Dans une démarche récursive, il n’y a pas toujours besoin d’un « else », notamment si la condition d’arrêt contient une instruction « return ». Ne pas mettre le « else » donne toute sa puissance à l’instruction « return » et aide même à mieux la comprendre. J’ai choisi de le mettre dans ces cas par simplicité de lecture, c’est un choix très discutable et discuté.

La récursivité est au programme de la spécialité NSI en terminale.

Je tenais à remercier tout particulièrement Davy Defaud et Julien Baldacci qui ont gentiment accepté de prendre de leur temps précieux afin de relire cet article.