Ce TP n'est pas noté mais doit être rendu.

Tout TP non rendu avant le 06/10 (à 23h59) entraînera un zéro. Tout TP où il n'y aura pas un minimum d'effort, d'explications pour montrer le résultat d'un travail, d'une recherche se verra également attribué un zéro.

Veuillez mettre clairement vos noms et prénoms sur votre code source

Récursivité¶

Fractales¶

Exemples de fractales¶

Une fractale est un objet géométrique auto-similaire.

Le choux de Romanesco est un exemple de fractale présente dans la nature :

Buddhabrot :

Cette vidéo est déconseillée aux épiléptiques :

Flocon de Koch¶

Nous allons utiliser la librairie Turtle pour construire une fractale simple, le flocon de Koch, d'abord de manière itérative, puis de manière récursive.

Les méthodes Turtle dont nous aurons besoin :

Méthode	Paramètres	Description
`forward()`	`distance`	Déplace la tortue vers l’avant de `distance`
`right()`	`angle`	Tourne la tortue dans le sens des aiguilles d’une montre
`left()`	`angle`	Tourne la tortue dans le sens contraire des aiguilles d’une montre

Vous pouvez revoir les autres méthodes Turtle disponibles en cliquant ici : https://snt-nsi.net/nsi_terminale/activite_0/

Approche itérative¶

1) Ecrire une fonction nommée motif de paramètre L permettant de réaliser le motif suivant de longueur totale L.

Le triangle au milieu dont il manque un des côtés est équilatéral.

2) Ecrire une fonction nommée iteration1 de paramètre L permettant de dessiner la première itération de la droite de Koch ci-dessous de largeur totale L. On utilisera la fonction motif.

3) Ecrire une fonction nommée iteration2 de paramètre L permettant de dessiner la deuxième itération de la droite de Koch ci-dessous de largeur totale L. On utilisera la fonction iteration1.

Approche récursive¶

On voit que l'on utilise plusieurs fois le même motif. Pour résoudre ce problème de manière élégante on va utiliser une approche dite récursive.

1) Ecrire une fonction iteration de paramètres L et n permettant de dessiner la nième itération de la droite de Koch de largeur totale L. On utilisera la fonction iteration à l’intérieur même de sa déclaration.

Le cas de base, celui qui permet d'effectuer le tracé n'est pas évident à trouver dans ce cas. Pour vous aider un peu voici un schéma :

N'oubliez pas de décrémenter le nombre d'itérations n.

2) Ecrire une fonction nommée flocon de paramètre L et n permettant de dessiner la nième itération du flocon de Von Koch. L représente la largeur totale de la figure.

Utilisez la fonction "iteration" (de la question 1 juste au dessus) et une boucle.

Fibonacci¶

La suite de Fibonacci est définie par la relation de récurrence :

$F_{n} = F_{n-1} + F_{n-2}$

Les premiers termes de la suite :

$F 0$	$F 1$	$F 2$	$F 3$	$F 4$	$F 5$	$F 6$	$F 7$	$F 8$	$F 9$	$F 10$	$F 11$	$F 12$	$F 13$	$F 14$	$F 15$
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610

Ecrire une fonction récursive fibo(n) qui calcule et retourne la nième valeur de la suite de Fibonacci.

Tester avec une grande valeur pour $n$. Que constatez vous ?

complexité¶

Essayer de comprendre ce qui se passe en mémoire vive lors de ces différents appels récursifs. Faites un schéma sous la forme d'un arbre qui montre les différents appels effectués. Pouvez vous déterminer la complexité (en temps) dans le pire des cas de cet algorithme récursif ?

Les questions ci-dessous sont facultatives

PGCD¶

Écrire une fonction récursive pgcd(a, b) qui renvoie le PGCD de deux entiers a et b.