arvb.net

Generative Recursion

4 min read

Generative Recursion

Generative recursion differs from previous methods, known as “structural recursion”. Structural recursion works by always taking a piece of data as an argument. One can think of a function operating on a list as recursive, as each successive call uses (first lox) as an argument and recurses via (rest lox).

This taking a piece of the whole (another example is looking at each node in an arbitrary arity tree) defines the structure of the recursion. In contrast, with generative recursion we create new data with each recursive call to operate on.

Worked example

(define CUTOFF 2)
 
;; Number -> Image
;; produce a Sierpinski Triangle of the given size
(check-expect (stri CUTOFF) (triangle CUTOFF "outline" "red"))
(check-expect (stri (* CUTOFF 2))
              (overlay (triangle (* 2 CUTOFF) "outline" "red")
                       (local [(define sub (triangle CUTOFF "outline" "red"))]
                         (above sub
                                (beside sub sub)))))
 
 
(define (stri s)
  (cond [(<= s CUTOFF) 
         (triangle s "outline" "red")]
        [else
         (overlay (triangle s "outline" "red")
                  (local [(define sub (stri (/ s 2)))]
                    (above sub
                           (beside sub sub)))]))

Note: the call to overlay is not necessary. However, given the way the domain analysis was completed it was included. The line may safely be removed.

Recipe

This recipe is used to create a generative recursion function. As an example, the code will create a Sierpinski triangle.

Domain analysis

A Sierpinski triangle is create by first forming a triangle of side length s. Then, within that triangle, three triangles are then drawn with side length s/2. Then recurse until triangles are too smal.

Following the HtDF recipe, we can begin in the same way as any other template:

  • Type comment (Number -> Image)
  • Interpretation (produce Sierpinski Triange)
  • A stub ((define (stri s (square 0 "solid" "white")))
  • Check-expects

Note that for generative recursive functions, the base case is the stopping scenario. Thus,in the case, it is when the triangles are too small.

Purpose, Signature, Stub, Tests

(define CUTOFF 2)
 
;; Number -> Image
;; produce a Sierpinski Triangle of the given size
(check-expect (stri CUTOFF) (triangle CUTOFF "outline" "red"))
 
(define (stri s) (triangle 0 "solid" "white"))

Once the base case is established, we can use the next smallest case after the base case - in this case, a triangle of size CUTOFF * 2. Using the next smallest case after the base or trivial case can be useful to truly grasp the structure of the generative function.

(check-expect (stri (* CUTOFF 2))
              (overlay (triangle (* 2 CUTOFF) "outline" "red")
                       (local [(define sub (triangle CUTOFF "outline" "red"))]
                         (above sub
                                (beside sub sub)))))

In the code above, a starting triangle of size CUTOFF * 2 is overlaid over the other triangles. The use of local here is to avoid recomputation, given that each of the inner triangles is defined in the same way.

Template

Once the above has been completed, we can use the template for a generative recursion function:

(define (genrec-fn d)
  (cond [(trivial? d) (trivial-answer d)]
        [else
         (... d 
              (genrec-fn (next-problem d)))]))

From here on, we end up with the following:

(define (stri s)
  (cond [(trivial? s) (trivial-answer s)]
        [else
         (... s 
              (stri (next-problem s)))]))

In this template, the trivial? question refers to the basecase. For the on going example, we mean to say when the size of the triangle reaches CUTOFF:

(define (stri s)
  (cond [(<= s CUTOFF) 
         (triangle s "outline" "red")]
        [else
         (overlay (triangle s "outline" "red")
                  (local [(define sub (stri (/ s 2)))]
                    (above sub
                           (beside sub sub))))]))

Termination Arguments

For generative functions we will always need 3-part termination arguments.

Collatz conjecture

The Collatz conjecture (also known as hailstones if the length of the sequence is plotted) is a form of generative recursion. Given a number n a collatz sequence function will generate more and more numbers until a base case is reached:

;; Integer[>=1] -> (listof Integer[>=1])
;; produce a hailstone sequence for n
 
(define (hailstone n)
  (cond [(= n 1) (list 1)]
        [else
         (cons n
	         (if (even? n)
		         (hailstones (/ n 2))
		         (hailstones (add1 (* n 3)))))]))

Three part termination arguments

Base case

The base case for a generative case can be seen directly in the function definition. For hailstones, as an example, we can see it as the first cond:

(cond [(= n 1) (list 1)]

Reduction step

The reduction step is the one which moves the function further towards the base case. Thus, in hailstone we have:

If (even? n):
	(hailstones (/ n 2))
if (odd? n):
	(+ 1 (* n 3))
Repeated reduction to reach base

In other generative scenarios, the argument that that the function will approach the base case can be straight-forward: look at the reduction step.

The case of hailstones is particular because we still don’t understand why this particular sequence always reduces to 0. As in, there is no mathematical theory for it.

Graph View

Backlinks