4.5 KiB
Recursivité
Le programme
La récursivité est un style de programmation permettant de simplifier l'écriture de nombreux problèmes.
Un peu de culture
La récursivité, en informatique, est une pratique qui permet à une fonction de s'appeler elle-même. On peut comparer cela à la mise en abyme, procédé littéraire qui décrit une oeuvre incrustée dans elle même
La fonction récursive s'appelle elle même dans sa définition.
Mauvais exemple
Rien de tel qu'un mauvais usage pour mieux comprendre un concept.
Voici une fonction récursive :
def fct_recursive() :
print("Je fais un appel de la fonction")
fct_recursive()
Cette fonction s'appelle elle même, mais elle présente un problème.
Si nous l'appelons, le résultat sera celui-ci :
>>> fct_recursive()
"Je fais un appel de la fonction"
"Je fais un appel de la fonction"
"Je fais un appel de la fonction"
"Je fais un appel de la fonction"
"Je fais un appel de la fonction"
"Je fais un appel de la fonction"
"Je fais un appel de la fonction"
...
Tout comme les boucles, il faut créer une instruction permettant d'arrêter l'exécution du code, en récursif nous l'appelons le cas d'arrêt. Il permettra d'éviter les appels infinis
Le cas d'arrêt
Afin de stopper l'exécution du code il est donc essentiel de créer une instruction n'appelant pas notre fonction.
Par exemple :
Voici la fonction somme(n) se définissant comme :
somme(n) = \left\{ \begin{array}{ll} 0 {~si~} n = 0\\ n + somme(n -1){~sinon.} \end{array}\right.
def somme(n) :
if n == 0 :
return 0
else :
return n + somme(n-1)
Cette fonction s'appelle donc elle même jusqu'à avoir n égal à 0.
Mais quel sera le résultat de somme(3) ?
Pour obtenir cette réponse nous allons dérouler à la main le code :
somme(3) = 3 + somme(2)
somme(2) = 2 + somme(1)
somme(1) = 1 + somme(0)
somme(0) = 0
Voici les différents appels de fonctions pour somme(3). Mais là, le résultat n'est pas encore obtenu.
Pour cela il faut pour cela reprendre les appels de fonctions pour revenir jusqu'à somme(3)
somme(0) = 0
somme(1) = 1 + 0 = 1
somme(2) = 2 + 1 = 3
somme(3) = 3 + 3 = 6
Ici nous observons donc 4 appels de fonctions pour résoudre somme(3).
Appel de fonction en python
En python il existe une limite au nombre d'appel de fonction que l'on peut faire pour une fonction récursive.
En effet, avec notre exemple nous voyons que pour obtenir somme(3) nous faisons 4 appels de fonction.
Ces appels de fonction s'empilent en espace mémoire, python peut stocker autour de 1000 appels.
Si cette limite est dépassée alors l'erreur RecursionError apparaîtra.
>>> somme(1001)
...
RecursionError: maximum recursion depth exceeded in comparison
Autre type de récursivité
Il existe divers types de récursivité :
- La récursivité multiple
- La récursivité double
- La récursivité imbriquée
- etc ...
Ces différents types de récursivité sont quelques peu différents de ce que l'on vient de voir. Mais nous pourrions les rencontrer dans la suite du programme.
Récursivité double
En effet à la différence de la récursivité dite simple il y aura ici plusieurs appels de fonctions dans une même instruction.
En mathématiques, la suite de Fibonacci est une suite de nombres entiers dont chaque terme successif représente la somme des deux termes précédents, et qui commence par 0 puis 1. Ainsi, les dix premiers termes qui la composent sont 0, 1, 1, 2, 3, 5, 8, 13, 21 et 34.
def fibonacci(n):
if n == 0 :
return 0
elif n == 1 :
return 1
else :
return fibonnaci(n-1) + fibonnaci(n-2)
Auteurs : Florian Mathieu, Timothée Decoster, Enzo Frémeaux
Licence CC BY NC
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.