Exercice 6 - Itérateurs et aspirine

Dans les questions précédentes, l'itérateur faisait décroître $n$ de $1$ à chaque appel récursif. Soit $f$ la fonction à itérer et $x$ la valeur en $0$, nous pouvons définir un tel itérateur $\mathcal{I}$ de la sorte :

• $\mathcal{I}(f, n, x) = f(\mathcal{I}(f, n-1, x))$
• $\mathcal{I}(f, 0, x) = x$

Nous étendons une telle fonction en ajoutant en paramètre une fonction de décrément $\delta$, on obtient :

• $\mathcal{I}(\delta, f, n, x) = f(n, \mathcal{I}(\delta, f, \delta(n), x))$
• $\mathcal{I}(\delta, f, 0, x) = x$.

1. Implémentez la fonction $\mathcal{I}(\delta, f, n, x)$ en en utilisant le prototype suivant unsigned long applyFD(int (*delta)(int k), unsigned long (*f)(couple), int n, unsigned long x).
2. Ecrivez une fonction $f$ telle que $\mathcal{I}(\delta, f, n, b) = b^n$, vous utiliserez la relation de récurrence $b^n = b.b^{n-1}$ et $b^0 = 1$ et poserez $\delta : x \mapsto x - 1$.
3. Prouvez que $\mathcal{I}(\delta, f, n, b) = b^n$
4. Ecrivez en C la fonction unsigned long slowPuissanceIT(unsigned long b, unsigned long n), vous utiliserez applyFD et traduirez en C les fonctions $f$ et $\delta$ définies dans la question préccédente.
5. Ecrivez deux fonctions $f$ et $\delta$ telles que $\mathcal{I}(\delta, f, n, 1) = n!$
6. Prouvez que $\mathcal{I}(\delta, f, n, 1) = n!$
7. Ecrivez en C la fonction unsigned long fatorielleIT(unsigned long b, unsigned long n), vous utiliserez applyFD.
8. Ecrivez une fonction récursive $fastPuissance(b, n)$ calculant $b^n$ sans utiliser d'itérateur, vous utiliserez le fait que $$b^n = (b^2)^{\frac{n}{2}}$$ si $n$ est pair et $$b^n = b(b^2)^{\lfloor \frac{n}{2} \rfloor}$$ sinon.
9. Traduisez-là en C en utilisant le prototype suivant unsigned long fastPuissance(unsigned long b, unsigned long n).
10. Majorez le nombre d'appels récursifs en fonction de $n$, est-ce performant ?
11. Ecrivez la fonction $f$ et la fonction $\delta$ de sorte que $\mathcal{I}(\delta, f, n, b) = b^n$. Notez le fait que $f$ prend le couple $(n, b)$ en paramètre.
12. Prouvez par récurrence la validité de $\mathcal{I}(\delta, f, n, b) = b^n$.
13. Ecrivez en C la fonction unsigned long fastPuissanceIT(unsigned long b, unsigned long n), vous utiliserez la fonction applyFD.