Techniques de Récursion

Cours/Algorithmie/Techniques de Récursion

Nous y verrons divers moyens de manipuler la récursion de nos algorithmes.

Encapsulation de la récursion

Commençons par deux exercices préparatoires :

Donnez et prouvez un algorithme itératif de signature :

palindrome(T: [entier]) → booléen

Qui rend Vrai si le tableau est un palindrome.

corrigé

algorithme palindrome(T: [entier]) → booléen
    pour chaque i de [0, T.longueur // 2[:
        si T[i] ≠ T[T.longueur - 1 - i]:
            rendre Faux
    rendre Vrai

Et maintenant la version récursive :

Donnez et prouvez un algorithme récursif de signature :

palindrome_rec(T: [entier], i: entier) → booléen

corrigé

algorithme palindrome_rec(T: [entier], i: entier) → booléen
    si T.longueur - 1 - i ≤ i:
        rendre Vrai
    si  T[i] ≠ T[T.longueur - 1 - i]:
        rendre Faux
    
    rendre palindrome_rec(T, i + 1)

Il faut monter que l'algorithme rend Vrai si $T[j] = T[T.\mbox{longueur} - 1 - j]$ pour tous $i \leq j < T.\mbox{longueur} - 1 - i$

La premiere condition est la condition d'arrêt de la récursion puisque dans ce cas là $i$ a dépassé la moitié du tableau.

Puis on utilise l'équation de récurrence :

palindrome(T) = (T[0] == T[-1]) et palindrome(T[1:-1])

Lorsque l'on crée des algorithmes récursif, on a souvent besoin d'initialiser les paramètres. Par exemple si on veut savoir si un tableau est un palindrome en utilisant l'algorithme récursif palindrome_rec(T: [entier], i: entier) → booléen, il faut écrire palindrome_rec(T, T.longueur). Le paramètre $i$ est un paramètre important pour la récursion mais inutile pour l'appel global.

Pour éviter d'avoir des paramètres inutile on encapsulera la fonction récursive dans un algorithme dont le seul but est d'initialiser la récursion.

À retenir

Cette technique est à utiliser dès que l'on a besoin de paramètres récursifs mais non utile pour l'algorithme général.

Pour savoir si un tableau est un palindrome, l'algorithme sera :

fonction palindrome_rec(T: [entier], i: entier) → booléen
    ...  # code de la fonction récursive

algorithme palindrome(T: [entier]) → booléen
    rendre palindrome_rec(T, T.longueur)

Entraînons nous :

Encapsulez la fonction récursive maximum_rec(t: [réel], i: entier) → entier du premier exercice dans une fonction permettant de rendre le maximum d'un tableau passé en paramètre.

corrigé

algorithme maximum(T: [entier]) → entier
    rendre maximum_rec(t, T.longueur - 1)

Récursion terminale

Soit l'algorithme f suivant où c: A → Booléen, g: A → B et h: A → A sont trois fonctions parfaitement définies :


algorithme f(n: A) → B:
    si c(n) == Vrai:
        rendre g(n)
    sinon:
        rendre f(h(n))

L'algorithme f est sous la forme d'une récursion terminale, c'est à dire que :

soit il s'arrête si une condition d'arrêt est vérifiée
soit il rend une récursion de lui même

Pour que la définition de f ait du sens il faut bien sur que chaque récursion se rapproche de la condition d'arrêt. C'est ce qu'il faut démontrer pour chaque algorithme sous la forme d'une récursion terminale.

La récursion terminale est sympathique car équivalente à la forme itérative suivante :

algorithme f(n: A) → B:
    tant que c(n) est Faux:
        n ← h(n)
    rendre g(n)

Ce qui permet une implémentation en machine efficace (c'est ce que font les compilateur lorsque'ils repèrent une telle forme).

Le type A peut être de toute forme, c'est souvent un type composé comme on le verra.

Entraînons nous.

L'algorithme palindrome_rec(T: [entier], i: entier) → booléen est sous forme terminale, transformez le en programme itératif.

corrigé

algorithme palindrome_pas_rec(T: [entier], i: entier) → booléen
    tant que (T.longueur - 1 - i > i): 
        si  T[i] ≠ T[T.longueur - 1 - i]:
            rendre Faux
        i ← i + 1
    rendre Vrai

L'algorithme retournement_indice(T: [entier], i: entier) → ∅ est sous forme terminale, transformez le en programme itératif.

En déduire un algorithme itératif permettant de retourner un tableau.

corrigé

algorithme retournement_indice(t: [entier], i: entier) → ∅
    temp := entier
    tant que (t.longueur - 1 - i > i):
        temp ← t[i]
        t[i] ← t[t.longueur - 1 - i]
        t[t.longueur - 1 - i] ← temp

        i ← i + 1

Et donc, en utilisant un petit abus de pseudocode :

algorithme retournement(t: [entier], i: entier) → ∅
    tant que (t.longueur - 1 - i > i):
        t[i], t[t.longueur - 1 - i] ← t[t.longueur - 1 - i], t[i] 
        i ← i + 1

Notez que l'opération consistant à transformer un algorithme récursif sous forme terminale en algorithme itératif est exactement l'opération inverse que l'on a faite pour prouver certains algorithmes itératifs, comme la factorielle. On retrouve encore une fois que recursion et itération sont deux faces d'une même pièce.

Construire un algorithme sous forme terminale

Écrivez sous la forme d'une récursion terminale l'algorithme de signature :

algorithme puissance_2(m: entier, n: entier) → entier

Qui rend le plus grand entier de la forme $2^p \cdot m$ plus petit que $n$.

corrigé

algorithme puissance_2(m: entier, n: entier) → entier:
    si 2 * m ≥ n:
        rendre m
    sinon:
        rendre f(2 * m, n)

C'est bien une récursion terminale puisque le code est équivalent à :

fonction c(m: entier, n: entier) → booléen:
    rendre 2 * m ≥ n

fonction g(m: entier, n: entier) → entier:
    rendre m

algorithme puissance_2(m: entier, n: entier) → entier:
    si c(m, n) == Vrai:
        rendre g(m, n)
    sinon:
        rendre f(2 * m, n)

Avec le type A étant un couple d'entier et B le type entier.

Transformer en une forme terminale

La récursion terminale ne fait aucun calcul en propre, il envoie de nouveaux paramètres. Cela semble très restrictif. Par exemple notre fonction factorielle récursive n'est pas sous forme terminale puisque l'on fait un calcul en plus de la récursion :

algorithme factorielle(n: entier) → entier:
    si n == 1:  # condition d'arrêt
        rendre 1
    (f := entier) ← factorielle(n-1)
    rendre n * f

Le rendre récursif terminal est impossible en ne gardant qu'un seul paramètre. L'astuce est d'ajouter un paramètre, appelé accumulateur qui va transmettre à la fonction récursive les calculs intermédiaires, dans notre cas le début du calcul de factoriel. Dans notre cas :

fonction factorielle_term(n: entier, acc: entier) → entier:
    si n == 1:
        rendre acc
    rendre factorielle(n-1, n * acc)


algorithme factorielle(n: entier  # n > 1
                      ) → entier:
    rendre factorielle_term(n, 1)

Montrer que l'algorithme précédent :

est bien sous la forme terminale
calcule bien la factorielle

corrigé

Il est clairement sous la forme récursive terminale. Il fini car chaque récursion se rapproche strictement de la condition d'arrêt.

Enfin, acc va contenir la factorielle comme le prouve une récursion triviale sur $n$.

La récursion terminale est un moyen efficace d'implémenter des suites arithmétiques ou géométriques. Montrez le :

Donner un prouvez un algorithme écrit sous la forme d'une récursion terminale permettant de calculer tout élément $u_n$ d'une suite arithmétique définie telle que :

$$ u_n = \left\{ \begin{array}{ll} u_0 & \mbox{si } n = 0 \\ r + n_{n-1} & \mbox{sinon.} \end{array} \right. $$

corrigé

fonction u_n_term(n: entier, 
                 u0: entier, 
                 r: entier, 
                 acc: entier) → entier:
    si n == 0:
        rendre u0 + acc
    rendre u_n_term(n-1, u0, r, r + acc)


algorithme u_n(n : entier, 
               u0: entier, 
               r : entier
              ) → entier:
    rendre u_n_term(n, u0, r, 0)

Transformez l'algorithme récursif précédent en un algorithme itératif.

corrigé

Le but de la récursion terminale est de facile,ent transformer un algorithme récursif en un algorithme itératif cr la récursion est une boucle tant que.

algorithme u_n(n : entier, 
               u0: entier, 
               r : entier
              ) → entier:
    (acc := entier) ← 0
    tant que n > 0:
        acc ← r + acc
        n ← n - 1
    
    rendre u0 + acc

Transformer un algorithme récursif en un algorithme avec une récursion terminale revient à ajouter des variables à un programme récursif (ses variables sont ses paramètres).

À retenir

La technique de l'accumulateur (ie. l'ajout de variables) est fondamentale pour la création d'algorithme récursif.

Récursion croisée

Une dernière technique qui peut être utile est la récursion croisée qui définie une fonction par rapport à une autre et réciproquement :

Écrire les deux fonctions récursives suivantes sans utiliser de division entière :

algorithme pair(n: entier) → booléen
algorithme impair(n: entier) → booléen

Vous pourrez utiliser le fait que pair(0) est Vrai alors que'impair(0) est Faux.

corrigé

algorithme pair(n: entier) → booléen
    si n == 0:
        rendre Vrai
    rendre NON impair(n - 1)

algorithme impair(n: entier) → booléen
    si n == 0:
        rendre Faux
    rendre NON pair(n - 1)

La finitude est claire puisque :

il n'y a qu'un appel récursif
chaque appel se rapproche strictement de la condition d'arrêt

La correction est évidente par définition de la parité.