Nous présentons ici quelques exemples d’utilisation de la récursivité et montrons tant la puissance des fonctions récursives que certains pièges que leur utilisation peut amener.
I. Recherche dichotomique dans une liste triée
Soit lst une liste de nombres triée dans l’ordre croissant et soit x un nombre. Nous pouvons adapter l’algorithme de recherche dichotomique vue en Première de manière récursive : on teste si l’élément médian de lst est égal à x, sinon on cherche sa présence à gauche ou à droite dans lst suivant qu’il est plus grand ou plus petit que x.
Cet algorithme s’arrête lorsque lst est vide.
En apparence, cette fonction a la même complexité que la recherche dichotomique dans une liste triée écrite de manière itérative, donc de l’ordre de log2n. Néanmoins, le slicing a un coût caché qu’il faut prendre en compte.
La relation de récurrence s’écrit alors Tn=Tn/2+n/2. Cette relation de récurrence mène à Tn=Θn. L’utilisation d’une fonction locale stockant les indices gauches et droits encadrant les indices où peut être trouvé l’élément aurait permis de réduire cette complexité :
Mot-clé
Une fonction locale est une fonction définie à l’intérieur d’une fonction. Elle permet, notamment dans le cadre de la récursivité, d’ajouter des arguments à une fonction.
La fonction recherche2 n’effectue que des opérations élémentaires à chaque appel récursif. Le fait d’utiliser comme arguments supplémentaires les indices i et j tels que lst[i] <= x <= lst[j] permet d’éviter d’effectuer des opérations directement sur la liste et réduit le coût.
Ceci a comme coût Tn=Tn/2+1 ce qui mène à Tn=Θlogn.
II. Suite de Fibonacci et récursivité explosive
1) Fonction récursive naïve de Fibonacci
On s’intéresse ici à la programmation récursive du calcul du terme général de la suite de Fibonacci, définie par :
u0=0 ; u1=1 et, pour tout entier naturel n, un+2=un+1+un.
Une écriture, naïve, de ce calcul conduit à :
Si cette fonction renvoie le bon résultat, les valeurs un tant soit peu élevées de n donnent des calculs longs (essayer fibo(37)).
Une analyse de complexité explique ce temps de calcul. Si Tn désigne le nombre d’opérations pour calculer fibo(n), on obtient la relation de récurrence Tn+2=Tn+1+Tn+1. Or cette suite croît encore plus vite que la suite de Fibonacci, qui a déjà un comportement exponentiel.
2) Fonction récursive avec mémoïsation
Une solution possible consiste à garder en mémoire les termes de la suite déjà calculés. Cette technique de mémoïsation (procédé où on garde en mémoire les valeurs déjà calculées) peut par exemple être traitée en créant un dictionnaire qui stocke ces valeurs, ainsi qu’une fonction locale :
