TD1 - Récursion – Structures de Données Avancées

1 Exercice 1 : addition et multiplication récursives

On considère deux entiers positifs \(a\) et \(b\). En vous appuyant sur les descriptions récursives suivantes, écrivez en langage C les fonctions récursives add_rec(a,b) et mult_rec(a,b) qui implémentent ces définitions.

\[ a + b = \begin{cases} b & \text{si } a = 0 \\ (a - 1) + (b + 1) & \text{sinon} \end{cases} \]

\[ a \times b = \begin{cases} 0 & \text{si } a = 0 \\ \frac{a}{2} \times (b + b) & \text{si } a \text{ est pair} \\ \left(\frac{a - 1}{2} \times (b + b)\right) + b & \text{si } a \text{ est impair} \end{cases} \]

Note

Pour la fonction add_rec, les opérations \(-1\) et \(+1\) ici sont considérées uniquement en tant que décrémentation et incrémentation. Ici donc, \(b + 1\) n’est pas une addition.

2 Exercice 2 : Puissance

L’élévation à la puissance d’un entier positif \(a\) par un entier positif \(n\) se traduit par la multiplication de \(a\) par lui-même \(n\) fois. Et par convention, on définit \(a^0 = 1\) pour tout entier \(a\) non nul.

Proposez une fonction itérative power_iter(a,n) qui calcule \(a^n\).
Ce problème peut également être résolu de manière récursive. On se propose d’écrire une fonction récursive power_rec(a,n) qui calcule \(a^n\).
1. Pour quelle valeur de \(n\) a-t-on une résolution directe ?
2. Trouvez une relation de récurrence pour \(a^n\) en fonction de \(a^{n-1}\). Déduisez-en la description récursive de power_rec(a,n).
3. Écrivez en langage C une fonction power_rec(a,n) qui calcule \(a^n\).

3 Exercice 3 : Palindrome

Un palindrome est un mot qui se lit de la même manière de gauche à droite et de droite à gauche. Par exemple, les mots radar, elle, rotor sont des palindromes. On se propose d’écrire une fonction récursive is_palindrome(s) qui vérifie si une chaîne de caractères s est un palindrome ou non. Cette fonction doit donc retourner true si s est un palindrome et false sinon.

On suppose qu’une chaîne s de longueur \(n\) peut être représentée par \(s[1, \dots, n]\).

Identifiez les cas de base de votre fonction récursive.
Trouvez une relation de récurrence pour is_palindrome(s) en fonction de is_palindrome(s'), où s' est une sous-chaîne de s.
Proposez deux implémentations de votre fonction récursive en langage C en utilisant les prototypes suivants:
```
int is_palindrome(char * s, int n);
int is_palindrome(char * s, int l, int r);
```

4 Exercice 4 : Recherche binaire

La recherche binaire est un algorithme efficace pour rechercher un élément dans un tableau trié. L’idée est de comparer l’élément recherché avec l’élément au milieu du tableau. Si l’élément recherché est plus petit, on continue la recherche dans la moitié gauche du tableau, sinon dans la moitié droite. On répète ce processus jusqu’à trouver l’élément ou jusqu’à ce que la portion du tableau à explorer soit vide.

Voici l’implémentation itérative de la recherche binaire en C :

// Recherche l'élément target dans le tableau arr de taille n
// Retourne l'indice de l'élément si trouvé, -1 sinon
int binary_search_iter(int *arr, int n, int target) {
    int left = 0;
    int right = n - 1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        
        if (arr[mid] == target) {
            return mid;  // Élément trouvé
        } else if (arr[mid] < target) {
            left = mid + 1;  // Chercher dans la moitié droite
        } else {
            right = mid - 1;  // Chercher dans la moitié gauche
        }
    }
    
    return -1;  // Élément non trouvé
}

On souhaite maintenant écrire une version récursive de cet algorithme.

Identifier le cas de base : Dans quelles situations peut-on déterminer directement si l’élément est présent ou absent sans faire d’appel récursif ?
Réduction du problème : Comment peut-on réduire le problème de recherche dans un tableau de taille \(n\) à un problème de recherche dans un tableau plus petit ?
Définition récursive : Complétez la définition récursive suivante pour la recherche binaire. Soit binary_search_rec(arr, left, right, target) qui recherche target dans la portion du tableau arr entre les indices left et right :

\[ \text{binary\_search\_rec}(arr, left, right, target) = \begin{cases} ? & \text{si } left > right \\ ? & \text{si } arr[mid] = target \\ ? & \text{si } arr[mid] < target \\ ? & \text{sinon} \end{cases} \]

où \(mid = \lfloor \frac{left + right}{2} \rfloor\).
Implémentation : Écrivez la fonction récursive binary_search_rec(arr, left, right, target) en C qui implémente la recherche binaire de manière récursive.
Fonction auxiliaire : Écrivez une fonction binary_search(arr, n, target) qui utilise binary_search_rec avec les bons paramètres initiaux.

Tip

Comparaison avec l’approche itérative :

La version itérative utilise une boucle while et modifie les variables left et right à chaque itération.
La version récursive remplace la boucle par des appels récursifs avec des valeurs différentes de left et right.
Les deux versions ont la même logique, seule la structure de contrôle change !

5 Exercice 5 : Tours de Hanoï

On considère trois tours, A, B et C, et \(n\) disques de tailles différentes. Les disques sont empilés en ordre décroissant de taille sur la tour A. Le but est de déplacer tous les disques de la tour A à la tour B en utilisant la tour C comme tour intermédiaire. On peut déplacer un seul disque à la fois et on ne peut jamais placer un disque de taille plus grande sur un disque de taille plus petite.

L’algorithme récursif suivant résout le problème des tours de Hanoï avec un nombre minimal de déplacements:

hanoi(n, A, B, C):
    si n > 0 alors:
        hanoi(n - 1, A, C, B)
        déplacer le disque restant de la tour A à la tour B
        hanoi(n - 1, C, B, A)

Combien de déplacements sont nécessaires pour résoudre le problème pour 0 disque ? Même question pour 1 disque.
Trouvez une relation de récurrence pour le nombre de déplacements nécessaires pour résoudre le problème des tours de Hanoï avec \(n\) disques.

6 Exercice 6 : Récursion terminale

On rappelle la définition récursive de la fonction factorielle d’un entier positif, factorial(n) telle que présentée dans le cours:

factorial(n):
    si n ≤ 1 alors
        retourner 1
    sinon
        retourner n × factorial(n - 1)

On dit qu’une fonction récursive est terminale, si dans le corps de sa définition, l’appel récursif est la dernière instruction exécutée. De telles fonctions récursives sont intéressantes car elles permettent une gestion optimisée de la pile d’appel.

Considérez la fonction \(g\), définie sur les couples d’entiers de la manière suivante:

\[ g(n, a) = \begin{cases} a & \text{si } n \leq 1 \\ g(n - 1, n \times a) & \text{sinon} \end{cases} \]

On notera que la récurrence porte sur l’argument \(n\).

Que vaut \(g(n, 1)\) pour tout entier \(n > 0\) ?
Écrivez en langage C une fonction récursive terminale factorial_term qui calcule la factorielle de \(n\).