Scribd
Importer
48 vues1 page

Exercices de récursivité en algorithmique

Le document présente des exercices sur la récursivité, incluant des algorithmes pour calculer des fonctions comme celle de Fibonacci et une suite définie par une relation de récurrence. Chaque exercice demande de tracer l'algorithme, d'en déduire son fonctionnement et de fournir des implémentations en langage C. L'objectif est d'explorer les concepts de récursivité et d'itération à travers des exemples pratiques.

Transféré par

Faiçal Bhar
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
48 vues1 page

Exercices de récursivité en algorithmique

Le document présente des exercices sur la récursivité, incluant des algorithmes pour calculer des fonctions comme celle de Fibonacci et une suite définie par une relation de récurrence. Chaque exercice demande de tracer l'algorithme, d'en déduire son fonctionnement et de fournir des implémentations en langage C. L'objectif est d'explorer les concepts de récursivité et d'itération à travers des exemples pratiques.

Transféré par

Faiçal Bhar
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Exercices sur la récursivité

Exercice 1 :
Soit la fonction suivante :
Entier f(entier i, entier n)

Debut
Si (n=0) ou (n=1) alors retour (1)

Sinon si T[i] £ T [i+1] alors retour ( f(i+1, n-1) )


Sinon retour (0)
fin
Où T est un tableau d’entiers.

a) Faire une trace de l’algorithme pour l’appel f(0, 5) et T= 5 9 17 20 35


b) En déduire ce que fait l’algorithme.
c) Ecrire le pg C correspondant et le tester

Exercice2 :
La fonction de Fibonacci est définie par :
F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2 si n > 2

1- donner l’algorithme récursif pour calculer le terme général Fn .


2- donner la trace de l’algorithme précédent pour F3 et F4. En déduire
pourquoi l’algorithme récursif pour Fibonacci est inefficace.
3- Donner l’algorithme itératif pour calculer Fn
4- Tester les programmes C récursif et itératif

Exercice 3 :

Soit la suite définie par le terme général suivant :

un = 5*un-1 +2*un-2 +1 pour n>=2

u0=0 ; u1=1

Objectif: calcul de la somme des 20 premiers termes de la suite.

1. Ecrire une fonction récursive termegeneral qui calcule le terme général.


2. Ecrire une autre fonction qui utilise la fonction précédente pour le calcule de
la somme.
3. Donner et tester le programme C correspondant

[Tapez ici]
[Link] fiches pédagogiques

Vous aimerez peut-être aussi