Récursivité dans l'algorithmique et la programmation/Exercices/Algorithmes récursifs

Fibbonacci revisité

Nous avons vu un algorithme (dit naïf) qui calcule le n^ième terme de la suite de Fibbonacci :

Début de l'exemple

Algorithme récursif pour calculer le n^ième terme de la suite de Fibbonacci

Fin de l'exemple

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 ?

Solution

La trace correcte de Fibb(5) est

Les appels récursifs ne se partagent pas est incorrect.

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\times F_{n}-2$

 

2. L'algorithme est-il terminal ? Justifiez la réponse.

Solution

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 à

$tmp_{1}\leftarrow {\mbox{Fibb}}(n-1)$

$tmp_{2}\leftarrow {\mbox{Fibb}}(n-2)$

$\mathbf {retourner} \ \ tmp_{1}+tmp_{2}$

 

Début de l'exemple

Algorithme récursif pour calculer le n^ième terme de la suite de Fibbonacci (version 2)

Fin de l'exemple

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 ?

Solution

${\begin{array}{lcrcl}Fibb(5,a,b)&&a=5+3=8&&b=5\\\downarrow &&\scriptstyle {a\leftarrow a+b}&\uparrow &\scriptstyle {b\leftarrow a}\\Fibb(4,a,b)&&a=3+2=5&&b=3\\\downarrow &&\scriptstyle {a\leftarrow a+b}&\uparrow &\scriptstyle {b\leftarrow a}\\Fibb(3,a,b)&&a=2+1=3&&b=2\\\downarrow &&\scriptstyle {a\leftarrow a+b}&\uparrow &\scriptstyle {b\leftarrow a}\\Fibb(2,a,b)&&a=1+1=2&&b=1\\\downarrow &&\scriptstyle {a\leftarrow a+b}&\uparrow &\scriptstyle {b\leftarrow a}\\Fibb(1,a,b)&&a=1+0=1&&b=1\\\downarrow &&\scriptstyle {a\leftarrow a+b}&\uparrow &\scriptstyle {b\leftarrow a}\\Fibb(0,a,b)&\longrightarrow &a=1&&b=0\\\end{array}}$

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.

Solution

L'algorithme est terminal car :

1. seul un appel récursif est fait à la fois (ligne 8)
2. 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 ?

Solution

La trace est :

${\begin{array}{lcrcl}Fibb(5,a,b)&&a=5+3=8&&b=5\\\downarrow &&\scriptstyle {a\leftarrow a+b}&\uparrow &\scriptstyle {b\leftarrow a}\\Fibb(4,a,b)&&a=3+2=5&&b=3\\\downarrow &&\scriptstyle {a\leftarrow a+b}&\uparrow &\scriptstyle {b\leftarrow a}\\Fibb(3,a,b)&&a=2+1=3&&b=2\\\downarrow &&\scriptstyle {a\leftarrow a+b}&\uparrow &\scriptstyle {b\leftarrow a}\\Fibb(2,a,b)&&a=1+1=2&&b=1\\\downarrow &&\scriptstyle {a\leftarrow a+b}&\uparrow &\scriptstyle {b\leftarrow a}\\Fibb(1,a,b)&&a=1+0=1&&b=1\\\downarrow &&\scriptstyle {a\leftarrow a+b}&\uparrow &\scriptstyle {b\leftarrow a}\\Fibb(0,a,b)&\longrightarrow &a=1&&b=0\\\end{array}}$

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 :

${\begin{array}{lcrcl}Fibb(5,a,b)\\\downarrow \\Fibb(4,a,b)\\\downarrow \\Fibb(3,a,b)\\\downarrow \\Fibb(2,a,b)\\\downarrow \\Fibb(1,a,b)\\\downarrow \\Fibb(0,a,b)&\longrightarrow &a=1&&b=0\\\end{array}}$

• Dans un second temps, on remonte en effectuant toujours les mêmes opérations $a\gets a+b$ et $b\gets a$, c’est la partie :

${\begin{array}{rcl}a=5+3=8&&b=5\\\scriptstyle {a\leftarrow a+b}&\uparrow &\scriptstyle {b\leftarrow a}\\a=3+2=5&&b=3\\\scriptstyle {a\leftarrow a+b}&\uparrow &\scriptstyle {b\leftarrow a}\\a=2+1=3&&b=2\\\scriptstyle {a\leftarrow a+b}&\uparrow &\scriptstyle {b\leftarrow a}\\a=1+1=2&&b=1\\\scriptstyle {a\leftarrow a+b}&\uparrow &\scriptstyle {b\leftarrow a}\\a=1+0=1&&b=1\\\scriptstyle {a\leftarrow a+b}&\uparrow &\scriptstyle {b\leftarrow a}\\a=1&&b=0\\\end{array}}$

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 :