# 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 :
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
* 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.
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}$
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 ?
${\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.
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 :
${\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 :
| Introduction | Structure de données récursives |