Exercices : récursivité

B. Sans cas de base, la fonction s’appelle indéfiniment et provoque un RecursionError (dépassement de la taille de la pile d’appels). A est faux (la récursivité remplace justement les boucles). C et D ne sont pas des conditions nécessaires : une fonction récursive peut n’avoir qu’un seul paramètre et renvoyer un entier.

C. $f(4) = 2 \times f(3) = 2 \times 2 \times f(2) = 2 \times 2 \times 2 \times f(1) = 2 \times 2 \times 2 \times 2 \times f(0) = 2^4 \times 1 = 16$. Cette fonction calcule $2^n$. A confond $f(n)$ et $n$. B confond avec $2^3$. D confond avec $2^5$.

B. Les appels sont : factorielle(5), factorielle(4), factorielle(3), factorielle(2), factorielle(1) et factorielle(0). Le cas de base est n == 0 : on a donc six appels. A oublie l’appel factorielle(0), qui est le cas de base. C et D surestiment le nombre d’appels : chaque appel, sauf le cas de base, n’en déclenche qu’un seul autre.

D. Chaque appel génère deux nouveaux appels, ce qui produit un arbre d’appels dont le nombre d’appels croît exponentiellement. A est la complexité de la version itérative ou mémoïsée. B et C sont des complexités polynomiales qui ne correspondent pas à la structure de l’arbre d’appels.

a) Cas de base : n == 0 (on ne fait rien, la récursion s’arrête). Appel récursif : compte_a_rebours(n - 1), le problème se réduit car n diminue de 1 à chaque appel, jusqu’à atteindre 0.

b) Cas de base implicite : un dossier qui ne contient aucun sous-dossier (la boucle for ne fait aucun appel récursif, on ne fait que compter les fichiers). Appel récursif : nb_fichiers(chemin) quand l’élément est un sous-dossier. Le problème se réduit car on descend dans l’arborescence : chaque sous-dossier est plus « petit » que son parent. C’est un exemple de récursivité appliquée au domaine de l’informatique (parcours de système de fichiers).

c) Cas de base : b == 0, on renvoie a. Appel récursif : pgcd(b, a % b). Le problème se réduit car le reste a % b est strictement inférieur à b, donc b diminue à chaque appel. C’est l’algorithme d’Euclide.

a)

somme([3, 5, 2])
  = 3 + somme([5, 2])
  = 3 + (5 + somme([2]))
  = 3 + (5 + (2 + somme([])))
  = 3 + (5 + (2 + 0))         ← cas de base (liste vide)
  = 3 + (5 + 2) = 3 + 7 = 10

b)

nb_voyelles("bonjour")
  "b" n'est pas une voyelle → nb_voyelles("onjour")
  "o" est une voyelle → 1 + nb_voyelles("njour")
  "n" non → nb_voyelles("jour")
  "j" non → nb_voyelles("our")
  "o" oui → 1 + nb_voyelles("ur")
  "u" oui → 1 + nb_voyelles("r")
  "r" non → nb_voyelles("")
  "" → 0                       ← cas de base (chaîne vide)
Dépilage : 0 → 0 → 1+0=1 → 1+1=2 → 2 → 2 → 1+2=3 → 3
Résultat : 3 voyelles (o, o, u).

c)

nb_chiffres(4073)
  4073 >= 10 → 1 + nb_chiffres(407)
  407 >= 10 → 1 + nb_chiffres(40)
  40 >= 10 → 1 + nb_chiffres(4)
  4 < 10 → 1                  ← cas de base
Dépilage : 1 → 1+1=2 → 1+2=3 → 1+3=4
Résultat : 4 chiffres.

a) (1) : n (un nombre à un chiffre est sa propre somme). (2) : n % 10 (le dernier chiffre). (3) : n // 10 (le nombre sans son dernier chiffre).

def somme_chiffres(n):
    if n < 10:
        return n
    return n % 10 + somme_chiffres(n // 10)

Vérification : somme_chiffres(347) = $7 + somme_chiffres(34) = 7 + 4 + somme_chiffres(3) = 7 + 4 + 3 = 14$.

b) (4) : False (l’élément n’est pas dans une liste vide). (5) : True (on l’a trouvé). (6) : L[1:], x (on cherche dans le reste de la liste).

def contient(L, x):
    if len(L) == 0:
        return False
    if L[0] == x:
        return True
    return contient(L[1:], x)

c) (7) : 0 (aucune occurrence dans une chaîne vide). (8) : 1. (9) : chaine[1:], c. (10) : chaine[1:], c.

def compter(chaine, c):
    if chaine == "":
        return 0
    if chaine[0] == c:
        return 1 + compter(chaine[1:], c)
    return compter(chaine[1:], c)

Vérification : compter("ananas", "a") = $1 + 1 + 1 = 3$.

a)

def population(n):
    if n == 0:
        return 1
    return 2 * population(n - 1)

Cas de base : au temps 0, une seule bactérie. Appel récursif : à chaque heure, la population double. population(n) renvoie $2^n$.

b)

import os

def taille_dossier(chemin):
    if not os.path.isdir(chemin):
        return os.path.getsize(chemin)
    total = 0
    for element in os.listdir(chemin):
        sous_chemin = os.path.join(chemin, element)
        total += taille_dossier(sous_chemin)
    return total

Cas de base : si le chemin est un fichier (pas un dossier), on renvoie sa taille. Appel récursif : pour un dossier, on additionne les tailles de tous ses éléments (fichiers et sous-dossiers), chaque sous-dossier étant traité récursivement.

c)

import math

def longueur_cote(points):
    if len(points) <= 1:
        return 0
    x1, y1 = points[0]
    x2, y2 = points[1]
    d = math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
    return d + longueur_cote(points[1:])

Cas de base : une liste de zéro ou un point a une longueur nulle. Appel récursif : on ajoute la distance entre les deux premiers points et la longueur de la ligne brisée restante.

a)

def longueur(L):
    if L == []:
        return 0
    return 1 + longueur(L[1:])

Cas de base : une liste vide a une longueur 0. Appel récursif : on ajoute 1 (pour le premier élément) et on calcule la longueur du reste.

b)

def maximum(L):
    if len(L) == 1:
        return L[0]
    m = maximum(L[1:])
    if L[0] > m:
        return L[0]
    return m

Cas de base : une liste d’un élément, dont le maximum est cet élément. Appel récursif : on compare le premier élément au maximum du reste.

c)

def miroir(L):
    if L == []:
        return []
    return miroir(L[1:]) + [L[0]]

Cas de base : le miroir d’une liste vide est une liste vide. Appel récursif : on inverse le reste de la liste et on ajoute le premier élément à la fin.

d) (Bonus)

def aplatir(L):
    if L == []:
        return []
    if isinstance(L[0], list):
        return aplatir(L[0]) + aplatir(L[1:])
    return [L[0]] + aplatir(L[1:])

Si le premier élément est une liste, on l’aplatit récursivement avant de le concaténer avec le résultat de l’aplatissement du reste. Sinon, on le garde tel quel.

a) Arbre d’appels de fibonacci(5) :

fib(2) est calculé trois fois, fib(3) est calculé deux fois, fib(1) est calculé cinq fois. La redondance croît exponentiellement avec $n$.

b) L’arbre d’appels de fibonacci(35) contient $2 \cdot F(36) - 1 = 29,860,703$ appels : les mêmes valeurs sont recalculées un nombre exponentiel de fois (la croissance est en $\varphi^n$, avec $\varphi \approx 1{,}618$). Par exemple, fibonacci(2) est calculé plus de 5 millions de fois.

c)

def fibonacci_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

Avant de calculer, on vérifie si le résultat est déjà dans le dictionnaire. Sinon, on le calcule, on le stocke, puis on le renvoie.

d) La complexité est $O(n)$ en temps et $O(n)$ en mémoire. Chaque valeur de fibonacci(k) est calculée au plus une fois (les appels suivants la trouvent dans le dictionnaire). On passe d’une complexité exponentielle $O(2^n)$ à une complexité linéaire.

a) Pour deux disques :

1. Déplacer le petit disque de A vers B ;
2. déplacer le grand disque de A vers C ;
3. déplacer le petit disque de B vers C.

Il faut trois déplacements.

b) L’idée récursive pour déplacer $n$ disques de A vers C :

1. Déplacer les $n-1$ disques du dessus de A vers B (en utilisant C comme auxiliaire) ;
2. déplacer le grand disque de A vers C ;
3. déplacer les $n-1$ disques de B vers C (en utilisant A comme auxiliaire).

L’étape 1 et l’étape 3 sont des sous-problèmes de même nature avec $n-1$ disques : c’est la récursivité. Le cas de base est $n = 1$ : on déplace directement le disque.

c)

def hanoi(n, source, destination, auxiliaire):
    if n == 1:
        print(f"Déplacer disque de {source} vers {destination}")
        return
    hanoi(n - 1, source, auxiliaire, destination)
    print(f"Déplacer disque de {source} vers {destination}")
    hanoi(n - 1, auxiliaire, destination, source)

Pour $n = 3$ :

Déplacer disque de A vers C
Déplacer disque de A vers B
Déplacer disque de C vers B
Déplacer disque de A vers C
Déplacer disque de B vers A
Déplacer disque de B vers C
Déplacer disque de A vers C

d) $T(1) = 1$ (un seul déplacement). Pour $n > 1$ : $T(n) = T(n-1) + 1 + T(n-1) = 2 \times T(n-1) + 1$.

Montrons que $T(n) = 2^n - 1$ par récurrence : $T(1) = 2^1 - 1 = 1$ (vrai). Supposons $T(k) = 2^k - 1$ pour un certain $k \geq 1$. Alors $T(k+1) = 2 \times (2^k - 1) + 1 = 2^{k+1} - 2 + 1 = 2^{k+1} - 1$.

e)

def hanoi_compteur(n, source, destination, auxiliaire):
    if n == 1:
        return 1
    return (hanoi_compteur(n - 1, source, auxiliaire, destination)
            + 1
            + hanoi_compteur(n - 1, auxiliaire, destination, source))

for k in range(1, 8):
    print(f"n={k} : {hanoi_compteur(k, 'A', 'C', 'B')}"
          f" déplacements (2^{k}-1 = {2**k - 1})")

On vérifie bien $T(n) = 2^n - 1$ pour chaque valeur.