Recursiviteeeeeeeeee

Lycée Benguardène 1

Ex1 Ecrire une fonction récursive qui permet de calculer :

= 12 + 22 + 32 + 42 + ………… + n2

Ex2 Ecrire une fonction récursive qui permet de calculer la somme des chiffres d’un entier positif: Exemple :

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

Ex3 Ecrire une fonction récursive qui permet de convertir un nombre décimal en binaire.

Ex4 Ecrire une fonction récursive qui permet de calculer le nombre de voyelles dans une chaîne CH. Exemple :

Si CH= BAC SI la fonction renvoie 2.

Ex5 Ecrire une fonction récursive SOMME_TAB qui permet de calculer la somme des éléments d’un tableau contenant des entiers.

Ex6 Ecrire une fonction récursive VERIF_PAIR qui permet de vérifier si un entier est pair ou non.

Ex7 Ecrire une fonction récursive qui permet de calculer le PGCD de deux entiers positifs.

Ex8 Ecrire une fonction récursive INVERSER qui permet d’inverser une chaîne de caractères CH.

Ex9 Ecrire une fonction récursive qui permet de vérifier l’existence d’un caractère dans une chaîne CH.

Ex10 Ecrire une fonction récursive qui permet de vérifier si une chaîne de caractère est palindrome.

Série N°3 : La Récursivité Classe : 4ème SI Lycée de Benguardène


Ex11 Ecrire une fonction récursive qui permet de calculer la suite de Fibonnacci définie par :

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

Ex12 Ecrire une fonction récursive qui permet de calculer la puissance an

Ex13 Ecrire une fonction récursive qui permet de calculer a*b en utilisant le principe de la multiplication russe. La « multiplication Russe » est une méthode particulière permettant la multiplication de deux entiers A et B

en utilisant seulement la multiplication par 2, la division par 2 et l’addition.

Exemple : pour A =17 et B = 19, le produit de A par B se fait comme suit :

A B

17 19

Le premier nombre est divisé par 2 (division entière) et le deuxième est multiplié par 2 : on aura

8 38 Le processus se répète jusqu’à avoir dans la première colonne 1 :

17 19 8 38 4 76 2 152

304

Le résultat est la somme des nombres de la deuxième colonne qui sont en face des nombres impairs de la première colonne (donc les nombres de la deuxième colonne qui sont en face des nombres pairs de la première colonne seront ignorés).

17 19

8 38 ignoré 4 76 ignoré 2 152 ignoré 1 304

17*19= 19+304=323

1


Ex14 Ecrire une fonction récursive qui permet de vérifier l’existence d’un élément dans un tableau en utilisant le principe de recherche séquentielle.

Ex15 Ecrire une fonction récursive qui permet de vérifier l’existence d’un élément 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) Exécuter à la main la fonction pour les valeurs suivantes :

A 3 0 2 7

B 5 6 7 0

2) Préciser le rôle de cette fonction.

3) Transformer cette fonction en une fonction récursive.

Ex17 Ecrire une fonction récursive contigu (chaîne comporte deux occurrences successives de même caractère) qui détermine si une chaîne comporte deux caractères contigus identiques.

Exemples : Contigu (masse) renvoie vrai

Contigu (escalier) renvoie faux

Contigu (a) renvoie faux

Ex18 Ecrire une fonction récursive qui permet de tester si un tableau est symétrique ou non.

Ex19 Soit la fonction MacCarthy définie par : Pour N>100 MacCarthy(n) = n-10 Pour N≤100 MacCarthy(n) = MacCarthy (MacCarthy (n+11)) Exemple :

MacCarthy(100) vaut 91 Ecrire une fonction récursive MacCarthy.


Ex20 a) Ecrire une fonction récursive qui permet de calculer la somme suivante :

S(n) =

b) Ecrire une fonction récursive qui permet calculer le N ième terme de la suite U définie par :

Ex21

Ecrire l’analyse puis l’algorithme d’un module récursif qui permet d’afficher les caractères d’une chaîne sous la forme indiquée dans l’exemple suivant :

Exemple : Soit la chaîne "TURBO"

TURBO

TURB

TUR

TU

T

Ex22 Ecrire une fonction récursive qui transforme une chaîne en majuscules.

Ex23

Ecrire une fonction récursive qui transforme une chaîne 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) Exécuter à la main cette fonction pour x=7 et n=6. (laisser une trace d’exécution) 3) Quel est le rôle de la fonction si les paramètres d’appel sont x, x-1 : Ghost (x,x-1)


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('Résultat= ',calcul(a,b));

end.

Travail demandé : Compléter le tableau ci-dessous en exécutant manuellement le programme avec les différentes valeurs de a.

Contenu de a Contenu de b Résultat

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) Compléter l’entête de cette fonction 2) Exécuter manuellement la fonction Quoi pour les exemples suivants Quoi (3) et Quoi (4). 3) Quel est l’ordre de récurrence de cette fonction ?


EX27

Ecrire l’algorithme d’un module récursif qui permet de vérifier l’existence d’une chaîne CH1

dans une deuxième chaîne CH2 en respectant les conditions suivantes :

CH1 et CH2 sont deux chaînes non vides.

On ne dois pas utiliser des fonctions prédéfinies

Exemples :

CH1= "apta" existe dans la chaîne CH2="adaptable"

CH1= "apte" n’existe pas dans la chaîne 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) Exécuter cette fonction pour les différentes valeurs de A et B suivantes :

A 20 6 5

B 10 6 13

Résultat de TOTO …………………….. …………………….. ……………………..

b) Quel est le rôle de cette fonction ?

EX29

Soit l’algorithme de la fonction suivante :

0) fonction inconnu (n : entier) : entier 1) S1

i 1 Répéter

i i + 2 S S+ i

Jusqu'à (i = 2*n -1) 2) inconnu S 3) fin inconnu

Questions

a) Faire un tournage à la main de cet algorithme avec les valeurs de n suivantes : n= 3 et 4. b) Quel est le rôle de cette fonction? c) Réécrire l’algorithme de la fonction inconnu en utilisant un procédé récursif.


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. Exécuter, manuellement, la fonction quoi pour les exemples suivants de chaînes :

Quoi (‘Bonne’,’n’, 1)

Quoi (‘chance’,’A’, 1)

Quoi (‘4SI’,’S’, 1)

2. Déduire le rôle de la fonction. Et trouver quelle est la fonction prédéfinie par Pascal qui peut réaliser le même traitement.

3. Lorsqu’on a exécuté le module quoi pour la chaîne suivante (‘’azertyuiopqsdfghjklm’’), et le caractère (‘’b’’), la fenêtre ci-dessous s’est déclenchée. Expliquer pourquoi ?

4. En déduire la(es) limite(s) d’une solution récursive.

Ex31

Soit la fonction suivante : 0) Fonction Accepter (ch : ………….) : ………………. 1) i 1

test vrai répéter 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) Compléter les données manquantes 2) Quel est le rôle de cette fonction ? 3) Proposer une forme récursive de cette fonction.

Erreur

Runtime error 202 at 0001: 000D


Ex32

Ecrire une fonction récursive de type booléen qui vérifie si un entier A est divisible par un entier B ou non sans l’utilisation des opérateurs "/", "MOD", "DIV" On suppose que A>0, B>0 et A>B

Ex33 (Ex1 session de contrôle 2009)

Soient T un vecteur de n entiers, m un autre entier et f une fonction définie de la fonction suivante :

f(m, n, T)= VRAI si (T[n]=m) = f (m, n-1, T) sinon pour tout n≠0.

f(m, 0, T) = FAUX

1. Donner la trace d’exécution de la fonction f pour les cas suivants :

T 5 7 6 3 ; m=6 et n=4

1 2 3 4

T 5 7 6 3 ; m=1 et n=4

1 2 3 4

Questions 2. En déduire le rôle de la fonction 3. Ecrire un algorithme récursif de la fonction f. 4. Donner sous forme d’un algorithme la itérative de la fonction f.

Ex34 (Ex1 session principale 2009) Soit la fonction inconnu1 suivante :

0) Fonction inconnu1 (x :réel ; n :entier) : réel 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


Questions : 1- Quel est l’ordre de récurrence de chacune des deux fonctions inconnu1 et inconnu2 ? 2- Exécuter manuellement inconnu1 (2,3) et inconnu2 (3,2). 3- Donner le rôle de chaque fonction 4- Ecrire un algorithme d’une procédure permettant d’afficher à l’écran le développement du

binôme (x+1)n en un polynôme en x pour un entier n donnée. On rappelle que la formule du binôme est :

(x+1)n = xk = x0 + x1 + ……… + xn-1 + xn

Sur l’écran l’affichage du terme xk se fera sous la forme x^k.

Ex35 (Ex1 Examen synthèse 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) d’arrêt de cette fonction récursive. 2- Exécuter cette fonction pour : a=5, b=4. Quel est le rôle de cette fonction récursive ? 3- Ecrire le programme principal (en Pascal, qui fait appel à cette fonction tout en traitant les cas :

a et b négatifs, a ou b négatif, a et b positifs.

Ex36 (Ex2 Examen synthèse 2- 2009) Soit la fonction suivante :

0) Fonction Anonyme (a, b : entier) : entier 1) Si (a>b) alors

X a Tant que (X mod b ≠ 0) faire X X + a Fin Tant que Anonyme X

Sinon

Anonyme Anonyme (b, a)

Fin si

2) Fin Anonyme


Questions : 1- Exécuter cette fonction pour les valeurs suivantes de a et b :

a=6 et b=4 a=2 et b=6

2- Déduire le rôle de cette fonction 3- Utiliser cette fonction pour écrire une analyse d’un module qui calcule la somme entre deux

fractions en déterminant un dénominateur commun.

Exemple :

NB : une fraction est une structure qui renferme deux champs : le numérateur et le dénominateur.

Ex37 (Ex1 Bac Blanc- 2009) On demande d’analyser une fonction récursive CHTOVAL permettant de convertir une chaîne formée de chiffres en sa valeur entière, sans utiliser la procédure prédéfinie VALEUR. On suppose que la chaîne est formée uniquement de chiffres et qu’elle peut être vide. NB : vous pouvez utiliser la fonction prédéfinie 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. Compléter l’entête de la fonction ainsi que la partie déclaration.

2. Quel est le rôle de cette fonction ?

3. Ecrire une version récursive de cette fonction.

Documents

Recursiviteeeeeeeeee