:: Enseignements :: Licence :: L2 :: 2007-2008 :: Programmation Avancée en C :: Travaux dirigés ::

Récursivité

La récursivité est une méthode de programmation très puissante. Elle permet d'écrire des programmes faciles à comprendre et souvent efficaces bien que son principal inconvénient est d'obliger le compilateur à utiliser une pile pour mémoriser les calculs intermédiaires.

Exercice 1 - Etrange

Après exécution du programme suivant, qu'a-t-on en sortie ? Que fait la fonction Etrange et en particulier, à quel moment a lieu le "passage à la ligne" ?

#include<stdio.h>

void Etrange(int n) {
if(n <=0) {
printf("\n");
} else {
Etrange(n - 1);
printf("%d ", n);
}
}

En déduire une fonction récursive qui affiche les n premiers entiers dans l'ordre croissant et une autre qui les affiche dans l'ordre décroissant.

Exercice 2 - Recherche dichotomique

On rappelle que l'idée de la recherche par dichotomie d'un élément x dans un tableau trié dans l'ordre croissant est le suivant:

On compare x avec l'élément m du milieu du tableau:

si x = m, on a alors trouvé une solution;
si x < m, x ne peut pas se trouver après m dans le tableau; il suffit alors de le rechercher dans la partie à gauche du tableau;
si x > m, x ne peut pas se trouver avant m dans le tableau; il suffit alors de le rechercher dans la partie à droite du tableau

Quand peut-on conclure que x n'est pas présent dans le tableau ?

Donnez une fonction récursive qui traduit cet algorithme.

Exercice 3 - Monnayeur

Etant donné une suite d'entiers strictement croissante et un entier strictement positif S, déterminer un ensemble d'entiers positifs {} tels que