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$.

A. Les appels sont : factorielle(5), factorielle(4), factorielle(3), factorielle(2), factorielle(1). Le cas de base est n == 1 (ou n == 0 selon l’implémentation). Pour factorielle avec cas de base n <= 1, on a cinq appels. Si le cas de base est n == 0, on en a six.

Note : la réponse dépend de la définition du cas de base. Si factorielle(0) = 1 est le cas de base, la réponse est B (six appels).

D. Chaque appel génère deux nouveaux appels, ce qui produit un arbre d’appels dont le nombre de nœuds 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.

d) Cas de base : arbre is None (sous-arbre vide, on renvoie False) ou arbre.valeur == element (on a trouvé, on renvoie True). Appels récursifs : chercher(element, arbre.gauche) et chercher(element, arbre.droite). Le problème se réduit car on explore des sous-arbres de plus en plus petits. C’est un exemple de récursivité avec deux appels (récursivité double), typique du parcours d’arbres.

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(5)
                  /        \
             fib(4)        fib(3)
            /     \        /     \
        fib(3)  fib(2)  fib(2)  fib(1)
        /   \    / \     / \
   fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
    / \
fib(1) fib(0)

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.