TP2 : La récursivité
TP2 : La récursivité
Programming, Math, etc. · exam
Fiche de révisionCorrigé
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce document présente un ensemble d'exercices pratiques (TP) sur la récursivité en langage C. Ces exercices visent à tester la compréhension des concepts fondamentaux de la récursivité, la capacité à écrire des fonctions récursives, ainsi que la manipulation de tableaux et de chaînes de caractères à travers des appels récursifs.
Il s'agit d'écrire une fonction récursive puissance qui calcule n à la puissance p, avec n > 0 et p ≥ 0.
La fonction est définie comme suit :
int puissance (int n, int p)
{
if(p==0)
return 1;
else
return (n * puissance(n, p-1));
}
Explication :
Le programme principal demande à l'utilisateur de saisir n et p, vérifie que n > 0 et p ≥ 0, puis affiche le résultat.
Réponse : La fonction calcule correctement n^p par récursion.
Écrire une fonction récursive somme qui calcule la somme des entiers de 1 à n, avec n > 0.
La fonction est définie ainsi :
int somme (int n)
{
if(n==1)
return 1;
else
return (n + somme(n-1));
}
Explication :
Le programme principal demande à l'utilisateur de saisir n > 0 et affiche la somme.
Réponse : La fonction calcule correctement la somme 1 + 2 + ... + n.
Écrire une fonction récursive fib qui calcule le n-ième terme de la suite de Fibonacci, avec n ≥ 0.
La fonction est définie par :
int fib (int n)
{
if(n==1 || n==0)
return n;
else
return (fib(n-1) + fib(n-2));
}
Explication :
Le programme principal demande à l'utilisateur de saisir n ≥ 0 et affiche le résultat.
Réponse : La fonction calcule correctement le terme de Fibonacci demandé.
Écrire une fonction récursive PGCD qui calcule le plus grand commun diviseur (PGCD) de deux entiers positifs a et b.
Deux méthodes sont proposées :
int PGCD(int a, int b)
{
if(a == b)
return a;
else if(a > b)
return PGCD(a - b, b);
else
return PGCD(a, b - a);
}
int PGCD(int a, int b)
{
if(a % b == 0)
return b;
else
return PGCD(b, a % b);
}
Le programme principal demande deux entiers positifs a et b, puis affiche leur PGCD.
Réponse : Les deux méthodes calculent correctement le PGCD, la deuxième méthode étant plus efficace.
Écrire la fonction récursive ack qui calcule la fonction d'Ackermann pour deux entiers m, n ≥ 0.
La fonction est définie par :
int ack(int m, int n)
{
if(m == 0)
return n + 1;
else if(n == 0)
return ack(m - 1, 1);
else
return ack(m - 1, ack(m, n - 1));
}
Le programme principal demande à l'utilisateur de saisir m et n ≥ 0 puis affiche le résultat.
Réponse : La fonction implémente correctement la fonction d'Ackermann, connue pour sa croissance très rapide.
Écrire une fonction récursive palindrome qui vérifie si une chaîne de caractères est un palindrome.
Première méthode :
int palindrome(char *ch, int i, int n)
{
if(i >= n)
return 1;
else if(ch[i] == ch[n])
return palindrome(ch, i + 1, n - 1);
else
return 0;
}
Explication :
Le programme principal lit une chaîne (max 10 caractères), puis affiche si elle est palindrome ou non.
Réponse : La fonction détecte correctement si la chaîne est palindrome.
Écrire deux fonctions récursives pour afficher un tableau d'entiers :
Première méthode :
void affiche(int *t, int i, int n)
{
if(i <= n - 1)
{
printf("%d |", t[i]);
affiche(t, i + 1, n);
}
}
void affiche_fin_debut(int *t, int i, int n)
{
if(i <= n - 1)
{
affiche_fin_debut(t, i + 1, n);
printf("%d |", t[i]);
}
}
Deuxième méthode :
void affiche(int *t, int n)
{
if(n >= 1)
{
affiche(t, n - 1);
printf("%d |", t[n - 1]);
}
}
void affiche_fin_debut(int *t, int n)
{
if(n >= 1)
{
printf("%d |", t[n - 1]);
affiche_fin_debut(t, n - 1);
}
}
Le programme principal demande la taille du tableau (1 à 10), puis les valeurs, et affiche le tableau dans les deux sens.
Réponse : Les deux méthodes fonctionnent correctement pour afficher un tableau dans les deux sens.
Écrire une fonction pour calculer la somme des éléments d'un tableau d'entiers, en version itérative et récursive.
Version itérative :
int somme(int *t, int n)
{
int s = 0, i;
for(i = 0; i < n; i++)
{
s = s + t[i];
}
return s;
}
Version récursive :
int somme(int *tab, int n)
{
if(n == 1)
return tab[n - 1];
else
return tab[n - 1] + somme(tab, n - 1);
}
Version récursive pour la somme des valeurs positives seulement :
int somme(int *tab, int n)
{
if(n < 0)
return 0;
else if(tab[n] > 0)
return tab[n] + somme(tab, n - 1);
else
return somme(tab, n - 1);
}
Le programme principal demande la taille (1 à 4), puis les valeurs, et affiche la somme.
Réponse : Les versions itérative et récursive calculent correctement la somme, la dernière version filtre les valeurs positives.
Écrire une fonction récursive maxtab qui retourne la valeur maximale d'un tableau d'entiers.
La fonction est définie par :
int maxtab(int *tab, int n, int max)
{
if(n == 1)
return max;
else if(tab[n - 1] > max)
return maxtab(tab, n - 1, tab[n - 1]);
else
return maxtab(tab, n - 1, max);
}
Le programme principal demande la taille (1 à 4), puis les valeurs, et affiche la valeur maximale.
Réponse : La fonction retourne correctement la valeur maximale du tableau.
Écrire une fonction récursive nbOccur qui compte le nombre d'occurrences d'une valeur donnée dans un tableau.
La fonction est définie par :
int nbOccur(int *tab, int n, int val)
{
if(n == 0)
return 0;
else if(tab[n - 1] == val)
return 1 + nbOccur(tab, n - 1, val);
else
return nbOccur(tab, n - 1, val);
}
Le programme principal demande la taille (1 à 4), les valeurs du tableau, puis la valeur à chercher, et affiche le nombre d'occurrences.
Réponse : La fonction compte correctement le nombre d'occurrences de la valeur.
Écrire une fonction récursive inverse qui inverse un tableau d'entiers entre deux indices d et f.
La fonction est définie par :
void inverse(int t[], int d, int f)
{
int temp;
if(d < f)
{
temp = t[d];
t[d] = t[f];
t[f] = temp;
inverse(t, d + 1, f - 1);
}
}
Le programme principal demande la taille du tableau, les valeurs, affiche le tableau initial, appelle la fonction inverse, puis affiche le tableau inversé.
Réponse : La fonction inverse correctement le tableau par récursion.
Ce TP récompense la maîtrise des techniques suivantes :
Les erreurs pénalisées sont :
Enfin, il est important de toujours montrer clairement le raisonnement, notamment en expliquant le rôle de chaque condition et la progression de la récursion.