TP2 : La récursivité

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.

Exercice n1

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 :

• Si la puissance p est 0, la fonction retourne 1 (car n^0 = 1).
• Sinon, elle multiplie n par le résultat de la fonction appelée avec p-1.

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.

Exercice n2

É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 :

• Si n = 1, la somme est 1.
• Sinon, on ajoute n à la somme des entiers de 1 à n-1.

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.

Exercice n3

É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 :

• Si n = 0 ou n = 1, la fonction retourne n (les deux premiers termes de Fibonacci).
• Sinon, elle retourne la somme des deux termes précédents.

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

Exercice n4

É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 :

• Première méthode (soustraction répétée) :

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);
}

• Deuxième méthode (algorithme d'Euclide avec modulo) :

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.

Exercice n5

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

Exercice n6

É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 :

• On compare les caractères aux positions i et n.
• Si i ≥ n, on a vérifié tous les couples, la chaîne est palindrome.
• Si les caractères sont égaux, on continue avec i+1 et n-1.
• Sinon, la chaîne n'est pas palindrome.

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.

Exercice n7

Écrire deux fonctions récursives pour afficher un tableau d'entiers :

• de début à fin,
• de fin à début.

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.

Exercice n8

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

Exercice n9

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

Exercice n10

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

Exercice n11

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

Méthode

Ce TP récompense la maîtrise des techniques suivantes :

• Compréhension claire de la récursivité : cas de base et appel récursif.
• Respect des conditions d'arrêt pour éviter les boucles infinies.
• Utilisation correcte des indices et paramètres dans les appels récursifs.
• Manipulation de tableaux et chaînes en récursif, notamment pour les parcours avant/arrière.
• Capacité à traduire des définitions mathématiques ou logiques en fonctions récursives.

Les erreurs pénalisées sont :

• Omission ou mauvaise définition du cas de base.
• Appels récursifs incorrects (mauvais paramètres ou ordre).
• Confusion entre indices ou dépassement de bornes.
• Manque de validation des entrées utilisateur.
• Non-respect des consignes sur les types et signatures des fonctions.

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.