4 Tuesday Afternoon: Generative Recursion

Related material in How to Design Programs: part v

4.1 Goal

to study

(1) a new form of program organization and

(2) a design recipe for creating such programs

4.2 Example: Generating Balloons

Problem:

Develop a function that creates a blue background with n randomly distributed balloons for an animated scene.

Or,

Develop a function that creates a blue background with n randomly distributed falling stars for the “Collect Star Thalers” fairy-tale game.

We clearly need n distinct Posns:

;; Number  →  PosnList
;; create a list of n distinct Posns 
(define (background n)
  (cond
    [(zero? n) empty]
    [else (add-distinct-posn (background (sub1 n)))]))

;; PosnList  →  PosnList
;; create and add a Posn to l that is distinct from all
;; Posns on there
(define (add-distinct-posn l)
  (local ((define new-x (random WIDTH))
          (define new-y (random HEIGHT))
          (define new-p (make-posn new-x new-y)))
    (cond
      [(boolean? (member new-p l)) (cons new-p l)]
      [else (add-distinct-posn l)])))

What’s wrong with the underlined recursion?

4.3 Example: Sorting Numbers

Problem:

Sort a list of numbers via a divide-and-conquer strategy. That is, pick a pivot element; extract all those items that are smaller than the pivot and sort those; extract all those items that are larger than the pivot and sort those; and finally juxtapose the two sequences to get a sorted sequence.

;; NumberList  →  NumberList
;; to create a sorted list of numbers from alon
(define (kwik-sort alon)
  (cond
    [(sorted? alon) alon]
    [else (append
	    (kwik-sort (smaller (first alon) (rest alon)))
	    (list (first alon))
	    (kwik-sort (larger (first alon) (rest alon))))]))

;; NumberList  →  NumberList
;; extract all items from l that are smaller than pivot
(define (smaller pivot l)
  (cond
    [(empty? l) empty]
    [else (cond
	    [(< (first l) pivot) (cons (first l) (smaller pivot (rest l)))]
	    [else (smaller pivot (rest l))])]))

;; NumberList  →  NumberList
;; extract all items from l that are larger than pivot
(define (larger pivot l)
  (cond
    [(empty? l) empty]
    [else (cond
	    [(> (first l) pivot) (cons (first l) (larger pivot (rest l)))]
	    [else (larger pivot (rest l))])]))

;; test: 
(equal? (kwik-sort (list 3 8 1 2 9 7)) (list 1 2 3 7 8 9))

What’s wrong with the underlined recursions?

4.4 Example: Fractals

Problem:

Design a program that draws these triangles:

;; Posn Posn Posn  →  true
;; to draw a Sierpinski triangle at a, b, and c,
(define (sierpinski a b c)
  (cond
    [(too-small? a b c) #t]
    [else 
      (local ((define a-b (mid-point a b))
	      (define b-c (mid-point b c))
	      (define c-a (mid-point a c)))
	(and
	  (draw-triangle a b c)	    
	  (sierpinski a a-b c-a)
	  (sierpinski b a-b b-c)
	  (sierpinski c c-a b-c)))]))

;; Posn Posn  →  Posn
;; to compute the mid-point between a-posn and b-posn
(define (mid-point a-posn b-posn)
  (make-posn (mid (posn-x a-posn) (posn-x b-posn))
             (mid (posn-y a-posn) (posn-y b-posn))))

;; Number Number  →  Number
;; to compute the average of x and y
(define (mid x y) (/ (+ x y) 2))

4.5 Generative Recursion: The Design Recipe

The design recipe uses the basic six steps.
Question: if the ideas are ad hoc, how can we design a template systematically?
All functions based on generative recursion use the same basic outline. To find it, ask these four questions:
1. what are trivial solutions?
2. how do you generate new, slightly different problems?
3. how do you use the solutions to these problems?
4. how do you now to get the solution for the original problem?
We need a seventh step. Does it terminate?