16. Revenir - f(n)¶
Dans ce chapitre, nous allons découvrir la récursivité. La définition d’une fonction f(n) qui contient à l’intérieur de sa définition le terme f(n-1) représente une fonction récursive, c’est-à-dire une fonction qui revient vers elle-même. Elle s’autoappelle souvent avec une valeur plus simple, par exemple n-1 au lieu de n. Vous allez voir que :
une boucle
while True:donne une boucle infinie,le nombre de fois une fonction peut s’appeler soi-même est limité,
une condition de terminaison permet à une fonction récursive de finir.
16.1. Boucle infinie¶
Il est très facile de créer une boucle qui ne se termine jamais. La façon standard pour une boucle infinie est d’utiliser le terme while True: qui répète à l’infini le bloc qui suit, car la condition de terminaison est toujours vraie.
Souvent ceci est un bug, et représente le cas où l’exécution reste bloquée dans une boucle et le programme ne réagit plus.
Attention : pour terminer ce programme, cliquez sur Interrompre.
Pour terminer une boucle infinie et en sortir, nous pouvons utiliser le mot-clé break. La boucle while True: est alors quittée et le programme continue avec l’instruction suivante à l’extérieur de la boucle.
Dans ce cas, on aurait pu écrire de façon plus simple encore:
16.2. Fonction récursive¶
Nous faisons maintenant la même chose, mais cette fois en utilisant une fonction récursive. Dans ce premier exemple, nous n’avons pas de condition de terminaison, et donc la fonction est appelée en continu. La fonction f(n) imprime la valeur n et s’appelle ensuite elle-même avec une valeur plus petite f(n-1) et ainsi de suite.
Le comportement est différent. Nous constatons que la fonction s’arrête après quelques centaines d’appels récursifs. C’est une limite qui peut être définie dans le compilateur Python.
16.3. Condition de terminaison¶
Cette fois dans notre fonction récursive, nous prévoyons une condition de terminaison qui va interrompre la récursivité.
16.4. Factorielle¶
La fonction factorielle est une fonction que nous pouvons écrire très facilement sous forme récursive. La factorielle retourne le produit de tous les entiers de 1 à n.
16.5. Carré¶
Mais aussi la fonction carre(n) peut être écrite sous forme récursive.
Exercice 1
Définissez la fonction cube(n) sous forme récursive.
16.6. Flocon de Koch¶
La courbe de Koch est une ligne coupée en 3 avec un triangle isocèle dessiné sur le segment du milieu. Il est possible d’appliquer cette règle de nouveau sur les 4 segments obtenus, et ainsi de suite.
Exercice 2
Calculez la longueur de la courbe.
16.7. Pyramide fractale¶
La règle de construction de cette courbe est similaire à la courbe de Koch. Le segment de départ est coupé en 3 est un carré est dessiné sur le segment du milieu.
Exercice 3
Calculez la longueur de la courbe.
16.8. Triangle de Sierpinski¶
Exercice 4
Augmentez le degré de la courbe.