WikiMath

Récursivité

Factorielle d'un entier naturel

On peut définir de façon récursive la factorielle d'un entier positif $n$ par :

 $n!=1 \;\mathrm{ si }\; n=0$

$n!=n(n-1)!\; \mathrm{ si }\; n>0 $

1. Ecrire une fonction $facto(n)$ qui calcule $n!$ de façon récursive.
2. Par combien de zéros l'entier 50! se termine-t-il ?

Suite de Fibonacci

La suite de Fibonacci est définie par : $F_0=0\;,\;F_1=1$ et $\;\forall\,n\in\mathbb N,\;F_{n+2}=F_{n+1}+F_n $

1. Calculer à la main $F_2\;,\;F_3\;,\;F_4\;$ et $\;F_5$.
2. Ecrire une fonction récursive $fibo(n)$ qui calcule le $n$-ième terme $F_n$ de cette suite.
3. Que vaut $F_{35}$ ?

Dichotomie

On rappelle le théorème dit "de la bijection" (corollaire du théorème des valeurs intermédiaires) :

Si $f:[a,b]\rightarrow \mathbb R$ est une fonction continue et strictement monotone sur un intervalle [$a,b$] et si $f(a)f(b)<0$, alors l'équation $f(x)=0$ admet une unique solution $x_0$ dans [$a,b$].

On souhaite obtenir une valeur approchée de $x_0$ à $\varepsilon$ près de la manière suivante :

• on pose $c=(a+b)/2$
• si $f(a)f(c)<0$ alors on cherche dans [$a,c$]
• sinon on cherche dans [$c,b$]

On utilise cette méthode de façon récursive et on s'arrête quand l'intervalle est de longueur strictement inférieure à $\varepsilon$. Le centre du dernier intervalle convient alors comme solution approchée de l'équation $f(x)=0$ à $\varepsilon$ près.

1. Démontrer que l'équation $x^5+3x=7$ admet une unique solution $x_0$ et encadrer $x_0$ par deux entiers consécutifs.
2. Programmer cet algorithme sous forme d'une fonction récursive $dichot(f,a,b,eps)$
3. Tester ce programme en prenant $f(x)=x^5+3x-7\;,\;a=1\;,\;b=2\;$ et $eps=10^{-9}$.