Classe : 4me SI

Lyce de Benguardne
Srie N3 :

La Rcursivit

Ex1
Ecrire une fonction rcursive qui permet de calculer :

= 12 + 22 + 32 + 42 + + n2
Ex2
Ecrire une fonction rcursive qui permet de calculer la somme des chiffres dun entier positif:

Exemple :

N=528 la fonction renvoie 15 = 5 + 2 + 8

Ex3
Ecrire une fonction rcursive qui permet de convertir un nombre dcimal en binaire.

Ex4
Ecrire une fonction rcursive qui permet de calculer le nombre de voyelles dans une chane CH.

Exemple :

Si CH= BAC SI la fonction renvoie 2.

Ex5
Ecrire une fonction rcursive SOMME_TAB qui permet de calculer la somme des lments dun
tableau contenant des entiers.

Ex6
Ecrire une fonction rcursive VERIF_PAIR qui permet de vrifier si un entier est pair ou non.

Ex7
Ecrire une fonction rcursive qui permet de calculer le PGCD de deux entiers positifs.

Ex8
Ecrire une fonction rcursive INVERSER qui permet dinverser une chane de caractres CH.

Ex9
Ecrire une fonction rcursive qui permet de vrifier lexistence dun caractre dans une chane
CH.

Ex10
Ecrire une fonction rcursive qui permet de vrifier si une chane de caractre est palindrome.

Lyce Benguardne

Ex11
Ecrire une fonction rcursive qui permet de calculer la suite de Fibonnacci dfinie par :

Ses premiers termes sont donc : 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...

Ex12
Ecrire une fonction rcursive qui permet de calculer la puissance an

Ex13
Ecrire une fonction rcursive qui permet de calculer a*b en utilisant le principe de la
multiplication russe.
La multiplication Russe est une mthode particulire permettant la multiplication de deux entiers A et B
en utilisant seulement la multiplication par 2, la division par 2 et laddition.
Exemple : pour A =17 et B = 19, le produit de A par B se fait comme suit :
A

17

19

Le premier nombre est divis par 2 (division entire) et le deuxime est multipli par 2 : on aura
8
38
Le processus se rpte jusqu avoir dans la premire colonne 1 :
17
8
4
2

19
38
76
152
304

Le rsultat est la somme des nombres de la deuxime colonne qui sont en face des nombres impairs de la
premire colonne (donc les nombres de la deuxime colonne qui sont en face des nombres pairs de la
premire colonne seront ignors).
17
19
8
38
4
76
2
152
1
304
17*19= 19+304=323

Lyce Benguardne

ignor
ignor
ignor

Ex14
Ecrire une fonction rcursive qui permet de vrifier lexistence dun lment dans un tableau en
utilisant le principe de recherche squentielle.

Ex15
Ecrire une fonction rcursive qui permet de vrifier lexistence dun lment dans un tableau en
utilisant le principe de recherche dichotomique.

Ex16
Soit la fonction
0) Fonction SCALAIRE (A, B : tab ; n : entier) : entier
1) P A[n] * B[n]
Pour i de n-1 1 (pas=-1) faire
P p + A[i] * B[i]
Fin pour
2) Scalaire p
3) Fin SCALAIRE
Questions :
1) Excuter la main la fonction pour les valeurs suivantes :
A

2) Prciser le rle de cette fonction.

3) Transformer cette fonction en une fonction rcursive.

Ex17
Ecrire une fonction rcursive contigu (chane comporte deux occurrences successives de mme
caractre) qui dtermine si une chane comporte deux caractres contigus identiques.
Exemples :
Contigu (masse) renvoie vrai
Contigu (escalier) renvoie faux
Contigu (a) renvoie faux

Ex18
Ecrire une fonction rcursive qui permet de tester si un tableau est symtrique ou non.

Ex19
Soit la fonction MacCarthy dfinie par :
Pour N>100 MacCarthy(n) = n-10
Pour N100 MacCarthy(n) = MacCarthy (MacCarthy (n+11))
Exemple :
MacCarthy(100) vaut 91
Ecrire une fonction rcursive MacCarthy.

Lyce Benguardne

Ex20
a) Ecrire une fonction rcursive qui permet de calculer la somme suivante :

S(n) =
b) Ecrire une fonction rcursive qui permet calculer le N ime terme de la suite U dfinie par :

Ex21
Ecrire lanalyse puis lalgorithme dun module rcursif qui permet dafficher les caractres dune
chane sous la forme indique dans lexemple suivant :
Exemple : Soit la chane "TURBO"
TURBO
TURB
TUR
TU
T

Ex22
Ecrire une fonction rcursive qui transforme une chane en majuscules.

Ex23
Ecrire une fonction rcursive qui transforme une chane en minuscules.

EX24
Soit la fonction suivante :
0) Fonction Ghost (x, n :entier) :
1) Si n=1 alors Ghost (n=1)
Sinon si (x mod n = 0) alors Ghost (x< n-1)
Sinon Ghost Ghost (x, n-1)
Fin si
2) Fin Ghost
Questions :
1) Quel est le type de la fonction ?
2) Excuter la main cette fonction pour x=7 et n=6. (laisser une trace dexcution)
3) Quel est le rle de la fonction si les paramtres dappel sont x, x-1 : Ghost (x,x-1)
Lyce Benguardne

EX25
program ex;
uses wincrt;
var
a,b:word;
function calcul (a,b:word):word;
begin
if b=0 then calcul:=0
else if (a mod b=0) then calcul:=b+calcul(a, b-1)
else calcul:=calcul(a,b-1);
end;

begin
repeat
write('Saisir un entier strictement positif: ');
readln(a);
until (a>0);
b:=a div 2;
write('Rsultat= ',calcul(a,b));
end.

Travail demand :
Complter le tableau ci-dessous en excutant manuellement le programme avec les diffrentes
valeurs de a.
Contenu de a
Contenu de b
Rsultat
6
15
19
28

EX26
Soit la fonction Quoi suivante :
0) Fonction Quoi (n : .) : .
1) Si n=0 alors quoi "0"
Sinon si n=1 alors Quoi "1"
Sinon Quoi Quoi (n-1) + Quoi (n-2)
Fin si
2) Fin Quoi
Questions :
1) Complter lentte de cette fonction
2) Excuter manuellement la fonction Quoi pour les exemples suivants Quoi (3) et Quoi (4).
3) Quel est lordre de rcurrence de cette fonction ?

Lyce Benguardne

EX27
Ecrire lalgorithme dun module rcursif qui permet de vrifier lexistence dune chane CH1
dans une deuxime chane CH2 en respectant les conditions suivantes :
CH1 et CH2 sont deux chanes non vides.
On ne dois pas utiliser des fonctions prdfinies
Exemples :
CH1= "apta" existe dans la chane CH2="adaptable"
CH1= "apte" nexiste pas dans la chane CH2="adaptable"

EX28
Soit la fonction algorithmique suivante :
0) FONCTION TOTO (A, B : ENTIER) : ENTIER
1) SI A = 1
ALORS
TOTO B
SINON
SI A MOD 2 = 1
ALORS
TOTO B + TOTO (A DIV 2 , B * 2 )
SINON
TOTO TOTO (A DIV 2 , B * 2 )
FINSI
2) FIN TOTO
Travail faire :
a) Excuter cette fonction pour les diffrentes valeurs de A et B suivantes :
20
6
5
A
10
6
13
B
.. .. ..
Rsultat de TOTO
b) Quel est le rle de cette fonction ?

EX29
Soit lalgorithme de la fonction suivante :

Questions

0) fonction inconnu (n : entier) : entier

1) S1
i 1
Rpter
i i + 2
S S+ i
Jusqu' (i = 2*n -1)
2) inconnu S
3) fin inconnu

a) Faire un tournage la main de cet algorithme avec les valeurs de n suivantes : n= 3 et 4.

b) Quel est le rle de cette fonction?
c) Rcrire lalgorithme de la fonction inconnu en utilisant un procd rcursif.
Lyce Benguardne

EX30
Soit la fonction suivante :
Function quoi (CH:string; x:char; P:integer):integer;
Begin
If

length (CH)=0 then quoi :=0

Else if CH [1] = X then

quoi :=P

Else quoi :=quoi (copy (CH, 2, length (CH)-1), X, P+1);

End;
1. Excuter, manuellement, la fonction quoi pour les exemples suivants de chanes :

Quoi (Bonne,n, 1)

Quoi (chance,A, 1)

Quoi (4SI,S, 1)

2. Dduire le rle de la fonction. Et trouver quelle est la fonction prdfinie par Pascal qui peut raliser le
mme traitement.
3. Lorsquon a excut le module quoi pour la chane suivante (azertyuiopqsdfghjklm), et le caractre
(b), la fentre ci-dessous sest dclenche. Expliquer pourquoi ?
Erreur
Runtime error 202 at 0001: 000D
4. En dduire la(es) limite(s) dune solution rcursive.

Ex31
Soit la fonction suivante :
0) Fonction Accepter (ch : .) : .
1) i 1
test vrai
rpter
Test Majus(ch[i]) dans ["A".."Z"]
I I + 1
jusqu' (test=faux) ou (i=long(ch))
2) Accepter test
3) Fin Accepter
Questions :
1) Complter les donnes manquantes
2) Quel est le rle de cette fonction ?
3) Proposer une forme rcursive de cette fonction.
Lyce Benguardne

Ex32
Ecrire une fonction rcursive de type boolen qui vrifie si un entier A est divisible par un entier B
ou non sans lutilisation des oprateurs "/", "MOD", "DIV"
On suppose que A>0, B>0 et A>B

Ex33 (Ex1 session de contrle 2009)

Soient T un vecteur de n entiers, m un autre entier et f une fonction dfinie de la fonction
suivante :
f(m, n, T)= VRAI si (T[n]=m)
= f (m, n-1, T)
sinon

pour tout n0.

f(m, 0, T) = FAUX
1. Donner la trace dexcution de la fonction f pour les cas suivants :

T
T

; m=6 et n=4
;

m=1 et n=4

Questions
2. En dduire le rle de la fonction
3. Ecrire un algorithme rcursif de la fonction f.
4. Donner sous forme dun algorithme la itrative de la fonction f.

Ex34 (Ex1 session principale 2009)

Soit la fonction inconnu1 suivante :
0) Fonction inconnu1 (x :rel ; n :entier) : rel
1) Si (n=0) alors
Inconnu1 1
Sinon
Inconnu1 x * inconnu1 (x, n-1)
2) Fin inconnu1
Soit la fonction inconnu2 suivante :
0) Fonction inconnu2 (n, p : entier) : entier
1) Si (p=0) ou (p=n) alors
Inconnu2 1
Sinon
Inconnu2 inconnu2 (n-1, p) + inconnue (n-1, p-1)
Fin si
2) Fin inconnu2

Lyce Benguardne

Questions :
1- Quel est lordre de rcurrence de chacune des deux fonctions inconnu1 et inconnu2 ?
2- Excuter manuellement inconnu1 (2,3) et inconnu2 (3,2).
3- Donner le rle de chaque fonction
4- Ecrire un algorithme dune procdure permettant dafficher lcran le dveloppement du
binme (x+1)n en un polynme en x pour un entier n donne.
On rappelle que la formule du binme est :

(x+1)n =

xk =

x0 +

x1 + +

xn-1 +

xn

Sur lcran laffichage du terme xk se fera sous la forme x^k.

Ex35 (Ex1 Examen synthse 1-2009)

Soit la fonction f suivante:

function f (a,b: integer):integer;

begin
if (a=0) or (b=0) then
f :=0
else if b=1 then
f: =a
else
f:= a + f (a,b-1);
end;
Questions :
1- Indiquer le (les) condition (s) darrt de cette fonction rcursive.
2- Excuter cette fonction pour : a=5, b=4. Quel est le rle de cette fonction rcursive ?
3- Ecrire le programme principal (en Pascal, qui fait appel cette fonction tout en traitant les cas :
a et b ngatifs, a ou b ngatif, a et b positifs.

Ex36 (Ex2 Examen synthse 2- 2009)

Soit la fonction suivante :
0) Fonction Anonyme (a, b : entier) : entier
1) Si (a>b) alors
Xa
Tant que (X mod b 0) faire
XX+a
Fin Tant que
Anonyme X
Sinon
Anonyme Anonyme (b, a)
Fin si
2) Fin Anonyme

Lyce Benguardne

Questions :
1- Excuter cette fonction pour les valeurs suivantes de a et b :
a=6 et

b=4

a=2 et b=6

2- Dduire le rle de cette fonction

3- Utiliser cette fonction pour crire une analyse dun module qui calcule la somme entre deux
fractions en dterminant un dnominateur commun.
Exemple :
NB : une fraction est une structure qui renferme deux champs : le numrateur et le dnominateur.

Ex37 (Ex1 Bac Blanc- 2009)

On demande danalyser une fonction rcursive CHTOVAL permettant de convertir une chane
forme de chiffres en sa valeur entire, sans utiliser la procdure prdfinie VALEUR. On
suppose que la chane est forme uniquement de chiffres et quelle peut tre vide.
NB : vous pouvez utiliser la fonction prdfinie ORD
Exemples :
CHTOVAL ("147") = 147
CHTOVAL ("") = 0

Ex38 (Ex2 CONT THEO 2- 2009)

Soit la fonction suivante crite en Pascal :
Function Inconnu (n: integer; T: tab): ;
Var

Begin
i := 0 ;
Repeat
i := i+1 ;
rep := T[i] > T[i+1];
until (i=n-1) or (Not rep);
Inconnu := rep;
End;
Questions
1. Complter lentte de la fonction ainsi que la partie dclaration.
2. Quel est le rle de cette fonction ?
3. Ecrire une version rcursive de cette fonction.

Lyce Benguardne

10