I- Introduction à la récursivité
Récursif ou itératif… Voilà un sujet de discussion encore non élucidé entre les développeurs du monde entier. Pourtant, avant de chercher à argumenter dans un sens ou dans l’autre autour de cette question, il faut déjà comprendre ce que l’on appelle algorithme récursif (et donc algorithme itératif). Si l’on remonte ainsi aux débuts de l’informatique, un programme en langage machine s’exécutait « verticalement » en lisant tour à tour les instructions écrites, autorisant néanmoins l’instruction « jump » qui permettait de sauter vers une étape particulière du programme. L’informatique évoluant, la puissance des ordinateurs aussi, on a pu arriver petit à petit à des algorithmes plus ou moins efficaces que ces derniers. Parmi les voie d’optimisation, on a développé les algorithmes récursifs, c’est-à-dire des algorithmes qui s’appellent eux-mêmes lors de l’exécution et qui sont donc plus « compactes » mais aussi et surtout plus compréhensibles selon les cas. Des avantages de la programmation récursive, on pourra souligner :
- La facilité d’explication de certains algorithmes beaucoup plus complexes
- L’optimisation du code par les compilateurs qui est rendue plus facile par l’abstraction
- L’existence de structures qui se prêtent facilement à l’utilisation de tels algorithmes
Encore aujourd’hui, la programmation récursive constitue un outil à part entière et on peut souvent « simplifier » nos codes en faisant appel à des fonctions récursives. De plus, la plupart des langages auxquels nous accédons aujourd’hui ont un environnement qui permet l’utilisation de fonctions récursives. Cela se résume bien souvent à la gestion astucieuse d’une pile de stockage mémoire…
Dans cet article, j’aborderai un exemple commun d’algorithme récursif en implémentant le calcul de la fonction mathématiques factorielle.
II- Programmation
a) La fonction factorielle
Avant de se lancer dans la programmation, j’ai souhaité écrire quelques lignes sur la fonction factorielle afin que l’on parle tous de la même chose et que l’on s’accorde sur les termes et notations.
En mathématiques, la fonction factorielle est définie de la manière suivante :
n! = \prod_{i=1}^n i = 1*2*3*4*... *nDès lors, on note l’image de x par la fonction factorielle. A titre indicatif, on notera les valeurs suivantes :
\begin{cases}
0! = 1\\
1! = 1\\
2! = 2\\
3! = 6
\end{cases}
On remarque ainsi que l’on peut écrire la fonction factorielle de la manière suivante :
\begin{cases}
n! = (n-1)! * n \\
0! = 1
\end{cases}Et nous voilà ainsi arrivés à l’écriture dont nous aurons besoin dans la suite de notre article. En effet, la formule ci-dessus nous permet de calculer la factorielle de « rang » n en calculant auparavant la factorielle de « rang » n-1. On peut alors répéter l’opération jusqu’à arriver à la factorielle de « rang » 0 dont la valeur est définie à 1
b) Du code, enfin…
Dans un premier temps, je vous propose une implémentation « à l’ancienne » de la fonction factorielle. En fait, cela correspond à un algorithme itératif, littéralement qui va itérer sur notre produit jusqu’à arriver à la fin :
import time
def factorielle(n):
resultat = 1
for k in range(1, n+1):
resultat *= k
return resultat
clock1 = time.perf_counter_ns()
print(factorielle(1000))
clock2 = time.perf_counter_ns()
print("Temps d'exécution: " + str(clock2 - clock1) + "ns")
Dans ce script, j’ai inclus le calcul du temps d’exécution qui pourrait bien nous être utile pour la suite…
Quant à l’algorithme récursif, il est en fait beaucoup plus clair car on applique directement les formules établies dans la première partie. Cet algorithme est dit récursif car il s’appelle lui-même dans sa fonction. Cela devrait être bien plus explicite à la lecture du code suivant :
import time
def factorielle(n):
if n == 0:
return 1
else:
return n * factorielle(n-1)
clock1 = time.perf_counter_ns()
print(factorielle(100))
clock2 = time.perf_counter_ns()
print("Temps d'exécution: " + str(clock2 - clock1) + "ns")
A la lecture du temps d’exécution des deux programmes, on remarque que l’algorithme itératif est bien plus rapide (environ deux fois) mais l’algorithme récursif est bien plus simple à comprendre. Du moins, il est plus proche de la vision mathématique que l’on a de la fonction. On peut cependant lui trouver une limite si l’on demande à calculer factorielle(1000), Python refusera alors le calcul. En effet, lorsque le nombre d’appel de l’algorithme (« profondeur » de récursivité) est trop élevé, l’occupation mémoire de l’algorithme devient trop importante et Python met alors en place une limite pour éviter les erreurs.
III- Conclusion
Au cours de cet article, nous avons abordé les fondamentaux de la programmation récursive. Si l’intérêt ne semble à première vue pas gigantesque, comprenez que ce type de programme nous permet de calculer des formes fractales ou autres étranges beautés mathématiques d’une manière souvent bien plus élégante que la méthode récursive.
L’objectif n’est pas ici de maitriser un algorithme en particulier mais bien de comprendre l’intérêt d’une telle méthode pour un développeur confronté à un problème bien particulier. Nous aurons sans doute par la suite l’occasion d’aborder de nouveau ce type de programmation.
