Université de Tunis Année Universitaire 2015/2016

Institut Supérieur de Gestion de Tunis, ISG Tunis Algorithmique et Structure de données II – 1ére L.F.I.G 1ére L.A.I.D

TD2

-| Récursivité |-
Exercice 1 :

Soit la fonction Guess définie comme suit :

int Guess (int x, int y)

{
if (x == y)
return x;
else
{
if (x > y)
return Guess (x-1, y) + Guess (x, y+1);
else
return Guess (x+1, y) + Guess (x, y-1);
}
}

Donner le résultat de l’exécution des fonctions suivantes : • Guess (3,1) • Guess (4,2) • Guess (2,5) et
• Guess (3,6)

Exercice 2 :

Transformer la procédure suivante en une fonction récursive :

Procédure Calcul (N : entier, var P : réel)

Var i : entier
P1
Pour i de 1 à N faire
PP*i
Fin Pour
Fin

Que fait cette fonction ?

Exercice 3 :

Ecrire une fonction récursive qui écrit un nombre décimal en valeur binaire.

Exercice 4 :

Ecrire une fonction récursive affichant un nombre décimal positif dans l’ordre inverse. Un nombre
entier est utilisé.

Exercice 5 :

Ecrire une fonction récursive qui permet de calculer les nombres de "Fibonacci" qui sont définis par :
Fibonacci (0) = 0,
Fibonacci (1) = 1,
et pour tout n > 1, Fibonacci (n) = Fibonacci (n-1) + Fibonacci (n-2)

1
Université de Tunis Année Universitaire 2015/2016
Institut Supérieur de Gestion de Tunis, ISG Tunis Algorithmique et Structure de données II – 1ére L.F.I.G 1ére L.A.I.D

Exercice 6 :

Ecrire une fonction récursive chiffre(n, k) qui permet de retourner le k-ième chiffre à partir de la droite
d'un entier n > 0.
Exemple :

Le 3ième chiffre à partir de la droite de 8724 est 7

Le 5ième chiffre à partir de la droite de 21327 est 2

Exercice 7 :

Ecrire une fonction récursive qui permet de calculer la valeur de la fonction d’Ackermann définie de la
manière suivante pour m ≥ 0 et n ≥ 0 :

Acker(m, n) = Acker(m-1, Acker(m, n-1))

Acker(0, n) = n+1 pour n > 0
Acker(m, 0) = Acker(m-1, 1) pour m > 0

Exercice 8 :

Ecrire une fonction récursive qui permet de calculer la somme des n (n ≥ 0) premiers termes (à partir de 1
jusqu’à n).

Exercice 9 :

Il s’agit de calculer la somme des entiers allant de 0 à un entier donné N et qui ont la même parité que N.

Exemple :

Pour la valeur 6, la fonction doit rendre la valeur 12. (6+4+2+0 = 12)

Pour la valeur 5, la fonction doit rendre la valeur 9. (5+3+1 = 9)

a) Écrire une fonction itérative permettant de résoudre ce problème.

b) Résoudre le même problème par une fonction récursive.

Exercice 10 :

On souhaite écrire une fonction calculant la division par 2 d'un entier sans utiliser l'opérateur / mais
seulement les opérateurs + et -. Pour cela on remarque la propriété suivante :

Ecrire cette fonction d’une manière récursive.

Exercice 11 :

On souhaite écrire une fonction calculant le produit de deux entiers m et n sans utiliser l'opérateur * mais
seulement les opérateurs + et -. Pour cela on remarque la propriété suivante :

Ecrire cette fonction d’une manière récursive.

2
Université de Tunis Année Universitaire 2015/2016
Institut Supérieur de Gestion de Tunis, ISG Tunis Algorithmique et Structure de données II – 1ére L.F.I.G 1ére L.A.I.D

Exercice 12 :

p
Ecrire une fonction récursive qui retourne Cn , le nombre de combinaisons de p éléments d'un ensemble
p
comportant n éléments. Une définition récursive de Cn est donnée par :

 Pour les cas de base :

 Pour le cas de récurrence : Cnp = Cn-1p-1 + Cn-1p

Exercice 13 :

Ecrire une fonction récursive qui permet de dire si un mot donné est un palindrome ou pas.

Exercice 14:

1. Ecrire une fonction récursive qui teste si deux tableaux d’entiers sont identiques. Résoudre le même
problème avec une fonction itérative.

2. Ecrire une fonction récursive qui compte le nombre d’occurrences d’un entier dans un tableau d’entiers.

3. En déduire une fonction qui teste si deux tableaux d’entiers contiennent les mêmes éléments sans tenir
compte de l’ordre dans lequel les éléments sont rangés.

Exercice 15 :

Écrire un programme récursif permettant de dessiner une pyramide d’étoiles selon un entier n donné,
avec n un nombre impair.

Exemple :

*
***
*****
*******
*********

Pour ce faire, vous devez :

1. Ecrire une fonction récursive, SAISIE( ), qui permet de faire la saisie d’un nombre impaire.

2. Ecrire une fonction récursive, ETOILE( ), qui permet de symboliser les étoiles.

3. Ecrire une fonction récursive, ESPACE( ), qui permet de faire les espaces au début de chaque ligne.

4. Ecrire une fonction récursive, DESSINER( ), qui permet de dessiner la pyramide d’étoiles.

5. Tester ces fonctions sous le programme main( ).

3
Université de Tunis Année Universitaire 2015/2016
Institut Supérieur de Gestion de Tunis, ISG Tunis Algorithmique et Structure de données II – 1ére L.F.I.G 1ére L.A.I.D

Exercice 16 :

Ecrire une fonction récursive qui retourne un tableau résultant de la concaténation de deux tableaux.

Exemple :

4 3 2 4 1 4 2

4 3 2 1 1 4 2

Exercice 17 :

Ecrire une fonction récursive qui additionne terme à terme les éléments de deux tableaux et retourne le
tableau résultant.