Récursivité dans l'algorithmique et la programmation/Exercices/Algorithmes récursifs
Fibbonacci revisité
modifierNous avons vu un algorithme (dit naïf) qui calcule le nième terme de la suite de Fibbonacci :
Tracez Fibb(5). Combien cet appel génère-t-il d'appels récursifs ? Combien au maximum y a-t-il d'appels imbriqués ?
La trace correcte de Fibb(5) est
Les appels récursifs ne se partagent pas |
Donc un appel à Fibb(5) génère 14 appels récursifs. Le nombre maximum d'appels imbriqués est de 4.
Remarques
D'une manière générale, quand on calcule Fibb(n), l'imbrication maximale sera n-1, et le nombre d'appels récursifs sera
2. L'algorithme est-il terminal ? Justifiez la réponse.
L'algorithme n’est pas terminal, car pour retourner une valeur en ligne 8 on fait deux appels récursifs dont on additionne le résultat. La ligne 8 est équivalente à
3. Tracez Fibb2(5). Combien cet appel génère-t-il d'appels récursifs ? Combien au maximum y a-t-il d'appels imbriqués ?
Cet appel génère 5 appels récursifs, l'imbrication maximale est de 5 aussi.
4. L'algorithme est-il terminal ? Justifiez la réponse.
L'algorithme est terminal car :
- seul un appel récursif est fait à la fois (ligne 8)
- les données renvoyées sont
- soit des constantes (lignes 4-5)
- soit des valeurs issues de l'appel récursif (lignes 9-10)
Le fait des les manipuler entre-elles ne modifie pas la terminalité d'un algorithme.
5. Pouvez-vous tirer de la trace donnée dans la réponse 3 un algorithme itératif de Fibb2 ?
La trace est :
On remarque qu’il y a deux temps distincts.
- Dans un premier temps, les appels récursifs s'enchaînent jusqu'à trouver la condition d'arrêt. C’est la partie :
- Dans un second temps, on remonte en effectuant toujours les mêmes opérations et , c’est la partie :
Donc pour construire une version itérative de cet algorithme, il faut dans un premier temps faire l'initialisation de la condition d'arrêt, suivie de la répétition de n fois les opérations effectuées lors de la remontée. Cela donne :