Algorithmes récursifs¶
10-02-2023
Objectifs
concevoir des fonctions récursives
tracer le calcul recursifs
estimation experimentale de la complexité de calculs récursifs
dessiner des fractales
Matériel fourni¶
À faire
Récupérez l’archive Recursion.zip et
décompressez la dans un dossier que vous nommerez Recursion.
Tracer une fonction récursive¶
La fonction nommée trace, définie dans le module
ap2_decorators est un décorateur, i.e. une fonction qui
ajoute certaines fonctionnalités à une autre fonction.
Ce décorateur a pour but d’imprimer une ligne marquant chaque appel à la fonction décorée accompagnée de ses arguments, ainsi qu’une ligne marquant la valeur renvoyée. Dans le cas d’appels récursifs successifs, les lignes sont indentées par des points.
Pour décorer une fonction, il suffit de placer l’instruction
@trace juste avant la définition de la fonction. Par exemple, pour
tracer la fonction factorielle on écrit
@trace
def fact(n: int) -> int:
"""
Renvoie n!
Condition d'utilisation : n >= 0
"""
if n == 0:
res = 1
else:
res = n * fact(n - 1)
return res
Et voici ce que donne un appel à la fonction fact ainsi décorée
par trace pour la valeur n=6
>>> fact(6)
-> fact((6,), {})
... -> fact((5,), {})
...... -> fact((4,), {})
......... -> fact((3,), {})
............ -> fact((2,), {})
............... -> fact((1,), {})
.................. -> fact((0,), {})
.................. <- 1
............... <- 1
............ <- 2
......... <- 6
...... <- 24
... <- 120
<- 720
720
On trace ainsi le calcul de \(6!\) en visualisant l’appel
initial ainsi que les six appels récursifs successifs, puis les sept
valeurs renvoyées par ces différents appels. La dernière ligne étant
la valeur renvoyée par fact(6).
À réaliser
Programmez les fonctions récursives de la feuille de td :
somme de deux nombres ;
binomial;is_palindromic.
et tracez quelques exécutions de chacune de ces fonctions.
Ces trois fonctions doivent être programmées dans le fichier
tracing_recursion.py.
Nombres de Fibonacci¶
Note
Pour cette partie, les fonctions à réaliser doivent l’être dans un fichier
fibonacci.py.
La suite des nombres de Fibonacci est définie par ses deux premiers termes \(f_0=0\): et \(f_1=1\) et pour tout entier \(n\geq 2\) par la relation de récurrence
À faire
Calculez «à la main» les nombres de Fibonacci jusqu’à \(n=10\).
À réaliser
Dans un fichier fibonacci.py, programmez une fonction
récursive nommée fibo qui pour un entier \(n\in\mathbb{N}\)
passé en paramètre renvoie le terme \(f_n\) de la suite de
Fibonacci.
Vérifiez la validité de votre programme en calculant les nombres \(f_n\) pour \(n\) compris entre 0 et 10.
À réaliser
Utilisez votre programme pour calculer \(f_{40}\). Que constatez-vous ?
À réaliser
Afin d’avoir une idée de la quantité de calculs nécessaires pour
calculer un nombre de Fibonacci avec votre programme, vous allez
décorer votre fonction avec le décorateur count du module
ap2_decorators qui permet de compter le nombre d’appels à la
fonction décorée.
Ce décorateur ajoute à la fonction un attribut (public) nommé
counter. La valeur de cet attribut est le nombre d’appels à la
fonction décorée réalisés depuis la dernière mise à 0.
Par exemple, en supposant que votre fonction fibo a été décorée
par count, et n’a pas encore été appelée, vous devriez avoir
>>> fibo.counter = 0
>>> fibo(4)
3
>>> fibo.counter
9
Le calcul de fibo(4) fait 9 appels à la fonction fibo
(l’appel initial + 8 appels récursifs).
À réaliser
Utilisez votre fonction ainsi décorée pour déterminer le nombre
d’appels à la fonction dans le calcul de \(f_n\) pour \(n\)
compris entre 0 et 10, puis pour \(n=40\). (Attention à veiller
à remettre l’attribut counter à 0 entre deux mesures.)
Dessins de fractales¶
La récursion est particulièrement bien adaptée aux dessins de fractales.
Note
Pour cette partie, les fonctions à réaliser doivent l’être dans un
fichier fractals.py.
Quelques fonctions du module turtle¶
Vous allez utiliser le module turtle. Il faut donc l’importer.
>>> import turtle
Voici listées les fonctions du module turtle que vous serez
amenés à utiliser pour les dessins qui suivent :
turtle.clearscreenturtle.speedturtle.exitonclickturtle.penupturtle.pendownturtle.gototurtle.forwardturtle.backwardturtle.leftturtle.right
À réaliser
Avant de passer à la production des dessins qui suivent, lisez la documentation sur ces fonctions et testez les !
En particulier, réalisez le zig-zag de la figure ci-dessous.
Courbe de Von Koch¶
Sur la figure ci-dessous vous pouvez observer les courbes de Von Koch de l’ordre 0 à l’ordre 5.
La courbe de Von Koch de l’ordre 0 à l’ordre 5¶
On remarque qu’à l’ordre \(n\) :
On divise le segment à tracer en trois segments égaux ;
On remplace le segment du milieu par les deux autres côtés d’un triangle équilatéral dont il est la base ;
On obtient alors quatre portions de tracé, qui sont chacune déssinées en appelant récursivement la fonction à l’ordre \(n-1\).
Question
Quelle est la relation entre la longueur de tracé \(\ell\) à l’ordre \(n\) et à l’ordre \(n+1\) de telle sorte que quel que soit l’ordre la largeur occupée par le tracé soit toujours la même ?
À réaliser
Programmez une fonction récursive à deux paramètres :
\(\ell\) de type
intoufloatprécisant la longueur séparant les deux extrémités\(n\) de type
intdonnant l’ordre de la courbe à dessiner
qui dessine la courbe de Von Koch d’ordre \(n\).
Vous programmerez cette fonction en utilisant exclusivement les quatre dernières fonctions de la tortue listées plus haut.
Le flocon de Von Koch à l’ordre 4¶
À réaliser
Programmez une fonction à deux paramètres :
\(\ell\) de type
intoufloatprécisant la longueur\(n\) de type
intdonnant l’ordre de la courbe à dessiner
qui dessine le flocon de Von Koch d’ordre \(n\) tel que le montre la figure ci-dessus lorsque \(n=4\).
Courbe de Cesaro¶
Une variante des courbes de Von Koch : les courbes de Cesaro. L’angle à la pointe observée à l’ordre 1 est de 10°.
La courbe de Cesaro de l’ordre 0 à l’ordre 5¶
Comme dans la courbe de Von Koch, le tracé d’un segment est remplacé par le tracé de quatre segments de longueurs égales, la largeur du tracé restant inchangée.
Voici deux schémas illustrant ce que l’on cherche à obtenir
Le détail de la construction lorsque l’angle vaut 10 degrés¶
Le détail de la construction lorsque l’angle vaut 40 degrés¶
Question
Quelle est la relation entre la longueur de tracé \(\ell\) à l’ordre \(n\) et à l’ordre \(n+1\) de telle sorte que quel que soit l’ordre la largeur occupée par le tracé soit toujours la même ?
À réaliser
Programmez une fonction récursive à deux paramètres :
\(\ell\) de type
intoufloatprécisant la longueur séparant les deux extrémités\(n\) de type
intdonnant l’ordre de la courbe à dessiner
qui dessine la courbe de Cesaro d’ordre \(n\).
Vous programmerez cette fonction en utilisant exclusivement les quatre dernières fonctions de la tortue listées plus haut.
Le carré de Cesaro à l’ordre 5¶
À réaliser
Programmez une fonction à deux paramètres :
\(\ell\) de type
intoufloatprécisant la longueur\(n\) de type
intdonnant l’ordre de la courbe à dessiner
qui dessine le carré de Cesaro d’ordre \(n\) tel que le montre la figure ci-dessus lorsque \(n=5\).
Triangle de Sierpinski¶
Le triangle de Sierpinski est une courbe fermée dont la figure de base est un triangle équilatéral. À l’étape \(n\), cette figure est constituée de trois figures d’ordre \(n-1\) de longueur divisée par deux.
Le triangle de Sierpinski de l’ordre 0 à l’ordre 5¶
La vidéo suivante montre un tracé possible des premiers triangles de Sierpinski :
Question
Quelle est la relation entre la longueur de tracé \(\ell\) à l’ordre \(n\) et à l’ordre \(n+1\) de telle sorte que quelque soit l’ordre la largeur occupée par le tracé soit toujours la même ?
À réaliser
Programmez une fonction récursive à deux paramètres :
\(\ell\) de type
intoufloatprécisant la taille du triangle\(n\) de type
intdonnant l’ordre de la courbe à dessiner
qui dessine le triangle de Sierpinski d’ordre \(n\).
