►Fundamentals I
▼Labs
►Lab 9 Generative Recursion
On this page:
The Dragon Fractal
Generative Recursion
Readable Numbers
If you’re done early...
    ← prev  up  next → 

Lab 9 Generative Recursion

home work!

Purpose This lab is an introduction to generative recursion.

The Dragon Fractal

For the next 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 a Symbol and is one of:
; - '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 Direction, 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 (say 5). You can use add-line to create the lines. You’ll need a bit of 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))

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 ’(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. Recurse on the new list, and with one less iter.

Exercise 5 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.

image

Generative Recursion

You may have read about generative recursion in the book, but if not, go take a look. Generative recursion is a type of programming which rearranges a problem into a series of smaller subproblems, which are then combined to find a solution. These sub-problems are often (but not always) the same kind of problem as the original, which means you can use recursion!

Exercise 6 Design the function power, which computes the first number to the power of the second number using multiplication (do NOT use expt because it makes the problem trivial).

; power : Nat Nat -> Nat
; Compute n^m using '*'
(define (power n m) ...)
 
(check-expect (power 2 5) 32)

Exercise 7 Now, design a new function, power-fast which uses a method of repeated squaring to calculate the answer to the same problem. The basic rules of repeated squaring are: 1. x^(2y+1)=(x^(2y))*x 2. x^(2y)=(x^y)*(x^y)

You can test if your new function is faster using Racket’s time function, which takes an expression and tells you how long it took to complete that expression.
(define res1 (time (power 2 100000)))
(define res2 (time (power-fast 2 100000)))
If you don’t notice a VERY LARGE difference in the time it takes to run these two functions, you may be computing something twice when you don’t need to. Remember that you can use local to store values that you need to use more than once in your function.

Readable Numbers

Here’s a bit of code that turns a single digit number into a single character string.
; digit->string: Nat -> String
; Turn a single digit number into a single char string
(define (digit->string n)
  (string (integer->char (+ 48 n))))
 
(check-expect (digit->string 5) "5")
(check-expect (digit->string 0) "0")

Exercise 8 Design the function num->string that returns the string representation of a natural number. What is the base case for this function? What can we do to get from one digit to the next?

Here are some tests for num->string:
(check-expect (num->string 0) "0")
(check-expect (num->string 5) "5")
(check-expect (num->string 1234) "1234")
(check-expect (num->string 4321) "4321")

image

If you’re done early...

Exercise 9 Try making the Koch Snowflake fractal. This one’s a bit more of a challenge!

    ← prev  up  next →