La Récursivité

def puissance(x, n):
    """x^n pour n entier >= 0. Theta(log n) multiplications."""
    if n == 0:
        return 1
    if n % 2 == 0:
        y = puissance(x, n // 2)
        return y * y
    return x * puissance(x, n - 1)

Terminaison. Variant : \(n\), entier naturel. Dans le cas pair, l'appel porte sur \(n/2 < n\) (car \(n \ge 2\) puisque \(n \ne 0\) et \(n\) pair). Dans le cas impair, il porte sur \(n-1 < n\). Le variant decroit strictement et le cas de base \(n=0\) est atteint : la fonction termine.

Correction. Par recurrence forte sur \(n\).

• Base : \(n=0\), la fonction renvoie 1 \(= x^0\). Correct.
• Heredite : soit \(n \ge 1\), supposons le resultat vrai pour tout \(k < n\).
  • Si \(n\) est pair, \(n = 2p\) avec \(p = n/2 < n\). Par hypothese, puissance(x, p) vaut \(x^p\), donc la fonction renvoie \((x^p)^2 = x^{2p} = x^n\).
  • Si \(n\) est impair, \(n-1 < n\), donc puissance(x, n-1) vaut \(x^{n-1}\) et la fonction renvoie \(x \cdot x^{n-1} = x^n\).

Complexite. Notons \(M(n)\) le nombre de multiplications. Un cas impair est toujours suivi d'un cas pair, donc deux appels consecutifs au plus divisent \(n\) par 2 : \(M(n) \le 2\log_2 n + 1 = \Theta(\log n)\). Pour \(n = 10^6\) : une quarantaine de multiplications au lieu d'un million.

Deplacer \(n\) disques de la tige \(A\) vers \(C\) en utilisant \(B\), sans jamais poser un disque sur un plus petit.

def hanoi(n, depart="A", arrivee="C", intermediaire="B", mouvements=None):
    """Deplace n disques. Renvoie la liste des mouvements."""
    if mouvements is None:
        mouvements = []
    if n == 0:
        return mouvements
    hanoi(n-1, depart, intermediaire, arrivee, mouvements)   # 1. les n-1 du dessus
    mouvements.append((depart, arrivee))                     # 2. le plus grand
    hanoi(n-1, intermediaire, arrivee, depart, mouvements)   # 3. on les remet dessus
    return mouvements

m = hanoi(3)
print(len(m), m)      # 7 mouvements
assert len(hanoi(10)) == 2**10 - 1

Complexite. \(T(n) = 2T(n-1) + 1\) avec \(T(0)=0\). En posant \(u_n = T(n)+1\), il vient \(u_n = 2u_{n-1}\), donc \(u_n = 2^n\) et \[ T(n) = 2^n - 1. \] C'est optimal : on montre par recurrence que tout deplacement du plus grand disque exige d'avoir prealablement deplace les \(n-1\) autres. Pour \(n = 64\) (la legende), a raison d'un disque par seconde, il faudrait environ 585 milliards d'annees.

Un arbre binaire est None (vide) ou un triplet (valeur, gauche, droite) : la definition est elle-meme recursive, les algorithmes le sont donc naturellement.

def taille(a):
    """Nombre de noeuds."""
    return 0 if a is None else 1 + taille(a[1]) + taille(a[2])

def hauteur(a):
    """Hauteur : -1 pour l'arbre vide, 0 pour une feuille."""
    return -1 if a is None else 1 + max(hauteur(a[1]), hauteur(a[2]))

def infixe(a):
    """Parcours gauche - racine - droite."""
    return [] if a is None else infixe(a[1]) + [a[0]] + infixe(a[2])

def prefixe(a):
    return [] if a is None else [a[0]] + prefixe(a[1]) + prefixe(a[2])

def miroir(a):
    """Arbre symetrique."""
    return None if a is None else (a[0], miroir(a[2]), miroir(a[1]))

A = (1, (2, (4, None, None), (5, None, None)), (3, None, None))
assert taille(A) == 5 and hauteur(A) == 2
assert infixe(A) == [4, 2, 5, 1, 3]
assert prefixe(A) == [1, 2, 4, 5, 3]
assert infixe(miroir(A)) == [3, 1, 5, 2, 4]

Chaque fonction suit le meme moule : cas de base pour l'arbre vide, puis combinaison des resultats des deux sous-arbres. La complexite est \(\Theta(n)\) pour taille et hauteur, mais \(\Theta(n^2)\) au pire pour infixe a cause des concatenations de listes (a corriger en accumulant dans une liste passee en parametre).

Placer \(n\) reines sur un echiquier \(n\times n\) sans qu'aucune n'en menace une autre.

def n_reines(n):
    """Nombre de solutions au probleme des n reines."""
    def compatible(colonnes, c):
        """La reine en (ligne len(colonnes), colonne c) est-elle sure ?"""
        ligne = len(colonnes)
        for l, col in enumerate(colonnes):
            if col == c or abs(col - c) == abs(l - ligne):    # colonne ou diagonale
                return False
        return True

    def place(colonnes):
        if len(colonnes) == n:
            return 1                          # une solution complete
        total = 0
        for c in range(n):
            if compatible(colonnes, c):
                total += place(colonnes + [c])   # on essaie, on explore
        return total                             # ... puis on revient (backtrack)

    return place([])

assert [n_reines(k) for k in range(1, 9)] == [1, 0, 0, 2, 10, 4, 40, 92]

Le retour sur trace (backtracking) explore un arbre de choix, en elaguant des qu'une contrainte est violee. Sans elagage, il faudrait examiner \(n^n\) placements ; l'elagage reduit considerablement l'exploration, meme si le probleme reste exponentiel.