►Fundamentals I – Accelerated
▼Labs
►Lab 7 Generative Recursion
On this page:
Generative Recursion (20 minutes)
Fractals (80 minutes)
6.7
    ← prev  up  next → 

Lab 7 Generative Recursion

home work!

Purpose: This lab is an introduction to generative recursion.

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

Generative Recursion (20 minutes)

Sample Problem Design the function power, which computes the first number to the power of the second number using multiplication.

; power : Nat Nat -> Nat
; Compute n^m using '*'
(check-expect (power 2 5) 32)
(check-expect (power 3 2) 9)
(define (power n m)
  (cond [(zero? m) 1]
        [else (* n (power n (sub1 m)))]))

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:

  • X2Y = (XY)*(XY)

  • X2Y+1 = X*(X2Y)

; power-fast : Nat Nat -> Nat
; Compute n^m using rules of repeated squaring
(check-expect (power-fast 2 5) 32)
(check-expect (power-fast 3 2) 9)
(define (power-fast n m)
  (cond [(zero? m) 1]
        [(zero? (modulo m 2))
         (local [(define halfpower (power-fast n (/ m 2)))]
           (* halfpower halfpower))]
        [else (* n (power-fast n (sub1 m)))]))

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
(check-expect (digit->string 5) "5")
(check-expect (digit->string 0) "0")
(define (digit->string n)
  (string (integer->char (+ 48 n))))

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? 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 (80 minutes)

For the next part of the lab you will design functions to draw (and iterate) some interesting fractal designs. A fractal is just a pattern that contains a smaller version of itself. Here are some examples:

One fractal design we can make is called the Dragon Fractal. 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 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-dirs, that rotates all the Dirs in a [List-of Dir] counter-clockwise. What loop function can you use?

Exercise 4 Design the function move-posn that takes two Numbers, x and y, a Dir d, and a Number amnt and returns a Posn that is the result of moving the given x and y in the given direction, by the given amount.

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

Exercise 6 Put your functions together using big-bang to create an interactive line-drawing program. Use the arrow keys to create a path (a [List-of Dir]). You can hit r to rotate all the points to the left.

Exercise 7 Now we need to generate our fractal! Design a function jurassic which takes a [List-of Dir] and a Number (the iterations left to be done) and implements the algorithm as follows:

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

  • Otherwise return a new modified list as follows:

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

    • Reverse the rotated list.

    • Append the new reversed/rotated list on 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 8 Now we can remove (or comment out) our old big-bang code and replace it with an interactive fractal drawing program! Your World should be a Number (the number of iterations to draw) and you should be able to hit the up and down arrow keys to increase or decrease the number of iterations of the fractal.

You may notice that after about 11 iterations, your fractal stops showing up properly. This is fine, it’s just that your fractal is too big to draw anymore. Below are some examples of what the fractal will look like after several iterations:

Number of iterations

Image of fractal

0

2

4

6

    ← prev  up  next →