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

{{Exercice
  | idfaculté = informatique
  | numéro    = 2
  | chapitre  = [[../../Algorithmes récursifs/]]
  | précédent = [[../Introduction/]]
  | suivant   = [[../Structure de données récursives/]]
  | niveau    = 13
}}

== Fibbonacci revisité  ==

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

{{Exemple
  | titre   = Algorithme récursif pour calculer le n<sup>ième</sup> terme de la suite de Fibbonacci
  | contenu =
[[Fichier:Algo_FcRec_Fibb_1.png|532px]]
}}

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
  | contenu =
La trace correcte de Fibb(5) est

[[Fichier:Algo_FcRec_Exo_Fibb_1_trace_5.png|703px]]

{{Attention
  | Avec_fond = oui
  | Les appels récursifs ne se partagent pas   
[[Fichier:Algo_FcRec_Exo_Fibb_1_trace_5_faux.png|182px]]  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 <math>2 \times F_{n}-2</math>
}}

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

{{Solution
  | contenu =
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 à

<math>tmp_1 \leftarrow \mbox{Fibb}(n-1)</math>

<math>tmp_2 \leftarrow \mbox{Fibb}(n-2)</math>

<math>\mathbf{retourner}\ \  tmp_1 + tmp_2</math>
}}

{{Exemple
  | titre   = Algorithme récursif pour calculer le n<sup>ième</sup> terme de la suite de Fibbonacci (version 2)
  | contenu =
[[Fichier:Algo_FcRec_Exercice_Fibbo2.png |442px]]
}}

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
  | contenu =
<math>
\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}
</math>

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
  | contenu = 
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)<br />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
  | contenu = 
La trace est :

<math>
\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}
</math>

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 :
<math>
\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}
</math> 

:* Dans un second temps, on ''remonte'' en effectuant toujours les mêmes opérations <math>a \gets a+b</math> et <math>b \gets a</math>, c’est la partie :
<math>
\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}
</math>

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 :

[[Fichier:Algo_FcRec_Exercice_FibboIter.png|519px]]
}}

{{Bas de page
  | idfaculté = informatique
  | précédent = [[../Introduction/]]
  | suivant   = [[../Structure de données récursives/]]
}}