TP Récursivité

---

1. Courbe de Koch

Prérequis : Module turtle

La courbe de Koch est une figure fractale récursive. Elle fait partie des premières fractales décrites mathématiquement (1904).

Principe de construction

Ordre 0 : Un simple segment de longueur cote.

─────────────────────

Ordre 1 : Le segment est divisé en 3 parties égales. La partie centrale est remplacée par deux segments formant un triangle équilatéral sans sa base (un "chapeau" ^).

        /\
       /  \
──────/    \──────

Ordre 2 et suivants : On applique la même transformation à chaque segment de la figure précédente.

    /\
   /  \      /\
  /    \    /  \
─/      \──/    \─

Questions

1. Écrire de manière récursive le code de la fonction courbe_koch(n, cote) permettant de dessiner cette courbe à l'ordre n avec des segments de longueur cote.

Nous voulons obtenir maintenant un flocon de Koch. Celui-ci est composé de trois courbes de Koch disposées en triangle équilatéral.

1. Écrire le code de la fonction flocon(n, cote) qui dessine le flocon de Koch.

Indice : Le flocon est formé de 3 courbes de Koch, avec un angle de 120° entre chaque courbe.

---

2. Triangle de Pascal

Le triangle de Pascal représente les coefficients binomiaux sous la forme d'un triangle :

        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1
   1 5 10 10 5 1

La fonction coef(n, p) permet de calculer le coefficient à la ligne n et colonne p :

\[ coef(n, p) = \begin{cases} 1 & \text{si } p = 0 \text{ ou } n = p\\ coef(n-1, p-1) + coef(n-1, p) & \text{sinon} \end{cases} \]

Questions

1. Écrire le code de la fonction récursive coef(n, p).

Le sommet du triangle est le résultat de coef(0, 0), la première ligne est représentée par coef(1, 0) et coef(1, 1), ainsi de suite pour les autres lignes.

1. À l'aide de deux boucles, écrire un code permettant d'afficher les 6 premières lignes du triangle.

---

3. Recherche dichotomique

La recherche dichotomique fonctionne sur un tableau trié et permet de trouver un élément de façon optimale en O(log n).

Voici le code de la recherche dichotomique (programme de 1ère) de manière itérative :

def recherche_dichotomique(t, v):
    debut = 0
    fin = len(t) - 1
    while debut <= fin:
        milieu = (debut + fin) // 2
        if t[milieu] == v:
            return True
        elif t[milieu] > v:
            fin = milieu - 1
        else:
            debut = milieu + 1
    return False

Question

1. Réécrire ce code en version récursive. La fonction prendra en paramètres le tableau t, la valeur cherchée v, ainsi que les indices debut et fin.