Récursivité: Série d'exercices Exercice 1 Ecrire une procédure qui affiche les entiers par ordre décroissant, de n jusqu’à 1. Proposer une solution itérative et une autre récursive.

Exercice 2 Soit la procédure itérative suivante :

procedure affiche; var a, b: integer; begin for a := 0 to 3 do for b := 0 to 9 do writeln(a * 10 + b); end;

Transformer cette procédure en une procédure récursive.

Exercice 3 Ecrire une fonction récursive permettant de calculer la factorielle d’un entier N donné.

Exercice 4 On appelle "palindrome" un mot ou une phrase qui se lit de la même façon à l'endroit comme à l'envers, sans tenir compte des espaces. Exemple : le mot "ABCBA" est un palindrome. Ecrire une fonction récursive permettant de vérifier si une chaîne de caractères CH est un palindrome.

Exercice 5 Ecrire une fonction récursive permettant de vérifier la parité d’un entier N.

Exercice 5 Ecrire une fonction récursive permettant de tester les multiples de 5.

Exercice 6 Ecrire une fonction récursive permettant d'effectuer la multiplication de deux entiers positifs (notés p et q) donnés, en utilisant uniquement l'addition entière. En effet, pxq = p+p+p+…+p (q fois). Exercice 7 Ecrire une fonction récursive permettant de calculer la somme des N premiers entiers.

Exercice 8 Ecrire une fonction récursive permettant de calculer Xn pour X réel et n entier relatif.

Exercice 9 Ecrire une fonction récursive permettant de calculer le PGCD de deux entiers A et B par la méthode d' EUCLIDE puis la méthode de différence.

Exercice 10 Ecrire une fonction récursive permettant de calculer le PPCM de deux entiers A et B.

Exercice 11 La suite de Fibonacci est définie par : Un = Un-1 + Un-2 avec U1 = 1 et U2 = 1. Ecrire une fonction récursive permettant de calculer le Nème terme de la suite de Fibonacci.

Exercice 12 Ecrire une procédure récursive permettant de décomposer un entier N en facteurs premiers. (Exemple : 432 = 2*2*2*2*3*3*3).

Série d’exercices proposée par FENNI-Salah (Lycée Chebba) Page 1/4

Exercice 13 Un nombre parfait est un nombre qui est égale à la somme de ses diviseurs sauf lui même exemple : 6 est parfait car 6=1+2+3 Ecrire une fonction récursive qui vérifie si un entier N est parfait ou non. Exercice 14 Un entier supérieur à 1 est dit premier s’il n’est divisible que par 1 et par lui-même. Ecrire une fonction récursive qui vérifie si un entier N est premier ou non. Exercice 15

Soit l’exponentielle :

2 3

1 .1 2 ! 3 !

nx x x x xe

n. .

!+ + + + +

Faire une fonction fact(n) qui renvoie n!. Faire une fonction puiss(x,n) qui renvoie xn. Ecrire une fonction récursive qui calcule la valeur approchée de ex en faisant appel aux fonctions fact et puiss. Exercice 16 Ecrire une fonction récursive qui permet de chercher le maximum d'un tableau T de n entiers. Exercice 17 Ecrire une fonction récursive qui détermine la valeur la plus proche d'un entier m donné dans un tableau T de n entiers. Exercice 18 Ecrire une fonction récursive qui teste l'existence d'un élément donné dans un tableau donné en utilisant une recherche séquentielle. Exercice 19 Ecrire une fonction récursive qui teste l'existence d'un élément donné dans un tableau donné en utilisant une recherche dichotomique. Exercice 20 Ecrire une procédure récursive qui permet de décaler tous les éléments d’un tableau d’une position à droite à partir de la position p.

Exercice 21 Voici une procédure récursive qui permet d’inverser les éléments d’une partie d’un tableau compris entre la position p et n.

Exercice 22 Ecrire une fonction récursive qui détermine la valeur maximale de deux entiers positifs sans utiliser < et >. Exercice 23 Soit une chaîne de caractères ; supposons qu'on veuille faire aussi bien la fonction que la procédure qui nous renvoie l'inverse de cette chaîne.

Exercice 24 Ecrire une fonction récursive qui teste l'existence d'une lettre dans une chaîne de caractère donnée. Exercice 25 Ecrire une procédure récursive qui permet de trier un tableau de n entiers en utilisant la méthode de tri par sélection. Exercice 26 Ecrire une procédure récursive qui permet de trier un tableau de n entiers en utilisant la méthode de tri par insertion.

Série d’exercices proposée par FENNI-Salah (Lycée Chebba) Page 2/4

Exercice 27 Ecrire une procédure récursive qui permet de trier un tableau de n entiers en utilisant la méthode de tri à bulles. Exercice 28 Ecrire une procédure récursive qui permet de trier un tableau de n entiers en utilisant la méthode de tri Shell. Exercice 29 Ecrire une procédure récursive qui permet de trier un tableau de n entiers en utilisant la méthode de tri par fusion. Exercice 30 Le triangle de Pascal est le tableau des coefficients qui sont utilisés pour le développement de certaines expressions comme (a+b)² ou (a+b)n. Ce triangle est le suivant :

0 : 1 (a+b)0 = 1 1 : 1 1 (a+b)1 = 1*a + 1*b 2 : 1 2 1 (a+b)2 = 1*a2 + 2*a*b + 1*b2

3 : 1 3 3 1 (a+b)3 = 1*a3 + 3*a2*b + 3*a*b2 + 1*b3

4 : 1 4 6 4 1 (a+b)4 = 1*a4 + 4*a3*b + 6*a2*b2 + 4*a*b3 + 1*b4

Ecrire une fonction récursive permettant de déterminer les valeurs du triangle pascal. Exercice 31 Ecrire une fonction récursive calculant la fonction d'Ackermann définie comme suit :

n+1 si m = 0( , ) Ack (m-1, 1) si m > 0 et n = 0

Ack (m-1, Ack (m, n-1)) si m > 0 et n > 0 Ack m n

⎧⎪= ⎨⎪⎩

Calculer Ack(0,3) et Ack(2,2)

Exercice 32 Ecrire une fonction récursive MacCarthy qui calcule MacCarthy(n) selon la définition suivante :

Si n>100 MacCarthy(n) = n-10

Si n≤100 MacCarthy(n) = MacCarthy( MacCarthy(n+11))

Exercice 33 Evaluation d’une chaîne de caractère Soit une chaîne de caractères du type s="5+123-4+67-2" ; Ecrire une fonction récursive qui évalue cette chaîne de caractères. Exercice 34 Vers une mini-calculatrice Soit une chaîne de caractères du type s="5+3*4/2-5*3+4*7/2" ; faisons le programme qui évalue cette chaîne de caractères. Exercice 35 Ecrire un programme permettant d'évaluer un nombre romain en son équivalant en décimal. Sachant que les chiffres romains :

• M = 1000 • D = 500 • C = 100 • L = 50 • X = 10 • V = 5 • I = 1

Série d’exercices proposée par FENNI-Salah (Lycée Chebba) Page 3/4

On constate que les nombres s'arrêtaient aux milliers. Exemples d'écriture des nombres romains :

• 4 s'écrit IV. • 6 s'écrit VI. • 9 s'écrit IX. • 15 s'écrit XV. • 47 s'écrit XLVII. • 149 s'écrit CXLIX (et non CIL, comme on pourrait le penser) On constate ici la

décomposition 100+40+9 = C + XL + IX • 1490 s'écrit MCDXC = 1000 + 400 + 90 = M + CD + XC

Exercice 36 Supposons qu'on veuille faire un programme qui affiche les combinaisons (les différentes permutations de n objets) d'une chaîne de caractères ; par exemple les anagrammes des lettres de "abc" sont : "abc", "acb", "bac", "bca", "cab" et "cba".

Série d’exercices proposée par FENNI-Salah (Lycée Chebba) Page 4/4