Design recipe Derivative example, GCD example, Ackerman's function example
Today we look at some examples of generative recursion that illustrate important aspects of what we need to think about.
In class, we concluded that we now have a new methodology for use with generative recursion. If a function is generative recursive, we modify our design recipe with the following changes:
(define (f args ...)
(cond [(trivial? args ...)
(solve-trivial args ...)]
[else
(combine (f (generate-subproblem1 args ...) ...)
...
(f (generate-subproblemn args ...) ...))]))
One common mathematical problem is to find the area under some function f between some points xlo and xhi. I.e., given f, its integral is the area of the shape between f's curve and the x-axis.
Given f, the area can be calculated:
| area under f from xlo to the x-midpoint | |
| + | area under f from the x-midpoint to xhi |
| = | area under f from xlo to xhi |
To do: Develop the program
; integrate : (num -> num) num num num -> num
(define (integrate f xlo xhi threshold) ...)
that follows the above idea.
Follow our methodology for developing generative recursive programs.
Don't forget to make and use a good set of examples, although you might
have difficulty calculating the result values of examples.
GCD (Greatest Common Divisor) is a common mathematical problem.
Given two positive natural numbers, what is the largest (positive) natural number which is a divisor for both inputs?The benefit for us is that GCD is a good example to see the tradeoffs between structural recursion and generative recursion.
A structurally recursive version is rather straightforward -- count down until you find a numbers that divides both inputs. Q: What should we count down from? Q: Why does this find the greatest common divisor? Here's the code:
;; gcd-structural : N[>=1] N[>=1] -> N[>=1]
;; find the greatest common divisor of the two inputs
;; Examples:
;; (gcd-structural 6 25) = 1
;; (gcd-structural 18 24) = 6
;; based on structural recursion
(define (gcd-structural n m)
(local (; divides? : N N -> boolean
; returns whether i divides n with zero remainder
(define (divides? n i)
(zero? (remainder n i)))
; first-divisor-<= : N[>=1] -> N[>=1]
; find the greatest common divisor of m and n
; which is less than or equal to i
(define (first-divisor-<= i)
(cond
[(= i 1) 1]
[else (cond
[(and (divides? n i) (divides? m i)) i]
[else (first-divisor-<= (sub1 i))])])))
(first-divisor-<= (min m n))))
A generative recursive version devised by Euclid requires a "Eureka!". To do: Look at the following and figure out what it does. Q: Why does this work?
;; gcd-generative : N[>=1] N[>=1] -> N[>=1]
;; find the greatest common divisor of the two inputs
;; Examples:
;; (gcd-generative 6 25) = 1
;; (gcd-generative 18 24) = 6
;; based on generative recursion
(define (gcd-generative n m)
(local (; euclid-gcd : N N -> N
; find the greatest common divisor of the two inputs
; assume that larger >= smaller
(define (euclid-gcd larger smaller)
(cond
[(= smaller 0) larger]
[else (euclid-gcd smaller (remainder larger smaller))])))
(euclid-gcd (max m n) (min m n))))
The advantage of the structural version is obvious -- it is easier to understand. To do: To see the advantage of the generative version, guesstimate how many recursive calls each version takes to find the answer. Try out your idea on some more examples, including some larger ones, such as
(gcd-structural 101135853 45014640)
(gcd-generative 101135853 45014640)
Here's the definition of a strange numerical function on natural numbers, called Ackerman's Function:
A(m,n) = 0, if n=0
= 2n, if n>0 and m=0
= 2, if n=1 and m>0
= A(m-1,A(m,n-1)), if n>1 and m>0
Note that this definition is not structurally recursive.
(In fact, it cannot be defined in a structurally recursive manner.)
To do:
This function isn't very useful, except as a function that grows faster than probably any one you've seen before. (In technical jargon, the function is not primitive recursive.)