On this page:
Generative Recursion
Readable Numbers
The Dragon Fractal
Accumulators
If you’re done early...
If you’re STILL done early...

Lab 9h Generative Recursion and Accumulators

home work!

Purpose This lab is an introduction to generative recursion and accumulator style functions.

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 1 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 2 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 3 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")

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 4 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 5 Design the function, rotate-dirs, that rotates all the Dirs in a [List-of Dir] counter-clockwise. What loop function can you use?

Exercise 6 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 7 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 8 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

Accumulators

You’ve seen one use of accumulators in class, namely use of the list of "visited" nodes when implementing path?. An accumulator is an argument that summarizes the collected knowledge seen so far in a recursive function. For example, the implementation of list length in both regular and accumulator style is shown below.

; length.reg : [List-of X] -> Number
(define (length.reg lst)
  (if (empty? lst) 0
      (add1 (length.reg (rest lst)))))
(check-expect (length.reg (list 1 2 3 4 5)) 5)
 
; length.acc : [List-of X] -> Number
(define (length.acc lst)
  (local [(define (loop lst acc)
            (if (empty? lst) acc
                (loop (rest lst) (add1 acc))))]
    (loop lst 0)))
(check-expect (length.acc (list 1 2 3 4 5)) 5)

Consider the function sum that sums all the elements in a [List-of Number].

Exercise 9 Quickly write a "follow the template" recursive function definition of sum.

Exercise 10 Now write a second definition of sum using DrRacket’s foldr loop function(s).

Exercise 11 Transform your recursive definition of sum into an accumulator style function. You will need a local helper with an extra argument to "accumulate" the sum-so-far.

Now let’s do the same thing for product.

Exercise 12 Quickly write a "follow the template" recursive function definition of product.

Exercise 13 Now write a second definition of product using DrRacket’s foldr loop function(s).

Exercise 14 Transform your recursive definition of product into an accumulator style function. You will need a local helper with an extra argument to "accumulate" the product-so-far.

Exercise 15 Design a function operate-through which takes a [List-of X] and an [X X -> X] function. This function should produce a [List-of X] where the first element is the same as in the original list, the second element is the operation applied to the first element and the second element of the original list, and so on. In other words, if you pass in the list (list x1 x2 x3 x4) and the operation op you should get back the list (list x1 (op x1 x2) (op (op x1 x2) x3) (op (op (op x1 x2) x3) x4)). Here are some tests:

(check-expect (operate-through (list 1 2 3 4) +)
              (list 1 3 6 10))
(check-expect (operate-through (list true false true) and)
              (list true false false))
(check-expect (operate-through (list "we" "are" "groot") string-append)
              (list "we" "weare" "wearegroot"))

image

If you’re done early...

Exercise 16 When drawing the directions in your draw-dirs function, try accumulating and changing the current color or modifying the size of the lines to create interesting drawings.

If you’re STILL done early...

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