Leçons de niveau 13

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

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
Algorithmes récursifs
Image logo représentative de la faculté
Exercices no2
Leçon : Récursivité dans l'algorithmique et la programmation
Chapitre du cours : Algorithmes récursifs

Exercices de niveau 13.

Exo préc. :Introduction
Exo suiv. :Structure de données récursives
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Exercice : Algorithmes récursifs
Récursivité dans l'algorithmique et la programmation/Exercices/Algorithmes récursifs
 », n'a pu être restituée correctement ci-dessus.




Fibbonacci revisité[modifier | modifier le wikicode]

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

Début de l'exemple
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 ?

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

Début de l'exemple
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 ?

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

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