Corrigé des exercices de révision sur la récursivité

Exercice 1 : Exponentiation rapide

Rappel : On souhaite calculer a^n avec les relations de récurrence suivantes : - a^0 = 1 - Si n est pair : a^n = (a * a)^(n / 2) - Sinon : a^n = a * (a * a)^((n - 1) / 2)

1. Version récursive

def exponentiation_rapide_recursive(a, n):
    if n == 0:
        return 1  # Cas de base
    elif n % 2 == 0:
        return exponentiation_rapide_recursive(a * a, n // 2)
    else:
        return a * exponentiation_rapide_recursive(a * a, (n - 1) // 2)

# Exemple de test
print(exponentiation_rapide_recursive(2, 10))  # Renvoie 1024

1. Version itérative

def exponentiation_rapide_iterative(a, n):
    result = 1
    while n > 0:
        if n % 2 == 1:  # Si n est impair
            result *= a
        a *= a
        n //= 2  # Diviser n par 2
    return result

# Exemple de test
print(exponentiation_rapide_iterative(2, 10))  # Renvoie 1024

---

Exercice 2 : Génération d’une liste décroissante

Fonction récursive

def generate_liste(n):
    if n == 0:
        return [0]  # Cas de base
    else:
        return [n] + generate_liste(n - 1)  # Ajoute n à la liste générée pour n-1

# Exemple de test
print(generate_liste(5))  # Renvoie [5, 4, 3, 2, 1, 0]

---

Exercice 3 : Multiplication égyptienne

Utiliser la technique pour a = 13 et b = 61

Étapes de la multiplication égyptienne
13 x 61 = 61
6 x 122
3 x 244 = 244
1 x 488 = 488
Total = 793

Fonction récursive :

def multiplication_egyptienne(a, b):
    if a == 0:
        return 0  # Cas de base : si a est 0, le produit est 0
    elif a % 2 == 1:
        return b + multiplication_egyptienne(a // 2, b * 2)  # Ajouter b si a est impair
    else:
        return multiplication_egyptienne(a // 2, b * 2)  # Continuer sans ajouter si a est pair

# Exemple de test
print(multiplication_egyptienne(13, 61))  # Renvoie 793

Complexité de l’algorithme

La complexité de cet algorithme dépend du nombre de divisions de a par 2, ce qui correspond à une complexité logarithmique : O(log a). En effet, chaque étape divise a par 2, ce qui signifie qu’il y aura environ log_2(a) itérations.