Algorithmes récursifs et itératifs

Il y a deux grandes familles d'algorithmes :

• les algorithmes itératifs, c'est-à-dire utilisant des boucles
• les algorithmes récursifs, c'est-à-dire écrits sous la forme d'une fonction qui s'appelle elle-même.

Tout algorithme pourra toujours s'écrire sous une forme itérative ou récursive (on va le montrer mais bien plus tard) mais certains problèmes se résolvent mieux sous une forme que sous l'autre.

Avant de définir formellement les deux approches commençons par deux remarques importantes :

Pour expliciter la différence entre les deux approches nous allons utiliser notre exemple fil rouge du calcul du $\operatorname{pgcd}$.

Algorithmes itératifs

Pour le calcul du $\operatorname{pgcd}$, l'algorithme itératif va tester tous les cas possibles :

algorithme pgcd(a: int, b: int) → int:  # a, b ≥ 0
    ref pgcd int

    pour chaque k de [1 .. min(a, b)]:
        si (a mod k == 0) ET (b mod k == 0):
            pgcd ← k
    
    rendre pgcd

def pgcd(a, b):
    pgcd = 0
    for k in range(1, min(a, b) + 1):
        if (a % k == 0) and (b % k == 0):
            pgcd = k
    
    return pgcd

Lorsque l'on construit un algorithme itératif, il faut faire attention au fait que les boucles finissent bien. C'est bien sûr toujours le cas avec les boucles de type pour chaque mais pour des boucles de type tant que ce n'est pas toujours évident.

Algorithmes récursifs

Pour le calcul du $\operatorname{pgcd}$ on va utiliser l'algorithme binaire de Stein :

algorithme pgcd(a: int, b: int) → int:  # a, b ≥ 0
    si min(a, b) == 0:
        rendre max(a, b)
    sinon si a == b:
        rendre a
    sinon si (a mod 2 == 0) ET (b mod 2 == 0):
        rendre 2 * pgcd(a // 2, b // 2)
    sinon si (a mod 2 == 0):
        rendre pgcd(a // 2, b)
    sinon si (b mod 2 == 0):
        rendre pgcd(a, b  // 2)
    sinon si a > b:
        rendre pgcd(a - b, b)
    sinon:
        rendre pgcd(a, b - a)

def pgcd(a, b):
    if min(a, b) == 0:                     
        return max(a, b)
    elif a == b:
        return a    
    elif (a % 2 == 0) and (b % 2 == 0):
        return 2 * pgcd(a // 2, b // 2)
    elif (a % 2 == 0):
        return pgcd(a // 2, b)
    elif (b % 2 == 0):
        return pgcd(a, b  // 2)
    elif a > b:
        return pgcd(a - b, b)
    else:
        return pgcd(a, b - a)

À chaque récursion soit $a$ soit $b$ (ou les deux) diminue strictement : à chaque itération on se rapproche donc des deux cas sans récursion qui mettent fin à l'algorithme.

Notre algorithme effectue 5 récursions avant de terminer pour calculer le pgcd entre 8 et 6 :

pgcd(8, 6) = 2 * pgcd(4, 3)
                 pgcd(4, 3) = pgcd(2, 3)
                              pgcd(2, 3) = pgcd(1, 3)
                                           pgcd(1, 3) = pgcd(1, 2)
                                                        pgcd(1, 2) = pgcd(1, 1)
                                                                     pgcd(1, 1) = 1

Pour comprendre comment cela fonctionne il faut se rappeler qu'un algorithme passe à la ligne suivante que si l'instruction est terminée : lors d'une récursion l'algorithme attend que la récursion se termine pour continuer. Ainsi lors du 5e appel de récursion, il y a 5 algorithmes qui attendent :

• pgcd(1, 2) attend en ligne 11 que la fonction pgcd(1, 1) se termine pour continuer
• pgcd(1, 3) attend en ligne 15 que la fonction pgcd(1, 2) se termine pour continuer
• pgcd(2, 3) attend en ligne 9 que la fonction pgcd(1, 3) se termine pour continuer
• pgcd(4, 3) attend en ligne 9 que la fonction pgcd(2, 3) se termine pour continuer
• pgcd(8, 6) attend en ligne 7 que la fonction pgcd(4, 3) se termine pour continuer

Lorsque la dernière récursion s'arrête : pgcd(1, 1) rend 1 sans récursion, qui permet à l'algorithme pgcd(1, 2) de s'arrêter qui permet à l'algorithme pgcd(1, 3) de s'arrêter qui permet à l'algorithme pgcd(2, 3) de s'arrêter qui permet à l'algorithme pgcd(4, 3) de s'arrêter qui permet à l'algorithme pgcd(8, 6) de s'arrêter.

Notez que nous n'avons pas prouvé que le programme trouve bien le plus grand diviseur commun de deux entiers, juste qu'il se termine quelles que soient ses entrées et donc que c'est un algorithme. Démontrons-le :

Récursion terminale

La récursion terminale est un algorithme écrit sous une forme récursive pouvant facilement se mettre sous forme itérative :

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

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 compilateurs lorsqu'ils repèrent une telle forme).

Illustrons ceci en utilisant directement l'algorithme d'Euclide pour le calcul du $\operatorname{pgcd}$. On peut en effet écrire cet algorithme sous la forme d'une équation récurrente :

On a montré en exercice que cette équation est correcte et qu'elle se termine en un nombre fini d'étapes, c'est donc bien un algorithme qui s'écrit :

algorithme pgcd(a: int, b: int) → int:  # a, b ≥ 0
    si min(a, b) == 0:
        rendre max(a, b)
    sinon:
        rendre pgcd(max(a, b) - min(a, b), min(a, b))

def pgcd(a, b):
    if min(a, b) == 0:
        return max(a, b)
    else:
        return pgcd(max(a, b) - min(a, b), min(a, b))

Il est écrit sous forme terminale et est donc équivalent à l'algorithme itératif suivant :

algorithme pgcd(a: int, b: int) → int:  # a, b ≥ 0
    tant que min(a, b) > 0:
        a, b ← max(a, b) - min(a, b), min(a, b)
    rendre max(a, b)

Récursion croisée

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

algorithme pair(n: int) → bool
algorithme impair(n: int) → bool

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

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