Exemples d’utilisation de la récursivité

icône de pdf
Signaler

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.

56a5ae09-ce2a-4792-9bb5-b7c459bfbacf

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.

4f14ac8e-3087-45e2-b101-5068bdc42c47

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 à :

5505db72-4143-429d-92d6-f539ec5c2582

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 :

4f47f15c-2b16-4873-95ea-64dcdc175ca5