HomeTortue graphiqueGPanelRobotique WebTigerPython
 Python - Online
rekursionen
Deutsch   English   Français   

15. RÉCURRENCES

 

 

TU APPRENDS ICI...

 

la récurrence est une méthode de résolution dans laquelle un problème est ramené à un problème similaire mais quelque peu simplifié. Une fonction est dite récurrente si elle s'appelle elle-même. Pour empêcher une fonction récurrente de s'exécuter indéfiniment, elle doit posséder une condition d'arrêt. Considère ce chapitre comme un matériel supplémentaire et apprécie les belles images créées avec des récurrences.

 

 

EXEMPLES

 

Le principe de la récurrence peut être expliqué clairement à l'aide de l'exemple du dessin d'un escalier : Un escalier de 6 marches est composé d'une marche et d'un escalier de 5 marches, un escalier de 5 marches est récurrent à une marche et un escalier de 4 marches (etc.). Dans la fonction staircase(n), la même fonction staircase(n - 1) est appelée à chaque étape. Lorsque la condition d'arrêt n = 0 est remplie, le programme s'arrête avec return.

  

Programme:    

from gturtle import *

def step():
    forward(20)
    right(90)
    forward(20)
    left(90)

def staircase(n):
    if n == 0:
        return
    step()
    staircase(n-1)  

makeTurtle() 
staircase(6)
► Copy to clipboard


 

Dessiner un arbre binaire peut être réduit à une figure de base simple.

Un arbre binaire avec une longueur de tronc s est composé d'un tronc et d'un arbre gauche et droit avec une longueur de tronc s/2. La récurrence s'arrête pour une longueur de tronc < 8.

  

Programme:    

from gturtle import *

def tree(s):
    if s < 8:
        return
    forward(s)
    left(45)
    tree(s/2)
    right(90)
    tree(s/2)
    left(45)
    back(s)

makeTurtle()
setY(-100)
tree(128)
► Copy to clipboard

Remarque : le back(s) est important, car après avoir dessiné l'arbre (ou une partie de l'arbre), la tortue doit revenir à son état initial.

 

 

RETENIR...
 

La récurrence est une méthode de résolution importante dans laquelle un problème est réduit au même problème de manière simplifiée et est résolu dans un cas particulièrement simple (dans le cas de la condition d'arrêt). Les méthodes de résolution récurrentes sont élégantes, mais souvent difficiles à comprendre.

 

 

AUTRES RÉCURRENCES CONNUES
 

Sirpinsky Fractale     

Flower Fractale    

Peano Fractale     

Tree Fractale     

Koch Fractale     

 

 

À FAIRE PAR TOI-MÊME


  1.

Réfléchis à la manière dont tu dois modifier le programme qui dessine l'arbre binaire (exemple 2) pour obtenir l'arbre adjacent.

 

  

  2.

Complète le code du programme afin qu'un flocon soit dessiné. Commence avec le cadre suivant :

def figure(s):
    
    for i in range(6):
        forward(s)
        figure(s/3)
        back(s)
        right(60)