La Récursivité

Le cas (e) illustre l'importance du cas de base : if n == 0 ne suffit pas, il faudrait if n <= 0. Une base « atteignable par une seule valeur » est toujours suspecte.

def somme(t, i=0):
    """Somme de t[i:]. Cas de base : suffixe vide. Variant : len(t) - i."""
    if i >= len(t):
        return 0
    return t[i] + somme(t, i + 1)

def maximum(t, i=0):
    """Maximum de t[i:]. Precondition : t non vide."""
    if i == len(t) - 1:
        return t[i]
    return max(t[i], maximum(t, i + 1))

def renverse(s):
    """Chaine renversee. Variant : len(s)."""
    if len(s) <= 1:
        return s
    return renverse(s[1:]) + s[0]

def est_palindrome(s):
    """Variant : len(s). Deux caracteres consommes par appel."""
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return est_palindrome(s[1:-1])

def pgcd(a, b):
    """Euclide recursif. Variant : b. Recursivite TERMINALE."""
    return a if b == 0 else pgcd(b, a % b)

assert somme([1, 2, 3]) == 6 and somme([]) == 0
assert maximum([3, 9, 2]) == 9
assert renverse("MPSI") == "ISPM"
assert est_palindrome("kayak") and not est_palindrome("python")
assert pgcd(1071, 462) == 21

import time
from functools import lru_cache

appels = 0
def fib_naif(n):
    global appels
    appels += 1
    return n if n < 2 else fib_naif(n-1) + fib_naif(n-2)

for n in (10, 20, 30):
    appels = 0; v = fib_naif(n)
    print(f"fib({n}) = {v:>7}, {appels:>10} appels")

fib(10) =      55,        177 appels
fib(20) =    6765,      21891 appels
fib(30) =  832040,    2692537 appels

2. Demonstration. Notons \(A(n)\) le nombre d'appels. On a \(A(0)=A(1)=1\) et, pour \(n \ge 2\), \(A(n) = 1 + A(n-1) + A(n-2)\) (l'appel courant, plus les deux sous-arbres). Posons \(B(n) = A(n) + 1\). Alors \[ B(n) = A(n)+1 = A(n-1)+A(n-2)+2 = B(n-1) + B(n-2), \] avec \(B(0) = B(1) = 2\). La suite \(B\) verifie donc la meme recurrence que Fibonacci, avec \(B(n) = 2F_{n+1}\) (verification : \(B(0)=2=2F_1\), \(B(1)=2=2F_2\)). D'ou \(A(n) = 2F_{n+1} - 1\). Verification : \(A(10) = 2F_{11}-1 = 2\cdot89-1 = 177\). Comme \(F_n \sim \varphi^n/\sqrt5\), la croissance est exponentielle de raison \(\varphi \approx 1{,}618\).

@lru_cache(maxsize=None)
def fib_memo(n):
    return n if n < 2 else fib_memo(n-1) + fib_memo(n-2)

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

n = 35
t0 = time.perf_counter(); fib_naif(n); t1 = time.perf_counter()
t2 = time.perf_counter(); fib_memo(n); t3 = time.perf_counter()
t4 = time.perf_counter(); fib_iter(n); t5 = time.perf_counter()
print(f"naif    : {t1-t0:.4f} s")     # ~ 3 s
print(f"memoise : {t3-t2:.6f} s")     # ~ 0.00002 s
print(f"iteratif: {t5-t4:.6f} s")     # ~ 0.000003 s

def produit2(A, B):
    return [[A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
            [A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]]]

def fib_matrice(n):
    """Theta(log n) multiplications de matrices 2x2."""
    if n == 0:
        return 0
    R, P = [[1, 0], [0, 1]], [[1, 1], [1, 0]]
    k = n
    while k > 0:
        if k & 1:
            R = produit2(R, P)
        P = produit2(P, P)
        k >>= 1
    return R[0][1]

for n in range(50):
    assert fib_matrice(n) == fib_iter(n)
print(fib_matrice(1000) == fib_iter(1000))     # True, calcule en ~30 produits

La relation utilisee est \(\begin{pmatrix}1&1\\1&0\end{pmatrix}^n = \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}\), demontree par recurrence. Pour \(n = 10^6\), la version matricielle fait 40 produits, l'iterative un million d'additions — mais sur de tres grands entiers, l'iterative reste competitive car les additions sont moins couteuses que les multiplications.

def hanoi(n, depart="A", arrivee="C", inter="B", mvts=None):
    """Liste des deplacements pour transferer n disques de depart vers arrivee."""
    if mvts is None:
        mvts = []
    if n == 0:
        return mvts
    hanoi(n-1, depart, inter, arrivee, mvts)
    mvts.append((depart, arrivee))
    hanoi(n-1, inter, arrivee, depart, mvts)
    return mvts

for n in range(1, 15):
    assert len(hanoi(n)) == 2**n - 1
print(hanoi(3))
# [('A','C'), ('A','B'), ('C','B'), ('A','C'), ('B','A'), ('B','C'), ('A','C')]

2. \(T(n) = 2T(n-1) + 1\) avec \(T(0) = 0\). Posons \(u_n = T(n)+1\) : alors \(u_n = 2T(n-1)+2 = 2u_{n-1}\), suite geometrique de raison 2 et de premier terme \(u_0 = 1\). Donc \(u_n = 2^n\) et \(T(n) = 2^n - 1\).

3. Optimalite. Par recurrence forte sur \(n\). Pour \(n=0\), 0 deplacement suffit et est necessaire. Soit \(n \ge 1\). Dans toute solution, considerons le dernier deplacement du plus grand disque : a cet instant, il doit aller de la tige de depart a la tige d'arrivee, donc la troisieme tige porte les \(n-1\) autres disques empiles. Il a donc fallu, auparavant, transferer ces \(n-1\) disques de la tige de depart vers la tige intermediaire : par hypothese de recurrence, cela exige au moins \(2^{n-1}-1\) deplacements. Apres ce deplacement du grand disque, il faut les ramener sur la tige d'arrivee : encore au moins \(2^{n-1}-1\). Total : \[ (2^{n-1}-1) + 1 + (2^{n-1}-1) = 2^n - 1. \] L'algorithme atteignant cette borne, il est optimal.

def verifie(n):
    """Simule les deplacements et verifie qu'aucune regle n'est violee."""
    tiges = {"A": list(range(n, 0, -1)), "B": [], "C": []}
    for depart, arrivee in hanoi(n):
        assert tiges[depart], f"tige {depart} vide"
        d = tiges[depart].pop()
        assert not tiges[arrivee] or tiges[arrivee][-1] > d, \
               f"disque {d} pose sur un plus petit"
        tiges[arrivee].append(d)
    assert tiges["C"] == list(range(n, 0, -1))
    assert not tiges["A"] and not tiges["B"]
    return True

for n in range(1, 13):
    assert verifie(n)
print("solutions de Hanoi validees jusqu'a n = 12")

from math import inf

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

def hauteur(a):
    """-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 somme(a):
    return 0 if a is None else a[0] + somme(a[1]) + somme(a[2])

def nb_feuilles(a):
    if a is None:
        return 0
    if a[1] is None and a[2] is None:
        return 1
    return nb_feuilles(a[1]) + nb_feuilles(a[2])

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

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

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

def est_abr(a, mini=-inf, maxi=inf):
    """Un ABR : tout noeud est > tous ceux de gauche et < tous ceux de droite.

    L'encadrement (mini, maxi) est INDISPENSABLE : comparer seulement aux fils
    directs est insuffisant.
    """
    if a is None:
        return True
    v, g, d = a
    if not (mini < v < maxi):
        return False
    return est_abr(g, mini, v) and est_abr(d, v, maxi)

def insere_abr(a, v):
    """Insere v dans l'ABR a. Renvoie le nouvel arbre."""
    if a is None:
        return (v, None, None)
    x, g, d = a
    if v < x:
        return (x, insere_abr(g, v), d)
    if v > x:
        return (x, g, insere_abr(d, v))
    return a                       # deja present

def construit_abr(t):
    a = None
    for v in t:
        a = insere_abr(a, v)
    return a

A = (5, (3, (1, None, None), (4, None, None)), (8, (7, None, None), None))
assert taille(A) == 6 and hauteur(A) == 2 and nb_feuilles(A) == 3
assert infixe(A) == [1, 3, 4, 5, 7, 8]
assert est_abr(A)

# contre-exemple : les fils directs sont corrects mais l'arbre n'est PAS un ABR
faux = (5, (3, None, (6, None, None)), (8, None, None))
assert not est_abr(faux)          # 6 est a gauche de 5 !

B = construit_abr([5, 3, 8, 1, 4, 7])
assert infixe(B) == sorted([5, 3, 8, 1, 4, 7])
print("arbres binaires valides")

Complexites : \(\Theta(n)\) pour toutes ces fonctions (chaque noeud est visite une fois), sauf les parcours qui, ecrits avec des concatenations, peuvent atteindre \(\Theta(n^2)\) sur un arbre degenere. L'insertion coute \(\Theta(h)\) ou \(h\) est la hauteur : \(\Theta(\log n)\) si l'arbre est equilibre, \(\Theta(n)\) s'il est degenere (liste triee inseree dans l'ordre).

def permutations(t):
    """Toutes les permutations de t. n! resultats."""
    if len(t) <= 1:
        return [list(t)]
    res = []
    for i in range(len(t)):
        reste = t[:i] + t[i+1:]
        for p in permutations(reste):
            res.append([t[i]] + p)
    return res

def parties(t):
    """Toutes les parties de t. 2^n resultats."""
    if not t:
        return [[]]
    sans = parties(t[1:])
    return sans + [[t[0]] + p for p in sans]

def somme_cible(t, c, i=0):
    """Existe-t-il une sous-liste de t[i:] de somme c ? Backtracking avec elagage."""
    if c == 0:
        return True
    if i >= len(t):
        return False
    # on prend t[i], ou on ne le prend pas
    return somme_cible(t, c - t[i], i + 1) or somme_cible(t, c, i + 1)

def somme_cible_liste(t, c, i=0, courant=None):
    """Renvoie une sous-liste de somme c, ou None."""
    if courant is None:
        courant = []
    if c == 0:
        return list(courant)
    if i >= len(t) or c < 0 and all(x > 0 for x in t):
        return None
    courant.append(t[i])
    r = somme_cible_liste(t, c - t[i], i + 1, courant)
    if r is not None:
        return r
    courant.pop()                       # BACKTRACK : on defait le choix
    return somme_cible_liste(t, c, i + 1, courant)

assert len(permutations([1, 2, 3])) == 6
assert sorted(permutations([1,2,3])) == [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
assert len(parties([1, 2, 3])) == 8
assert somme_cible([3, 34, 4, 12, 5, 2], 9)          # 4 + 5
assert not somme_cible([3, 34, 4, 12, 5, 2], 30)
print(somme_cible_liste([3, 34, 4, 12, 5, 2], 9))    # [3, 4, 2] ou [4, 5]

4. Complexites.

Pour les deux premieres, la complexite est necessairement exponentielle : il faut au minimum ecrire la sortie, qui comporte \(n!\) ou \(2^n\) elements. On dit que l'algorithme est optimal a la taille de la sortie pres.

Pour somme_cible, c'est different : la sortie est un simple booleen. Le probleme est NP-complet (probleme de la somme de sous-ensembles) : on ne connait pas d'algorithme polynomial, et il est conjecture qu'il n'en existe pas. On peut toutefois faire mieux que \(2^n\) dans certains cas :

def somme_cible_dp(t, c):
    """Programmation dynamique : Theta(n * c) si les valeurs sont des entiers positifs."""
    possible = {0}
    for x in t:
        possible |= {s + x for s in possible if s + x <= c}
        if c in possible:
            return True
    return c in possible

assert somme_cible_dp([3, 34, 4, 12, 5, 2], 9)
assert not somme_cible_dp([3, 34, 4, 12, 5, 2], 30)

Cette complexite \(\Theta(nc)\) est dite pseudo-polynomiale : elle est polynomiale en la valeur de \(c\), mais exponentielle en sa taille d'ecriture (\(\log c\) bits). Elle est utilisable quand \(c\) est petit.

def factorielle_iter(n):
    acc = 1
    while n > 1:
        acc *= n; n -= 1
    return acc

def pgcd_iter(a, b):
    while b:
        a, b = b, a % b
    return a

def infixe_iter(a):
    """Parcours infixe iteratif : pile explicite, pas de RecursionError."""
    res, pile, courant = [], [], a
    while pile or courant is not None:
        while courant is not None:
            pile.append(courant)
            courant = courant[1]        # descente a gauche
        courant = pile.pop()
        res.append(courant[0])          # traitement de la racine
        courant = courant[2]            # puis a droite
    return res

def hanoi_iter(n, depart="A", arrivee="C", inter="B"):
    """Version iterative : on simule la pile des appels en attente."""
    mvts = []
    pile = [(n, depart, arrivee, inter, False)]
    while pile:
        k, a, c, b, traite = pile.pop()
        if k == 0:
            continue
        if traite:
            mvts.append((a, c))
        else:
            # on empile dans l'ORDRE INVERSE de l'execution voulue
            pile.append((k-1, b, c, a, False))
            pile.append((k, a, c, b, True))
            pile.append((k-1, a, b, c, False))
    return mvts

A = (5, (3, (1, None, None), (4, None, None)), (8, (7, None, None), None))
assert infixe_iter(A) == [1, 3, 4, 5, 7, 8]
for n in range(1, 12):
    assert hanoi_iter(n) == hanoi(n)
print("derecursivations validees")

1. factorielle_terminale et pgcd sont recursives terminales : l'appel recursif est la derniere operation. Il suffit alors de remplacer l'appel par une mise a jour des parametres et de boucler. Aucune pile n'est necessaire, et la memoire passe de \(\Theta(n)\) a \(\Theta(1)\).

4. Trois categories :

• Recursivite terminale : derecursivation immediate en boucle while, memoire \(\Theta(1)\).
• Recursivite lineaire non terminale (factorielle, somme d'une liste) : on inverse l'ordre de traitement (accumulateur) ou l'on utilise une pile explicite.
• Recursivite multiple (Hanoi, parcours d'arbre, backtracking) : il faut necessairement une pile explicite, car il y a plusieurs appels en attente. La derecursivation ne fait alors que remplacer la pile systeme par une pile geree a la main : le gain est de contourner la limite de recursion, pas d'economiser de la memoire.

def sierpinski(k):
    """Tapis de Sierpinski d'ordre k, sous forme de liste de chaines."""
    if k == 0:
        return ["#"]
    petit = sierpinski(k - 1)
    n = len(petit)
    vide = " " * n
    res = []
    for ligne in petit:
        res.append(ligne * 3)                    # rangee du haut
    for ligne in petit:
        res.append(ligne + vide + ligne)         # rangee du milieu : trou central
    for ligne in petit:
        res.append(ligne * 3)                    # rangee du bas
    return res

for l in sierpinski(2):
    print(l)

def pleines(k):
    """Nombre de cases pleines."""
    return 8 ** k

for k in range(5):
    g = sierpinski(k)
    assert sum(l.count("#") for l in g) == pleines(k)
print("tapis de Sierpinski valide")

########
# ## ##
########
###  ###
# #  # #
###  ###
########
# ## ##
########

2. Le tapis d'ordre \(k\) est fait de 8 copies de celui d'ordre \(k-1\) (les 9 blocs sauf le central) : \(P(k) = 8P(k-1)\) avec \(P(0)=1\), donc \(P(k) = 8^k\). La grille compte \(9^k\) cases : la proportion pleine est \((8/9)^k \to 0\), le tapis est d'aire nulle a la limite.

La dimension fractale (dimension de similitude) est definie par : si l'objet est constitue de \(N\) copies de lui-meme reduites d'un facteur \(r\), alors \(d = \frac{\ln N}{\ln r}\). Ici \(N = 8\) et \(r = 3\), d'ou \[ d = \frac{\ln 8}{\ln 3} \approx 1{,}8928. \] Le tapis est « plus qu'une courbe, moins qu'une surface ».

3. Theoreme maitre. Soit \(T(n) = a\,T(n/b) + \Theta(n^d)\), avec \(a \ge 1\), \(b > 1\), \(d \ge 0\). Alors

\[ T(n) = \begin{cases} \Theta(n^d) & \text{si } d > \log_b a \quad\text{(le cout de combinaison domine)},\\[2pt] \Theta(n^d \log n) & \text{si } d = \log_b a \quad\text{(equilibre)},\\[2pt] \Theta(n^{\log_b a}) & \text{si } d < \log_b a \quad\text{(les feuilles dominent)}. \end{cases} \]

Idee de preuve : l'arbre des appels a \(\log_b n\) niveaux ; le niveau \(i\) comporte \(a^i\) sous-problemes de taille \(n/b^i\), donc coute \(a^i (n/b^i)^d = n^d (a/b^d)^i\). La somme est une serie geometrique de raison \(a/b^d\), dont le comportement depend du signe de \(d - \log_b a\).

4. Applications.

Le cas de Strassen est particulierement instructif : en remplacant 8 multiplications de blocs par 7 (au prix de 18 additions au lieu de 4), on fait passer \(a\) de 8 a 7, ce qui change l'exposant de 3 a 2,807. Une seule multiplication economisee suffit a ameliorer l'ordre de grandeur — c'est toute la puissance du diviser pour regner.