Exercices Récursivité

---

Exercice 1 : Exponentiation rapide

On rappelle que l'exponentiation rapide permet de calculer le nombre aⁿ en utilisant les relations de récurrence suivantes :

• a⁰ = 1
• Si n est pair : aⁿ = (a × a)^n/2
• Sinon : aⁿ = a × (a × a)^(n-1)/2

Questions :

1. Écrire une version récursive de l'exponentiation rapide.
2. Écrire une version itérative de l'exponentiation rapide.

---

Exercice 2 : Liste décroissante

Écrire une fonction récursive d'argument n qui génère la liste suivante :

[n, n-1, ..., 1, 0]

---

Exercice 3 : Multiplication égyptienne

La multiplication égyptienne, dite aussi du paysan russe, était utilisée par les scribes dès l'Antiquité. Elle ne nécessite pas la connaissance des tables de multiplication, seulement l'addition et la division par deux.

On multiplie deux entiers, a et b de la manière suivante : on divise a par 2 tant que c'est possible, en doublant b, sinon on décrémente a et on ajoute b au résultat.

Questions :

1. Utiliser cette technique pour calculer le produit a × b avec a = 13 et b = 61.
2. Écrire une fonction récursive qui calcule le produit de a et b en utilisant la multiplication égyptienne.
3. Quelle est la complexité de cet algorithme en fonction de a ?