TNSI: Cours Récursivité⚓︎
Introduction⚓︎
Les fonctions récursives permettent une nouvelle méthode/paradigme de programmation, quelquefois (beaucoup?) plus simple pour l'écriture de nombreux problèmes.
Exemple: Un Algorithme Itératif⚓︎
En Python, Écrire un algorithme itératif qui calcule la Somme \(S=1+2+3+...+1000\)
Exemple: Un Algorithme Récursif⚓︎
On souhaite maintenant calculer la même somme \(S=1+2+3+...+1000\) mais différemment : avec un algorithme dit récursif.
def f(n:int)->int:
if n==1:
return 1
else:
return n+f(n-1)
Cette fonction f implémente simplement une façon récursive de définir la somme des entiers positifs de 1 jusqu'à n, donc \(S=1+2+3+...+n\)
f
De manière très simplifiée, on peut décomposer ainsi l'appel récursif de f(4)
f(4)= 4 + f(3)
f(3)=3+f(2)
f(2) = 2+f(1)
f(1) = 1 // cas de base
Remarque:
- Cette fonction récursive commence par une condition d'arrêt qui s'occupe du cas de base.
- on peut débugguer cette fonction en affichant à l'écran la valeur courante de
n(faites-le)
Cas de Base
Un cas de base est une valeur de l'argument pour la quelle le problème se résout instantanément.
Notion de Pile d'Exécution⚓︎
- Lors de l'appel d'une fonction récursive, une structure de pile est utilisée en interne
- Une pile
, ou stack 
ou LIFO (Last In First Out) , fonctionne comme un empilement d'objets (penser par exemple à une pile d'assiettes):- on peut empiler un objet (comprendre ajouter un objet en haut de la pile)
- on peut dépiler un objet (comprendre enlever un objet du haut de la pile)
- le haut de la pile est le seul objet accessible
- La pile utilisée, appelé pile d'exécution, est de taille limitée. Au delà d'un certain nombre d'appels récursifs, 1000 par défaut en Python, il y a une erreur de dépassement de la taille de la pile (Stack Overflow)
Comment connaître la taille maximale de la pile du nombre d'appels récursifs?
import sys
print(sys.getrecursionlimit())
Modifier la taille de la pile du nombre d'appels récursifs en Python:
import sys
sys.setrecursionlimit(1500)
Exponentiation (Lente)
Formule Pour \(a\) réel, et \(n\) entier naturel (\(\ge0\)):
1°) En prenant en compte la formule précédente, Écrire une fonction récursive f(a:float,n:int)->a^n:float qui :
- reçoit en argument :
- un nombre flottant \(a\)
- un nombre entier naturel \(n\),
- renvoie en sortie la puissance \(a^n\)
2°) Modifier la fonction récursive précédente, pour qu'elle soit capable de calculer l'exponentiation de \(a\) par \(n\) avec des valeurs de \(n \in \mathbb Z\), donc pour des \(n\) entiers négatifs.
3°) Déterminer la complexité de cet algorithme
Principe Général d'Écriture d'une Fonction Récursive⚓︎
Une fonction récursive classique, simple, s'écrit sous la forme:
def fonction(args):
if conditionArret:
return valeurCasDeBase
else:
return appelRecursif
Pour écrire une fonction récursive, on doit:
- déterminer le type de données à renvoyer
- déterminer pour quelle.s valeur.s de l'argument le problème est résolu et on écrit la condition d'arrêt
- déterminer de quelle manière la taille du problème est réduite (argument entier qui décroit strictement, liste dont la taille diminue strictement, etc..)
- écrire l'appel récursif en prenant garde à ce que le type de données qu'il renvoie soit cohérent avec celui renvoyé par la condition d'arrêt.
Calculer la Complexité d'une fonction récursive⚓︎
Master Theorem (Rappel)
Le tableau suivant résume les complexités (asymtpotiques) \(C(n)\) des fonctions récursives :
| Relation de Récurrence | Complexité (Asymptotique) |
|---|---|
| \(C(n+1)=C(n)\) | \(O(1)\) |
| \(C(n+1)=C(n)+O(1)\) | \(O(n)\) |
| \(C(n+1)=C(n)+O(n)\) | \(O(n^2)\) |
| \(C(n+1)=C(n)+ \varepsilon\) pour \(\varepsilon>0\) et variable (avec \(n\)) |
cas plus subtil: ça dépend (de \(\varepsilon\)) |
| Exemple 1 : \(C(2\times n)=C(n)+ O(1)\) | \(O(log_2(n))\) |
| Exemple 2 : \(C(a\times n)=C(n)+ O(1)\) | \(O(log_a(n))\) |
| \(C(n+1)=2\times C(n)+ O(1)\) | \(O(2^n)\) |
| \(C(n+1)=a\times C(n)+ O(1)\) | \(O(a^n)\) |
Limites de la Récursivité⚓︎
Un Problème potentiel: la Complexité⚓︎
La suite de Fibonacci⚓︎
Def
La Suite de Fibonacci (ou Léonard de Pise, v. \(1175\) - v. \(1250\)) est définie par:
- \(F_0=0\); \(F_1=1\)
- Pour tout entier \(n\),
\(F_{n+2}=F_{n+1}+F_n\)
Remarquer que, mathématiquement, il existe une formule qui permet le calcul direct de la valeur de \(F_n\) :
Formule explicite de Fn en fonction de n (Formule de Binet)
\(\forall n\in\mathbb N, \quad F_n=\dfrac {1}{\sqrt 5} \left[ \left( \dfrac {1+\sqrt 5}{2} \right)^{n} - \left( \dfrac {1-\sqrt 5}{2} \right)^{n} \right]\)
Cette formule explicite prouve que la suite de Fibonacci admet une croissance exponentielle.
Un Algorithme récursif naïf⚓︎
On peut considér l'algorithme (naïf) suivant de calcul de \(F_n\):
Python
def fibo(n:int)->int:
if n<=1:
return n
else:
return fibo(n-1)+fibo(n-2)
Bien que cette fonction renvoie effectivement le bon résultat, les calculs deviennent chronophages pour des valeurs élevées de \(n\): e.g. essayer
Sa Complexité est Exponentielle⚓︎
Une simple analyse de la complexité en temps (le nombre d'opérations) de l'algorithme récursif naïf précédent explique ces temps de calcul: en effet, si on note fibo(n), alors on obtient la relation de récurrence:
Notons \(F_n\) les termes de la suite de Fibonacci, donc :
- \(F_0=0\) et \(F_1=1\)
- \(F_{n+2}=F_{n+1}+F_n\)
Démonstration "par Récurrence", notons \(H(n)\): « \(T_{n+1}\ge F_{n+1}\) et \(T_n\ge F_n\) »
- Initialisation: C'est vrai pour \(n=0\), car \(T_0=1 \ge 0=F_0\), et pour \(n=1\), car \(T_1=1 \ge 1=F_1\)
- Hérédité: Supposons que HR(\(n\)) soit vraie, i.e. supposons que \(T_{n+1}\ge F_{n+1}\) et \(T_{n}\ge F_{n}\) donc \(T_{n+1}+T_n+1\ge T_{n+1}+T_n\ge F_{n+1}+F_n\) donc \(T_{n+2}\ge F_{n+2}\) et par ailleurs \(T_{n+1}\ge F_{n+1}\) (déjà connu) ce qui prouve \(H(n+1)\): « \(T_{n+2}\ge F_{n+2}\) et \(T_{n+1}\ge F_{n+1}\) »
- Conclusion : « \(\forall n \in \mathbb N\), \(T_n\ge F_n\) »
Cette inégalité permet de déduire que cette suite \((T_n)\) croît encore plus vite que la suite de Fibonacci \((F_n)\), qui a déjà un comportement exponentiel (Formule de Binet).
Conclusion: La complexité en temps \(T_n\) (de cet algorithme récursif naïf) est exponentielle
Cela vient du fait, principalement, que la fonction fibo() recalcule en doublon de nombreux sous-problèmes, càd (dans ce contexte) plusieurs fois les valeurs de fibo(p) pour une même valeur p donnée : On dit que les sous-problèmes ne sont pas indépendants.
Une Solution: fonction récursive avec mémoïsation⚓︎
Lorsque les sous-problèmes ne sont pas indépendants, une stratégie possible, pour améliorer notablement la complexité, consiste à :
- Déterminer la solution de chaque sous-problème la première fois qu'on le rencontre, et
- le conserver en mémoire afin de ne plus devoir le recalculer (à chaque fois qu'on en a besoin par la suite)
Mémoïsation
Cette technique est appelée
En pratique, on utilise :
- un tableau ou un dictionnaire pour stocker les solutions aux sous-problèmes déjà rencontrés
- une fonction locale (une fonction à l'intérieur d'une fonction) pour stocker la logique, càd pour :
- accéder efficacement (sans les recalculer) aux solutions déjà calculées des sous-problèmes
- ou bien, s'il s'agit d'un nouveau sous-problème dont il faut calculer une solution pour la première fois, et la stocker dans le tableau/dictionnaire
Fonction Locale
Une
Exp
def fibo(n:int)->int:
memo_fibo = dict()
def fib(n:int)->int:
if n in memo_fibo:
return memo_fibo[n]
if n<=1:
memo_fibo[n] = n
else:
memo_fibo[n] = fib(n-1) + fib (n-2)
return memo_fibo[n]
return fib(n)
Dans le cadre de la récursivité, on l'utilise quelquefois pour ajouter des arguments à une fonction.