►Fundamentals 1
▼Labs
►Lab 10 Generative Recursion
On this page:
Generative Recursion
Fractals
7.5
    ← prev  up  next → 

Lab 10 Generative Recursion

lab!

Purpose: This lab is an introduction to generative recursion.

Textbook References: Chapter 25: Non-Standard Recursion, Chapter 26: Designing Algorithms

Generative Recursion

Sample Problem Design the function power, which raises its first argument to the power of its second argument using multiplication; the exponent must be a natural number.

; Number Nat -> Number
; x^n
(define (power x n)
  (if (zero? n) 1                 ; x^0 = 1
      (* x (power x (sub1 n)))))  ; x^n = x * x^(n-1)
 
(check-expect (power 2 5) 32)
(check-expect (power 3 2) 9)

Sample Problem Design power/fast which uses a method of repeated squaring to calculate the answer to the same problem. The basic rules of repeated squaring are:

  • x2n = (x2)n

  • x2n+1 = x*(x2)n

; Number Nat -> Number
; x^n
; Termination: n shrinks on each recursion
(define (power/fast x n)
  (if (even? n)
      (if (zero? n) 1
          (power/fast (* x x) (/ n 2)))           ; n even & non-zero
      (* x (power/fast (* x x) (/ (sub1 n) 2))))) ; n odd
 
; Question: why is n always a whole number on the two recursive calls?
 
(check-expect (power/fast 2 5) 32)
(check-expect (power/fast 3 2) 9)

Here’s a bit of code that turns a single-digit number into a single-character string:
; A Digit is a natural number in the range [0,9].
 
; Digit -> 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")

(It takes advantage of the ASCII encoding of characters.)

Exercise 1 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? How do we know your function’s recursions will always terminate in a base case?

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")

Fractals

For the next part of the lab you will design functions to draw (and iterate) some interesting fractal designs. A fractal is a pattern that is "self-similar" — it contains smaller versions of itself. Here are some examples:

One fractal design we can make is called the Dragon Curve. This was used on the headings of chapters in the book Jurassic Park. We’ll start off by building a simple line-drawing program. Then we’ll combine pieces into the fractal’s (generative) recursion.

; A Dir (Direction) is a Symbol and is one of:
; - 'left
; - 'right
; - 'up
; - 'down
; 
; Path = [ListOf Dir]
; A "path" is a sequence of directions.
; 
; Pt = (make-posn Number Number)
; A "point" is a 2D point on a plane.

Exercise 2 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 in each case?

Exercise 3 Design the function, rotate-path, that rotates each Dir in a Path 90 degrees counter-clockwise. (Which will rotate the entire path 90 degrees counter-clockwise.)

Exercise 4 Design the function move-pt that takes a Pt p, a Dir d, and a Number len and returns a Pt that is the result of moving p in direction d for the given distance len. Be careful to make your coordinate shifts respect the upside-down conventions of the screen coordinate system — shifting a point up means decreasing its y coordinate. (But you knew that, of course.)

Exercise 5 Design the function path+scene that draws a path onto a scene, starting at some given point; each segment of the path is of some fixed length, and extends in the direction given for that segment of the path. The path can be any color you like.
; Path Pt Number Image -> Image
; Draw lines following the path's directions starting at the
; given point, onto the given scene; each segment of the path
; is drawn with the given length.
(define (path+scene path start-pos seg-len scene) ...)

Hints: Use structural recursion here. The move-pt function may be of some utility for you. You can use scene+line to create the lines (look it up in the help desk). You’ll need to use the accumulator pattern for your code.

Here’s some scaffolding to test your functions: an interactive big-bang system that uses the arrow keys to create a path, and the r key to rotate the path. The path is rendered with each segment of length 10.
(define WIDTH  1024)
(define HEIGHT 1024)
(define BG (empty-scene WIDTH HEIGHT))
 
; Path Number -> Image
(define (path->scene path seg-len)
  (path+scene path                                 ; Paint the path
              (make-posn (/ WIDTH 2) (/ HEIGHT 2)) ; starting at the center
              20
              BG))                                 ; of an empty background.
 
(define (key-handler w ke)
  (cond [(key=? ke "up")    (append w '(up))]
        [(key=? ke "down")  (append w '(down))]
        [(key=? ke "left")  (append w '(left))]
        [(key=? ke "right") (append w '(right))]
        [(key=? ke "r")     (rotate-path w)]
        [else w]))
 
; A World is a Path
(big-bang '()
          [to-draw (lambda (w) (path->scene w 10))] ; segment length 10
          [on-key key-handler])

Exercise 6 Now we need to generate our fractal! Design a function jurassic which takes a Path and a Natural (the number of iterations left to be done) and implements the following fractal-generating algorithm:

  • If the number is 0, return the given list as is.

  • Otherwise return a new modified list as follows:

    • Rotate the current path 90 degrees counter-clockwise,

    • then reverse this rotated path.

    • Append the new reversed/rotated list onto the end of the old list.

    • Recursively call jurassic on this new list with one less iteration.

(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))

Exercise 7 Now we can remove (or comment out) our old big-bang code and replace it with an interactive fractal-drawing program! Your world-state is now a natural number that describes the depth of the recursion (the number of iterations you want jurassic to use to compute your dragon-curve path); you should be able to hit the up and down arrow keys to increase or decrease this value. (However, don’t let the player drop this value below zero — that is not a natural number and doesn’t make sense.) Your curve will get larger and larger as you increase the recursion depth. To account for this, shrink the segment length as the curve grows in size: paint the curve with a segment-length set to the width of the display divided by 1.5d, where d is the depth of the recursion — that is, the current world state of your big-bang system. (Or you could just fix it at 2 pixels and let the curve grow as you increase the recursion depth.)

You will notice that well before you hit 20 iterations, your dragon curve will exceed the resolution of your display. Here are some examples of of the curves you’ll get:

Number of iterations

Image of fractal

0

2

4

6

    ← prev  up  next →