Serie d'exercices (Récursivité)

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 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).

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 :
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 teste l'existence d'un élément donné dans un tableau donné en utilisant une recherche séquentielle.

Exercice 17

Ecrire une fonction récursive qui teste l'existence d'un élément donné dans un tableau donné en utilisant une recherche dichotomique.

Exercice 18

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 19

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 20

Ecrire une fonction récursive qui teste l'existence d'une lettre dans une chaîne de caractère donnée.

Exercice 21

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 22

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 23

Ecrire une procédure récursive qui permet de trier un tableau de n entiers en utilisant la méthode de tri par insertion.

Exercice 24

Ecrire une procédure récursive qui permet de trier un tableau de n entiers en utilisant la méthode de tri à bulles.

Exercice 25

Ecrire une procédure récursive qui permet de trier un tableau de n entiers en utilisant la méthode de tri Shell.

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 fusion.

Exercice 27

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.
Ecrire une fonction récursive permettant de déterminer les valeurs du triangle pascal.

Exercice 28

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 29

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 30
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 31

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
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 32

Supposons qu'on veuille faire un programme qui affiche les combinaisons d'une chaîne de caractères ; par exemple les anagrammes des lettres de "abc" sont "abc, acb, bac, bca, cab, cba".