Notion de récursivité

Exercice 1 :

Ecrire une fonctions récursive qui calcule la factorielle d’un nombre entier N.
N.B :
                N ! = 1*2*3*…….*N


Solution :
Pour écrire la forme récursive d’une fonction, il faut chercher tout d’abord la récurrence mathématique, sinon la récursivité n’est pas utilisable.
Dans le cas du calcul de la factorielle, la récurrence mathématique peut se présenter comme suit :
                0 ! = 1
                N ! = N*(N-1) !

Fonction factorielle (N : entier) () : entier;
Debut
                Si N=0 alors
                               Retour (1) ;
                Sinon
                                Retour(N*factorielle(N-1)()) ;
                Finsi  
fin

Exercice 2 :

Ecrire une fonction récursive qui calcule le Nième terme da la suite de Fibonacci définie comme suit :
F0 = 1
F1= 1
Fn =Fn-2  + Fn-1         pour tout n >2


Solution :
Fonction fibonacci (N : entier) () : entier;
Debut
                Si N<= 2 alors
                               Retour (1) ;
                Sinon
                                Retour(fibonacci(N-2)() +fibonacci(N-1)());
                Finsi  
fin

Exercice 3 :

Ecrire une fonction récursive qui calcule la somme de  N premiers nombres entiers naturels :
S=1+2+3+……+N


Solution :
Pour écrire la forme récursive de la fonction somme, il faut chercher tout d’abord la récurrence mathématique.
                               S(0) = 0
                               S(N)=N+S (N-1)

Fonction somme (N : entier) () : entier;
Debut
                Si N=0 alors
                               Retour (N) ;
                Sinon
                                Retour( N+somme(N-1)());
                Finsi  
fin

Exercice 4 :

Ecrire une fonction récursive qui calcule le Nième terme da la suite numérique  définie comme suit :
U0 = 2
U1= 2
U2= 2
Un =6*Un-1  + 4*Un-2 - 5*Un-3               pour tout n >2


Solution :
Fonction suite (N : entier) () : entier;
Debut
                Si N<= 3 alors
                               Retour (2) ;
                Sinon
                                Retour(6*suite(N-1)() + 4*suite(N-2)() – 5*suite(N-3)()) ;
                Finsi  
fin

Exercice 5 :

Ecrire une fonction récursive qui calcule les valeurs de polynôme d’Hermite Hn(x)  définie comme suit :
H0(x) = 1
H1(x) = 2*x
Hn (x)=2*x*Hn-1  (x) – 2(n-1)*Hn-2 (x)               pour tout n >1


Solution :
Fonction Hermite (N : entier,X : réel) () : entier;
Debut
                Si N= 0 alors
                               Retour (1) ;
                Sinon
                         Si N=1 alors
                                Retour(2*X);
                         Sinon
                               Retour(2*X*hermite(N-1,X)() + 2*(N-1)*Hermite(N-2,X)()) ;
                        Finsi
                Finsi  
fin
Suivant
« Précédent
Précédent
Suivant »

ConversionConversion EmoticonEmoticon

Remarque : Seul un membre de ce blog est autorisé à enregistrer un commentaire.