Introduction à la récursivité

Flocon de Koch

from turtle import forward,left,right,exitonclick

def flocon(n, taille):
    if n==0:
        forward(taille)
    else:
        forward(taille/3)
        left(60)
        forward(taille/3)
        right(120)
        forward(taille/3)
        left(60)
        forward(taille/3)

exitonclick()

Copiez ce code dans VSCodium, et juste avant le exitonclick() qui permet de laisser le dessin ouvert jusqu'à ce qu'on clique dessus :
- Testez ce que fait la fonction flocon avec n=0 et taille=200
- Testez avec n=1

Récursivité

Une fonction récursive est une fonction qui contient dans son code un appel à elle-même.

C'est tout à fait autorisé en python.

Changez dans la fonction flocon chacune des lignes forward(taille/3) en un appel récursif à la fonction flocon qui fasse la même chose si on l'appelle avec n=1. Testez pour vérifier.
Vérifiez qu'avec ces appels récursifs la fonction flocon avec n=2 appelle la fonction flocon avec n=1, qui elle-même appelera la fonction flocon avec n=0. Testez avec n=2, puis n=3.
Importez la fonction speed du module turtle et appelez speed(10) au début du programme pour dessiner plus vite.
Appelez trois fois la fonction flocon en tournant de 120° entre chaque appel pour dessiner en entier le Flocon de Koch. Plus on augmente la valeur de n, plus on se rapproche de cette courbe fractale.

"Boucle" infinie sans while

Créez une fonction toute simple qui affiche un message avec print.
Ajoutez un appel récursif pour que des messages s'affichent sans s'arrêter, sans utiliser de boucle.

Warning

Avec des appels récursifs, on peut créer un programme qui ne se termine pas comme avec une boucle while.

Est-ce que le programme tourne vraiment sans s'arrêter ? Que se passe-t-il en python ?

"Boucle" qui se répète n fois

Modifiez votre programme précédent en ajoutant un paramètre qui précise combien de fois la fonction doit s'appeler elle-même.

Par exemple si on l'appelle avec 5 comme argument, on doit avoir 5 messages affichés puis le programme s'arrête.

Info

Ceci est la manière dont certains langages de programmation dits "fonctionnels" font pour répéter des instructions sans utiliser de boucles for ou while.

Warning

Vous avez dû mettre un test pour que les appels récursifs s'arrêtent (par exemple quand le paramètre vaut 0).

On appelle ces situations où il ne faut plus faire d'appels récursifs les cas de bases et il faut toujours qu'il y en ait quand on écrit des fonctions récursives, sinon on est sûrs d'avoir des appels infinis.

Calculer une suite récursive

En maths vous avez probablement vu des suites définis comme ceci :

\(u_0 = 3\)

\(u_{n+1} = 2*u_n - 10\)

On peut coder une fonction u qui prend comme paramètre n et renvoie \(u_n\) en utilisant une liste et une boucle for et en rajoutant les valeurs de u une par une à la fin de la liste jusqu'à atteindre \(u_n\).

Mais en fait, le code python sera plus simple et très proche de la définition si on utilise la récursivité. Il suffit de coder la fonction u en disant que :

soit n vaut 0 et on renvoie 3
sinon, on renvoie 2*u(n-1) - 10

Exercice : Écrivez la version récursive. Puis, écrivez la version sans récursivité avec la liste et la boucle for, pour comparer.