rekursionen
Deutsch   English   

15. RECURSIONS

 

 

YOU LEARN HERE...

 

that recursion is a solution method in which a problem is traced back to a similar but somewhat simplified problem. A function is recursive if it calls itself. To prevent a recursive function from calling itself endlessly, it needs a termination condition. Consider this chapter as additional material and enjoy the beautiful pictures that are created with recursions.

 

 

EXAMPLES

 

The principle of recursion can be clearly explained using the example of drawing a staircase: A staircase with 6 steps is composed of a step and a staircase with 5 steps, a staircase with 5 steps is recursed to a step and a staircase with 4 steps (etc.). In the staircase(n) function, the same staircase(n - 1) function is called in each case. If the termination condition n = 0 is fulfilled, the program terminates with return.

  

Programm:    

from gturtle import *

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

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

staircase(6)
► Copy to clipboard


 
Drawing a binary tree can be reduced to a simple basic figure.

A binary tree with trunk length s is a trunk and a left and a right tree with trunk length s /2. The recursion terminates for trunk length < 8.

  

Programm:    

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)

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

Note: the back(s) is important, because after drawing the (partial) tree the turtle must be in the initial state again.

 

 

REMEMBER...
 

Recursion is an important solution method in which a problem is reduced to the same, somewhat simplified problem and solved in a particularly simple case (in the case of recursion termination). Recursive solution methods are elegant, but usually difficult to understand.

 

 

OTHER KNOWN RECURSIONS
 

Sirpinsky Fractal    

Flower Fractal    

Peano Fractal    

Tree Fractal    

Koch Fractal    

 

 

TO SOLVE BY YOURSELF


  1.

Think about how you have to change the program that draws the binary tree (example 2) so that the adjacent tree is created.

  

  2.

Add to the program code so that a flake is drawn. Start from the following framework.

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