Drawing fractal square pattern in Turtle

Question

I'm trying to get the squares to look like:

but instead my code is drawing:

I dont know what I'm doing wrong or if my entire approach is wrong.

Here's the code:

import turtle as tt
def recurse(depth, size):
    if depth==0:
        pass
    else:
        if depth%2==0:
            tt.pencolor('blue')
        else:
            tt.color('orange')
        tt.fd(size)
        tt.left(90)
        tt.fd(size)
        tt.left(90)
        tt.fd(size)
        tt.left(90)
        tt.fd(size)
        tt.left(90)
        tt.fd(size)
        tt.left(90)
        tt.fd(size)
        tt.right(90)
        recurse(depth - 1, size / 3)
        tt.penup()
        tt.bk(size)
        tt.pendown()
        recurse(depth-1, size/3)
        tt.penup()

        tt.left(90)

        tt.back(size)
        tt.right(90)
        tt.back(size)
        tt.pendown()

recurse( 4, 100 )
tt.done()

At the top right, the small squares end up not being the correct size, and over on the left, turtle moves forward way too much.

How can I write the recursion to produce the correct top-left square?

Answer 1

You're not allowd to use goto(), but are you allowed to use stamp()?

My rework of the excellent final solution of @ggorlen (+1) that uses stamping instead of drawing, also without goto:

import turtle

COLORS = ['blue', 'orange']
CURSOR_SIZE = 20

def draw_square(depth, size, shrink_by=3):
    if depth:
        turtle.pencolor(COLORS[depth % len(COLORS)])
        turtle.shapesize(size / CURSOR_SIZE)
        turtle.stamp()

        offset = (size + (shrinkage := size / shrink_by)) * 2**0.5 / 2

        for _ in range(4):
            turtle.right(45)
            turtle.forward(offset)
            turtle.left(45)
            draw_square(depth - 1, shrinkage)
            turtle.right(45)
            turtle.backward(offset)
            turtle.left(135)  # undo right and advance corners

if __name__ == "__main__":
    turtle.shape('square')
    turtle.speed('fastest')
    turtle.fillcolor(turtle.bgcolor())
    turtle.penup()

    draw_square(depth=4, size=100)

    turtle.hideturtle()
    turtle.exitonclick()

Answer 2

Good attempt! I will suggest a slightly different approach, adding x and y coordinates for your square-drawing function and using t.goto(x, y) to reposition the turtle. These coordinates represent the bottom-left corner for where the square should be drawn, and save you the trouble of shuffling the turtle around by hand (although technically possible, it's less clean-cut).

After a square is drawn, the turtle will always be facing rightward and ready to draw the next square, so movement commands are kept to a minimum. All that remains is figuring out the origin coordinates for each corner.

For the top-right corner, it's easy: x + size, y + size. For the top-left corner, it's similar: still y + size, but use x - size_of_smaller_square to offset the x-axis by the correct amount. I've also included the bottom-left and bottom-right corners if you're curious.

import turtle as t 

def draw_square(depth, size, x=0, y=0, shrink_by=3):
    if depth <= 0:
        return

    t.penup()
    t.goto(x, y)
    t.color(("blue", "orange")[depth%2])
    t.pendown()

    for _ in range(4):
        t.forward(size)
        t.left(90)

    smaller_size = size / shrink_by
    draw_square(depth - 1, smaller_size, x + size, y + size)
    draw_square(depth - 1, smaller_size, x - smaller_size, y + size)
    #draw_square(depth - 1, smaller_size, x - smaller_size, y - smaller_size)
    #draw_square(depth - 1, smaller_size, x + size, y - smaller_size)

if __name__ == "__main__":
    t.speed("fastest")
    draw_square(depth=4, size=100)
    t.exitonclick()

---

You mentioned goto is prohibited. You can follow a mechanical strategy that is guaranteed to work: always put the turtle exactly back where it started (same position and direction) at the end of each recursive call. This respects the self-similar structure of recursion. The high-level approach per frame is:

1. draw the current box

2. for each child box:

   3. move the turtle to the correct position and direction to draw the child box
   4. spawn a recursive call
   5. undo all of the moves you just made in step 3

Here's a correct but verbose and sloppy implementation of this strategy:

import turtle as t 

def draw_square(depth, size, shrink_by=3):
    if depth <= 0:
        return

    # draw this box
    t.color(("blue", "orange")[depth%2])
    t.pendown()

    for _ in range(4):
        t.forward(size)
        t.left(90)
    
    t.penup()
    smaller_size = size / shrink_by

    # put the turtle in the top-right facing east and spawn a child
    t.forward(size)
    t.left(90)
    t.forward(size)
    t.right(90)
    draw_square(depth - 1, smaller_size)

    # undo the moves
    t.right(90)
    t.forward(size)
    t.left(90)
    t.backward(size)

    # put the turtle in the top-left facing east and spawn a child
    t.left(90)
    t.forward(size)
    t.right(90)
    t.backward(smaller_size)
    draw_square(depth - 1, smaller_size)

    # undo the moves
    t.forward(smaller_size)
    t.right(90)
    t.forward(size)
    t.left(90)

if __name__ == "__main__":
    t.speed("fastest")
    draw_square(depth=4, size=100)
    t.exitonclick()

While this works, you can see there's some redundant movement that can be eliminated, while still preserving the property that the turtle will always wind up in the same position and direction they started from at the beginning of the recursive function. A rewrite:

import turtle as t 

def draw_square(depth, size, shrink_by=3):
    if depth <= 0:
        return

    # draw this box
    t.color(("blue", "orange")[depth%2])
    t.pendown()

    for _ in range(4):
        t.forward(size)
        t.left(90)
    
    t.penup()
    smaller_size = size / shrink_by

    # top-right
    t.forward(size)
    t.left(90)
    t.forward(size)
    t.right(90)
    draw_square(depth - 1, smaller_size)

    # top-left
    t.backward(size + smaller_size)
    draw_square(depth - 1, smaller_size)

    # undo all of the moves to reset the turtle state
    t.forward(smaller_size)
    t.right(90)
    t.forward(size)
    t.left(90)

if __name__ == "__main__":
    t.speed("fastest")
    draw_square(depth=4, size=100)
    t.exitonclick()

This can be made cleaner by attempting to find patterns and turn them into loops; for example, if you don't mind drawing children while you're in the process of drawing the parent box, you can skip the intermediate movements. This code draws all 4 corners, but you might try adapting it to the top 2 only:

import turtle as t 

def draw_square(depth, size, shrink_by=3):
    if depth <= 0:
        return

    for _ in range(4):
        t.color(("blue", "orange")[depth%2])
        t.forward(size)
        t.right(90)
        draw_square(depth - 1, size / shrink_by)
        t.right(180)

if __name__ == "__main__":
    t.speed("fastest")
    t.pendown()
    draw_square(depth=4, size=100)
    t.exitonclick()