CODEWITHSUNDEEP
python
Patrick J.
Patrick J.

Reputation: 19

What extra logic does this need to exceed a depth of three in this Sierpinski triangle?

Right now I'm trying to use this very simple loop to draw a Sierpinski triangle in Python, but with the current loop I cannot exceed a depth of 3. 

import turtle as t

def sier(n, length):

    if (n == 0):

        return

    for i in range(3):

        sier(n - 1, length / 2)

        t.fd(length)

        t.lt(120)

sier(3, 100)

t.exitonclick()

What logic do I need to add to the loop for it to be able to be infinitely recursive?

Upvotes: 1

Views: 107

Answers (2)

jsbueno
jsbueno

Reputation: 110561

The idea of recursive function is seldon that the deepmost call "do nothing". Instead, the deep-most call is the one performing the one basic step, reduced to the bare minimum and simple act - and then return. The combination of this bare minimum act with the complexity added on the calls further up on the stack is what "do the magic".

So, usually, in trivial text-book examples of recursive function, the "bare minimal" is to return a "1", which is then added-to or multiplied-by other results in the structure.

In the case of line-art fractals like Sierpinsk or Koch curves, the bare minimal is to actually draw the minimal desired image element. In your code, you are calling t.fd in the upper-calls on the stack, and drawing nothing on the deep-most call - that is where your code is wrong.

Thus, talking code:

from turtle import Turtle, tracer

def triangle(n, length):
    t.pendown()
    t.begin_fill()
    for i in range(3):
        t.fd(length)
        t.left(120)
    t.end_fill()
    t.penup()

def sierpinski(n, length):
    if n == 0 or length <= 1:
        triangle(n, length)
    else:
        # draw bottom-left triangle
        sierpinski(n - 1, length / 2)
        # position turtle at corner of bottom.left triangle:
        t.fd(length / 2)
        sierpinski(n - 1, length / 2)
        # Position turtle at the bottom-left corner
        # of the top the 3 triangle-set comprising this level:
        t.left(120)
        t.fd(length / 2)
        t.left(240)
        #draw top-most triangle
        sierpinski(n - 1, length / 2)
        # reposition turtle at lower-left corner:
        t.left(240)
        t.fd(length / 2)
        t.left(120)


if __name__ == "__main__":
    t = Turtle()
    # shut down all animation:
    tracer(100,0)
    t.hideturtle()
    t.penup()
    sierpinski(4, 400)
    t.screen.exitonclick()

As turtle is intended to be a didactic module, it is by default slow, even setting the speed to "0", not to show animations. To really speed thing up, add these lines to the begging of the code:

from turtle import tracer
tracer(100,0)

to effectively disable all animation - otherwise, depth level 4 is slow, and 5 is unfeasible.

Upvotes: 1

degenTy
degenTy

Reputation: 360

You don't need the for loop as part of your recursive call. The call to sier is what makes the function loop. And you have your recursive termination case with the n==0 check to end the loop.

Example

>>> def sier(n, length):
...     if(n==0):
...         return
...     print("n:" + str(n) + ", length: " + str(length))
...     sier(n-1, length/2)
... 
>>> sier(10,100)
n:10, length: 100
n:9, length: 50.0
n:8, length: 25.0
n:7, length: 12.5
n:6, length: 6.25
n:5, length: 3.125
n:4, length: 1.5625
n:3, length: 0.78125
n:2, length: 0.390625
n:1, length: 0.1953125
>>> sier(3,100)
n:3, length: 100
n:2, length: 50.0
n:1, length: 25.0

Upvotes: 0

Related Questions