En mathématiques, vous êtes nombreux à avoir vu les suites en spécialité de 1ère. Une suite définie par récurrence simple s'écrit sous la forme $ u_{n + 1} = f(u_n) $.
Si on "descend" d'un rang, on obtient $ u_{n + 1} = f(f(u_{n-1})) $ , et plus généralement
$u_{n + 1} = \underbrace{f(f(f(\dots f(u_0))))}_{\text{$n$ fois.}}$.
En informatique, la récurisivité se rapproche de ce type de raisonnement. Une fonction récursive est une fonction qui s'appelle elle-même.
La fonction factorielle est la fonction notée $!$. Vous avez peut-être déjà vu cette fonction en mathématiques. Elle s'applique sur les entiers naturels et vaut :
$
\left\{
\begin{array}{ll}
0! = 1 \\
n! = n\times n - 1 \times n - 2 \times \dots \times 1\\
\end{array}
\right.
$
On lit "factorielle n" de préférence.
Voici un des multiples algorithme de calcul de la factorielle en itératif.
Algorihtme : factorielle itérative
Donnée : un entier naturel $n$
Renvoie : $n!$
Début
f $\leftarrow$ 1
si n $\ne$ 0i $\leftarrow$ 1
Tant que i < n fairei $\leftarrow$ i + 1
f $\leftarrow$ f $\times$ iFin Tant que
Renvoyer f
fin
Ci-dessous le code correspondant. On a rajouté une ligne de code permettant de mesurer le temps d'exécution de la fonction, calculé en moyenne sur un grand nombre de fois (attention cela prend quelques secondes supplémentaires)
%timeit (fact(6))
Dans l'affichage du temps, "mean" signifie moyenne et std. dev. signifie "écart-type"
def fact(n) :
"""
Calcul la factorielle de n
@param n : entier positif ou nul
@return f : entier strictement positif, égal à n!
"""
f = 1
if n != 0 :
i = 1
while i < n :
i = i + 1
f = f * i
return f
print(fact(6))
%timeit (fact(6))
Comme vous pouvez le constater avec quelques tests, la fonction factorielle est une fonction qui croît très rapidement, plus encore que l'exponentielle. Pour l'exemple, si un programme de complexité $O(n!)$ met un temps de $1,2 \mu s$ pour $n = 5$ alors il mettra un temps $10^{48}$ ans pour $n = 50$, contre une centaine de jours pour un programme de complexité exponentielle.
Voyons ci-dessous un algorithme de calcul de la factorielle en version récursive.
Algorihtme : factorielle récursive
Donnée : un entier naturel $n$
Renvoie : $n!$
Début
fonction fact(n)
si n = 0
renvoyer 1
sinon
renvoyer n $\times$ fact(n - 1)
fin si
fin
Le code est ci-dessous. Vous pouvez comparer l'efficacité des deux fonctions avec timeit
def fact(n) :
if n == 0:
return 1
else :
return n * fact(n - 1)
assert( fact(6) == 720)
assert(fact(10) == 3628800)
assert(fact(0) == 1)
assert(fact(1) == 1)
print(fact(6))
%timeit (fact(6))
Copiez ce code (sans les assert
), et visualisez-en l'exécution sur Python Tutor. Vous y verrez notamment l'évolution de la "pile d'appels".
Tout doit bien sûr être programmé en récursif ! Utilisez Spyder de préférence, ou un autre IDE.
Un exercice rigolo
Peut-être certains d'entre vous ont déjà utilisé le module turtle
de Python. Ce module permet de programmer une "tortue" qui dessine. Les instructions principales sont :
forward(nombre)
: avancer de nombre (en pixels)backward(nombre)
: avancer de nombreleft(angle)
: tourner de angle vers la gaucheright(angle)
: tourner de angle vers la droiteclear()
: effacer le dessingoto(x,y)
: aller au point de coordonnées spécifiées On va travailler sur le flocon de Von Koch, qui est une structure fractale. Partant d'un triangle équilatéral, on découpe chaque segment en trois, on enlève le tiers médian que l'on remplace par les deux côtés de même taille d'un triangle équilatéral vers l'extérieur. Et on itère jusqu'à +∞. Comme vous le voyez, la construction récursive est apparente. La figure ci-dessous donne les quatre premières étapes de la construction.
Le but de cet exercice est de tracer une approximation du flocon de Von Koch, et de conjecturer ses propriétés sur le périmètre et la surface.
Un morceau de code pour vous lancer :
import turtle
def FractaleKoch(n, longueur) :
if n==0 :
turtle.forward(longueur)
else :
FractaleKoch(n-1, longueur/3)
turtle.left(60)
FractaleKoch(n-1, longueur/3)
turtle.right(120)
FractaleKoch(n-1, longueur/3)
turtle.left(60)
FractaleKoch(n-1, longueur/3)
longueur_segment_initial=400
turtle.up()
turtle.goto(longueur_segment_initial/40 - 500, longueur_segment_initial/100)
turtle.down()
FractaleKoch(3, longueur_segment_initial)
turtle.up()
turtle.ht()
turtle.exitonclick()
Recopier et compléter ce code de manière à tracer le flocon pour un rang donné, et donner son aire et son périmètre.
Conjecturer la valeur de l'aire et du périmètre en +∞. Plus mathématiquement : que valent $\displaystyle\lim\limits_{n \to +\infty} (\textrm{aire}_n)$ et $\lim\limits_{n \to +\infty} (\textrm{périmètre}_n)$ ?
Remarque : prouver ces conjectures est un exercice intéressant de spécialité mathématiques sur les suites, assez facile.
Pour ceux qui vont vite.
On définit deux suites (un) et (vn) au moyen des équations suivantes :
$$
\left\{
\begin{array}{c c}
u_0 = 1 \\
v_0 = 100 & \\
u_{n + 1} = \displaystyle\frac{1}{5}(3u_n + 2v_n) & \textrm{ si } n \ge 0 \\
v_{n + 1} = \displaystyle\frac{1}{5}(2u_n + 3v_n) & \textrm{ si } n \ge 0 \\
\end{array}
\right.
$$
Écrire, pour chacune des deux suites, une fonction qui, étant donné un entier naturel $n$ donné, calcule son terme d'indice $n$. Tester en affichant tous les termes de 1 à 20, que remarque-t-on ?
La fonction $f_{91}$ est définie pour tout entier naturel par :
$$
f(n) = \left\{
\begin{array}{c c}
n - 10 & \textrm{ si } n \gt 100 \\
f\left(f(n + 11)\right) & \textrm{ sinon }\\
\end{array}
\right.
$$
def f91(n: int) -> int:
"""
fonction f91 de McCarthy
"""
l_res = []
for i in range (200):
l_res.append(f91(i))
print(l_res)
Que pensez-vous de la terminaison du calcul de $f_{91}(n)$ ?
Quelles réflexions vous inspirent les fonctions récursives suivantes ? Je vous conseille d'éditer la cellule (par un double clic) afin de noter vos réponses précises, pour pourvoir réviser.
$ f(n) = \left{
\begin{array}{c c}
1 & \textrm{si } n = 0 \\
n \times f(n + 1) & \textrm{sinon }\\
\end{array}
\right.
$
Réponse :
$ f(n) = \left{
\begin{array}{c c}
1 & \textrm{si } n = 0 \\
n \times f(n - 2) & \textrm{sinon }\\
\end{array}
\right.
$
Réponse :
$ f(n) = \left{
\begin{array}{c c}
1 & \textrm{si } n = 0 \\
n \times f(n - 1) & \textrm{si } n \gt 1\\
\end{array}
\right.
$
Réponse :
On veut calculer un terme de rang donné de la suite de Fibonacci, dont la définition par récurrence sur $\mathbb{N}$ est :
$$ \left\{ \begin{array}{lll} u_0 = 0 \\ u_1 = 1 \\ u_n = u_{n - 1} + u_{n - 2} \\ \end{array} \right. $$
Ecrire le programme récursif donnant la valeur de rang donné d'un élément de la suite de Fibonacci.
Testez-le en calculant quelques valeurs, de plus en plus grandes.
def fiboRec(rang):
def fiboRecC(rang , compteur = 0):
n = 30
print(fiboRec(n))
Comme vous le constatez peut-être, ce programme est lent... Vous pouvez visulaiser la pile d'appels avec Python Tutor.
Rajoutez un compteur pour compter le nombre d'appels de la fonction (soyons fous, une variable globale est autorisée, mais sans c'est mieux). Placez quelques points $(n ; y)$ dans un repère, où $n$ est le rang du terme calculé de la suite de Fibonacci, $y$ est le nombre d'appel de la fonction. Conjecturer ensuite la nature de la complexité de l'algorithme récursif de Fibonacci (constante, logarithmique, linéaire, log-linéaire, quadratique, exponentielle, factorielle).
Vous pouvez en plus utiliser l'instruction %timeit (fibo(n))
, pour avoir les temps d'exécution.
Ecrivez ensuite un programme plus simple, de complexité spatiale minimale, et plus rapide, pour calculer un terme donné de la suite de Fibonnacci. Donner la complexité temporelle du programme construit.
<hr style="color:black; height:1px />
<div style="float:left;margin:0 10px 10px 0" markdown="1" style = "font-size = "x-small">
Ce(tte) œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.
frederic.mandon@
ac-montpellier.fr, Lycée Jean Jaurès - Saint Clément de Rivière - France (2015-2019)</div>