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 :

F₀ = 1

F₁= 1

F_n =F_n-2  + F_n-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 :

U₀ = 2

U₁= 2

U₂= 2

U_n =6*U_n-1  + 4*U_n-2 - 5*U_n-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 H_n(x)  définie comme suit :

H₀(x) = 1

H₁(x) = 2*x

H_n (x)=2*x*H_n-1  (x) – 2(n-1)*H_n-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

• Tweet
• Share
• Share
• Share
• Share

Related Post