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

De testwiki
Aller à la navigation Aller à la recherche

Modèle:Exercice

Fibbonacci revisité

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

Modèle: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 ? Modèle:Solution

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

Modèle:Solution

Modèle: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 ?

Modèle:Solution

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

Modèle:Solution

5. Pouvez-vous tirer de la trace donnée dans la réponse 3 un algorithme itératif de Fibb2 ?

Modèle:Solution

Modèle:Bas de page

Récupérée de "https://fr.wikiversity.beta.math.wmflabs.org/w/index.php?title=Récursivité_dans_l%27algorithmique_et_la_programmation/Exercices/Algorithmes_récursifs&oldid=374"