1 ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 ;; about the language level of this file in a form that our tools can easily process.
3 #reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname |26.3|) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp")))))
4 ;gcd-structural : N[>=1] N[>=1] -> N
5 ;Determine the greatest common divisor between n and m by testing every number between 1 and (min m n), starting at (min m n).
6 
7 ;check-divisible : N[>=1] -> N
8 ;Given x, check to see if m and n are divisible by x.  m and n are passed into check-divisible by a binding variable outside of check-divisible.
9 
10 #|
11 
12 Examples
13 (gcd-structural 5 10)
14 5
15 (gcd-structural 1 10)
16 1
17 (gcd-structural 1750 150)
18 50
19 
20 |#
21 
22 (define (gcd-structural m n)
23   (local ((define (check-divisible x)
24             (cond
25               [(= x 1) 1]
26               [(and (= (remainder m x) 0)
27                     (= (remainder n x) 0)) x]
28               [else (check-divisible (sub1 x))])))
29     (check-divisible (min m n))))
30 
31 ;gcd-generative : N N -> N
32 ;Uses generative recursion to determine the greatest common divisor between m and n. Reduces the main problem of finding the gcd of larger and smaller into the simpler problem of finding the gcd of smaller and the remainder of the larger divided by smaller. Only one new problem is generated each recursion, resulting in no net increase in problems.  The solution to the new problem is the same as the old problem.  No problems need to be combined. A trivially solvable problem is the case (gcd-generative x 0) where x is a number.  In this case, the answer is simply x.
33 
34 ;Termination Argument: gcd-algol takes in larger and smaller and produces a new problem with the two new parameters smaller and (remainder larger smaller).  Clearly, smaller is less than larger, and (remainder larger smaller) must necessarily be less than smaller.  Hence, each new recursion produces numbers that tend to get smaller.  At some point, (remainder larger smaller) must necessarily equal 0 for any given value since the recursion is strictly monotonic decreasing.  At this point the generative recursion answers the trivially solvable problem.
35 
36 ;Examples
37 ;(gcd-generative 10 20)
38 ;10
39 
40 ;gcd-algol : N N -> N
41 ;Given larger and smaller, finds the greatest common divisor.
42 
43 (define (gcd-generative m n)
44   (local ((define (gcd-algol larger smaller)
45             (cond
46               [(= smaller 0) larger]
47               [else (gcd-algol smaller (remainder larger smaller))])))
48     (gcd-algol (max m n) (min m n))))
49