CHAPITRE 7 : QUAND LA FONCTION S'APPELLE ELLE-MÊME

Une fonction récursive ne laisse voir aucune boucle. Il faut une autre technique : écrire ce que la fonction coûte en fonction de ce qu'elle coûte sur un problème plus petit.

Écrire la récurrence

def factorielle(n):
    if n <= 1:                      # cas de base
        return 1
    return n * factorielle(n - 1)   # 1 multiplication + un appel sur n-1

Appelons T(n) le coût pour un argument n. La fonction fait une multiplication, un coût constant, plus un appel sur n−1 :

T(n) = T(n−1) + 1     avec T(1) = 1

Déroulons :

T(n)   = T(n-1) + 1
       = T(n-2) + 1 + 1
       = T(n-3) + 1 + 1 + 1
       ...
       = T(1) + (n-1) fois 1
       = n

Donc O(n). Le résultat est intuitif : on descend de n à 1, une marche à la fois.

Quand on divise au lieu de décrémenter

def dicho(tab, x, debut, fin):
    if debut > fin:
        return -1
    m = (debut + fin) // 2
    if tab[m] == x:
        return m
    if tab[m] < x:
        return dicho(tab, x, m + 1, fin)   # moitié droite
    return dicho(tab, x, debut, m - 1)     # moitié gauche

Un seul appel récursif, sur la moitié du tableau, plus un coût constant :

T(n) = T(n/2) + 1

T(n) = T(n/2) + 1
     = T(n/4) + 2
     = T(n/8) + 3
     ...
     = T(1) + log₂(n)

Donc O(log n). On ne peut diviser n par deux que log₂ n fois avant d'arriver à 1.

Soustraire dans l'appel récursif donne du linéaire ou pire. Diviser donne du logarithmique. C'est la même règle qu'au chapitre 6, vue de l'autre côté.

L'arbre d'appels : voir le travail

Prenons le tri fusion. Il coupe en deux, trie chaque moitié, puis fusionne, et la fusion coûte n.

T(n) = 2 · T(n/2) + n

Dessinons les appels. À chaque niveau, les problèmes sont deux fois plus petits, mais deux fois plus nombreux.

niveau 0 :        n                       -> travail : n
niveau 1 :     n/2   n/2                  -> travail : n/2 + n/2 = n
niveau 2 :   n/4 n/4 n/4 n/4              -> travail : 4 x n/4   = n
   ...
niveau log n :  1 1 1 1 ... 1 (n fois)    -> travail : n

Chaque niveau coûte n. Il y a log₂ n niveaux. Total : O(n log n).

Cet arbre explique d'un coup pourquoi les bons tris sont en n log n : le découpage donne la hauteur log n, le recollage donne la largeur n.

L'exponentielle qui se cache

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

T(n) = T(n−1) + T(n−2) + 1

Deux appels, et presque aucune réduction de taille. L'arbre double quasiment à chaque niveau : la complexité est exponentielle, environ O(1,618ⁿ).

Concrètement : fib(40) demande plus de 300 millions d'appels, et fib(50) fait attendre plusieurs minutes. Le code tient en trois lignes et il est catastrophique.

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a
# O(n), et fib(1000) est instantané

Le théorème maître

Pour les récurrences de la forme T(n) = a · T(n/b) + f(n), a appels sur des problèmes b fois plus petits, plus un travail f(n), on peut conclure sans dérouler.

On compare f(n) à n^{log_b a}, qui mesure le travail des feuilles de l'arbre.

Tri fusion : a = 2, b = 2, f(n) = n. On calcule log₂ 2 = 1, donc n¹ = n. Or f(n) = n : c'est le cas 2. Résultat : Θ(n log n). Retrouvé en deux lignes.

Recherche dichotomique : a = 1, b = 2, f(n) = 1. On a log₂ 1 = 0, donc n⁰ = 1, du même ordre que f(n). Cas 2 encore : Θ(log n).

Un parcours d'arbre binaire : a = 2, b = 2, f(n) = 1. Ici n^{log₂ 2} = n, bien plus grand que 1. Cas 1 : Θ(n).

log_b(a) = log2(4) = 2
n^log_b(a) = n²

T(n) = 2 T(n-1) + 1
     = 4 T(n-2) + 2 + 1
     = 8 T(n-3) + 4 + 2 + 1
     ...
     = 2^n - 1