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

De testwiki
Version datée du 22 août 2023 à 11:04 par imported>Crochet.david.bot (Robot : remplacement de texte automatisé (-\n(==={0,3})(?: *)([^\n=\s]+)(?: *)\1(?: *)\n +\n\1 \2 \1\n))
(diff) ← Version précédente | Version actuelle (diff) | Version suivante → (diff)
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"