2. Algorithmes récursifs

sept. 24, 2018

Objectifs

  • concevoir des fonctions récursives
  • tracer le calcul recursifs
  • estimation experimentale de la complexité de calculs récursifs
  • dessiner des fractales
  • rédiger un peu de documentation au format reStructured Text (rst).

2.1. Matériel fourni

À faire

Récupérez l’archive Recursion.zip et décompressez la dans un dossier que vous nommerez Recursion.

Vous y trouverez l’aborescence de fichiers décrite dans le TP précédent.

À faire

Complétez la variable AUTHOR du fichier Makefile en lui attribuant votre nom, ou les noms du binôme.

Puis produisez la documentation au format HTML :

$ make doc

2.2. Tracer une fonction récursive

La fonction nommée trace, définie dans le module ap2_decorators (situé dans le dossier src) 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):
    if n == 0:
       return 1
    else:
       return n * fact(n - 1)

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

  • somme de deux nombres (exercice 3 feuille TD n°2),
  • binomial (exercice 7 feuille TD n°2),
  • is_palindromic (exercice 8 feuille TD n°2)

et tracez quelques exécutions de chacune de ces fonctions.

Ces trois fonctions doivent être programmées dans le fichier src/tracing_recursion.py.

Enlevez les commentaires (deux poins de début de ligne) dans le fichier de documentation sourcedoc/tracing_recursion.rst.

2.3. Nombres de Fibonacci

Note

Pour cette partie, les fonctions à réaliser doivent l’être dans un fichier src/fibonacci.py et la documentation générale dans le fichier sourcedoc/fibonacci.rst.

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

\[f_n = f_{n-1} + f_{n-2}.\]

À faire

Calculez «à la main» les nombres de Fibonacci jusqu’à \(n=10\), et reportez les valeurs que vous trouvez dans le tableau à compléter dans le fichier sourcedoc/fibonacci.rst.

À réaliser

Dans un fichier src/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. (pour cela vous devrez préalablement calculer «à la main» ces nombres.)

À réaliser

Utilisez votre programme pour calculer \(f_{40}\). Que constatez-vous ? Rédigez votre réponse dans le fichier sourcedoc/fibonacci.rst.

À 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.)

Rédigez votre réponse dans le fichier sourcedoc/fibonacci.rst.

2.4. 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 src/fractals.py et la documentation générale dans le fichier sourcedoc/fractals.rst.

2.4.1. 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.clearscreen
  • turtle.speed
  • turtle.exitonclick
  • turtle.penup
  • turtle.pendown
  • turtle.goto
  • turtle.forward
  • turtle.backward
  • turtle.left
  • turtle.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.

un zig-zag

2.4.2. 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

La courbe de Von Koch de l’ordre 0 à l’ordre 5

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 int ou float précisant la longueur séparant les deux extrémités
  • \(n\) de type int donnant 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

Le flocon de Von Koch à l’ordre 4

À réaliser

Programmez une fonction à deux paramètres :

  • \(\ell\) de type int ou float précisant la longueur
  • \(n\) de type int donnant 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\).

2.4.3. 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

La courbe de Cesaro de l’ordre 0 à l’ordre 5

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 int ou float précisant la longueur séparant les deux extrémités
  • \(n\) de type int donnant 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

Le carré de Cesaro à l’ordre 5

À réaliser

Programmez une fonction à deux paramètres :

  • \(\ell\) de type int ou float précisant la longueur
  • \(n\) de type int donnant 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\).

2.4.4. Triangle de Sierpinski

le triangle de Sierpinski de l'ordre 0 à l'ordre 5

Le triangle de Sierpinski de l’ordre 0 à l’ordre 5

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 int ou float précisant la taille du triangle
  • \(n\) de type int donnant l’ordre de la courbe à dessiner

qui dessine le triangle de Sierpinski d’ordre \(n\).