Lab 11 Generative and Accumulator Recursion

Purpose: When structural recursion just isn’t enough...

The Sierpinski Triangle – Structural recursion

Sample Problem The Sierpinski triangle is a fairly simple fractal. It consists of three “copies of itself”, scaled down to half their original size, and stacked next to each other:

Design a function sierpinski that takes a Natural and draws the appropriate detail-level of the Sierpinski triangle. Use structural recursion on your input. To avoid repeatedly computing the same image, use local to define the next-smaller level of detail.

(define (sierpinski n)

(cond

[(zero? n) (triangle 150 "solid" "red")]

[else

(local ((define sier-n-1 (scale 0.5 (sierpinski (sub1 n)))))

(above sier-n-1 (beside sier-n-1 sier-n-1)))]))

Try to work through either or both of the following fractals.

The Dragon Fractal – Generative recursion

For this part of the lab you will design functions to draw (and iterate) an interesting fractal design called the Dragon. This was used on the headings of chapters in the book Jurassic Park (if anyone is old enough to remember that...). We’ll start off by building a simple line drawing program. Then we’ll combine pieces into the fractal’s (generative) recursion.

; A Direction (Dir) is one of the following Symbols:

; - 'left

; - 'right

; - 'up

; - 'down

Exercise 1 Design the function rotate-dir, that rotates a given Dir 90 degrees counter-clockwise (rotate to the left). What are the four cases of Dir and what should you return?

Exercise 2 Design the function rotate-dirs, that rotates all the Dirs in a [List-of Dir] counter-clockwise. What loop function can you use?

Exercise 3 Design the function move-posn, that returns a Posn that is the result of moving the given x and y in the given Dir, by the given amount.

; move-posn : Number Number Dir Number -> Posn

; Move the x and y in the given direction by the given amount

(define (move-posn x y dir amt) ...)

Exercise 4 Design the function draw-dirs, that draws lines given a list of directions (in order) starting at the given x and y onto the given image.

Hint: Use structural recursion here, and choose some constant amount for move-posn (e.g. 5). You can use add-line to create the lines. You’ll need an accumulator too.

; draw-dirs : [List-of Dir] Number Number Image -> Image

; Draw lines following the given directions starting at (x,y) into

;   the given Image (any color you choose).

Here’s some interactive stuff to test your functions... use the arrow keys to create a path (a [List-of Dir]). You can hit r to rotate all the points to the left.

; Screen Size...

(define W 400)

(define H 400)

; Draw wrapper

(define (draw w)

(local ((define lst (reverse w)))

(draw-dirs lst (/ W 2) (/ H 2) (empty-scene W H))))

; Key Handler

(define (key w ke)

(cond [(key=? ke "up") (cons 'up w)]

[(key=? ke "down") (cons 'down w)]

[(key=? ke "left") (cons 'left w)]

[(key=? ke "right") (cons 'right w)]

[(key=? ke "r") (rotate-dirs w)]

[else w]))

(big-bang '()

(to-draw draw)

(on-key key))

Exercise 5 Now we need to generate our fractal! The algorithm takes a [List-of Dir] and a Number that is the iterations left to be done. To start the algorithm off we will pass it the list (list 'down), and the number of iterations we want. It goes like this:

• If iter is 0, then leave the list alone.

• Otherwise, return a new list modified as follows:

  1. Rotate all the Dirs from the old list counter-clockwise.

  2. Reverse the rotated list.

  3. Append the new reversed/rotated list on the end of the old list.

  4. Recur on the new list, and with one less iter.

Design a function jurassic, which implements the algorithm above. You can use local to define each step separately so that it will be clear that your function follows the specification.

; jurassic: [List-of Dir] Number -> [List-of Dir]

; Compute the next iteration of the Jurassic Fractal, given a [List-of Dir]

;   and the number of iterations left.

(define (jurassic lod iter) ...)

(check-expect (jurassic '(down) 0) '(down))

(check-expect (jurassic '(down) 1) '(down right))

(check-expect (jurassic '(down) 2) '(down right up right))

(check-expect (jurassic '(down) 3) '(down right up right up left up right))

Now we can remove (or comment out) our old big-bang code and replace it with this:

; draw : World -> Image

(define (draw w)

(local [(define lst (jurassic '(down) w))]

(draw-dirs lst (/ W 2) (/ H 2) (empty-scene W H))))

; key : World KeyEvent -> World

(define (key w ke)

(cond [(key=? ke "up") (add1 w)]

[(and (key=? ke "down") (> w 1))

(sub1 w)]

[else w]))

; Let's make this fractal!

(big-bang 0

(to-draw draw)

(on-key key))

Now you can hit the up or down arrows to increase or decrease the number of iterations run.

The Sierpinski Triangle – accumulator recursion

There is another, more flexible way to describe the generation of the Sierpinski triangle. Define three Posns in the plane, P1, P2 and P3: these will be the outermost corners of the triangle. Next, pick as a starting Posn any random point on the plane you want – though it will help if you pick a point inside the triangle, rather than one very far away. To generate the fractal, repeat the following steps:

Exercise 6 Design a function pick-corner that randomly returns one of P1, P2 or P3.

Exercise 7 Design a function move-toward-corner that takes a Posn and generates a point halfway between the given point and a randomly chosen corner.

Exercise 8 Design a function repeat-fun, that takes a function (of type X -> X), an initial value (of type X), and a count (a Natural number), and returns a list of values (base, f(base), f(f(base)), f(f(f(base))), ...) of total length given by the count. For example,

(repeat-fun add1 10 5) ==> (list 10 11 12 13 14)

This function will need an accumulator to help out.

Exercise 9 Design a function draw-dot-onto that takes a Posn and an Image, and draws a small dot at the given point onto the given image.

Exercise 10 Design a function draw-dots that takes a list of Posns and draws them all onto an empty image of a size big enough to hold them all. You can use a list abstraction here, but try to implement it yourself using an accumulator instead.

Exercise 11 Use repeat-fun to generate many (several thousand) points, and draw-dots to draw them all, to generate a new image. After sufficiently many points, it should start to look like the Sierpinski triangle above...no matter where you start your point from.

Before you go...

If you had trouble finishing any of the exercises in the lab or homework, or just feel like you’re struggling with any of the class material, please feel free to come to office hours and talk to a TA or tutor for additional assistance.