;; MORE GENERATIVE RECURSION

;; Design power (exponent) function that computes x to the nth power 
;; where n is a natural number

;; A Natural is one of: 
;; - 0
;; - (add1 Natural)

;-----------------------
;; Using Structural Recursion... i.e., template for Natural

#;(define (natural-temp n)
  (cond [(zero? n) ...]
        [else ... (natural-temp (sub1 n)) ...]))

;; pow : Number Natural -> Number
;; x to the nth power (where n is a natural number)
(define (pow.v0 x n)
  (cond [(zero? n) 1]
        [else (* x (pow.v0 x (sub1 n)))]))


;-----------------------
;; Using Generative Recursion...

;; pow : Number Natural -> Number
;; x to the nth power (where n is a natural number)
;; HOW: if n is even: compute x^(n/2) using recursion, 
;;      then square that [idea: x^n = (x^(n/2))^2]
;;      if n is odd, compute (x^(n-1)) using recursion, 
;;      then multiply that by x [idea: x^n = (x * (x^(n-1)))]
(define (pow x n)
  (cond 
    ;; -- trivial cases
    [(= n 0) 1]
    [(= n 1) x]
    ;; -- complex cases
    [(even? n) (local ((define y (pow x (/ n 2))))
                 (* y y))]
    [else ;; n is odd
     (* x (pow x (sub1 n)))]))
                   
(check-expect (pow 4 0) 1)
(check-expect (pow 2 2) 4)
(check-expect (pow 4 2) 16)
(check-expect (pow 2 5) 32)
(check-expect (pow 10 4) 10000)

;; ----------------------------------------------------------
;; PROBLEM: Finding Roots
;;
;; The root of a function f is some x value such that f(x) = 0. 
;; If a function is continuous and f(lo) * f(hi) <= 0, then f has 
;; a root in the range [lo, hi].

;; Design a function that finds an interval of size DELTA within
;; range [LO,HI] that contains a root of such a function.

;; find-root : Number Number Number [Number -> Number] -> Number
;; Find a window of size DELTA within range [LO,HI] containing an 
;; x where f(x)=0. Return the left edge of the window.
;; MUST f is continuous
;; MUST (<= (* (f lo) (f hi)) 0)
;; MUST lo <= hi

;-------------------------------------------------------
;; DESIGN: structural recursion plus composition
;; just check all these intervals

(define (find-root.slow delta lo hi f)
  (local [(define width (- hi lo))
          (define num-wins (ceiling (/ width delta)))
          (define (mk-win i) ; A window is represented by its left edge.
            (+ lo (* i delta)))
          (define intervals  (build-list num-wins mk-win))
          (define (good win)
	    (<= (* (f win) (f (+ win delta))) 0))]
    ;; Why is the "first" justified in the following line:
    (first (filter good intervals)))) ;; mathematics

;-----------------------------------------------------------
;; DESIGN: generative recursion
;; Idea: divide window in half each time and check which of two to 
;; continue searching in 
(define (find-root delta lo hi f)
  (cond [(<= (- hi lo) delta) lo] ;; base case
        [else (local ((define mid (/ (+ lo hi) 2))
                      (define f@lo (f lo))
                      (define f@mid (f mid)))
                      ;(define f@hi (f hi)))
                (cond 
                  [(= f@mid 0) mid]
                  [(<= (* f@lo f@mid) 0) 
                   (find-root delta lo mid f)]
                  [else ;; (<= (* f@mid f@hi) 0) 
                   (find-root delta mid hi f)]))]))
        
(check-within (find-root 0.001 -1 +1 (lambda (x) x)) 0 0.001)
(check-within (find-root 0.001 0 100 (lambda (x) (- (* x x) 9))) 3 0.001)

(find-root 0.0001 -1 +1 (lambda (x) x))             ; zero at x=0
(find-root 0.0001 0 100 (lambda (x) (- x 5)))       ; zero at x=5
(find-root 0.0001 0 100 (lambda (x) (- (* x x) 9))) ; zero at x=3

;; Find pi to varying precisions.
(find-root 0.1         1 4 sin)
(find-root 0.0001      1 4 sin)
(find-root 0.000000001 1 4 sin) ; Don't try this with slow version.

;; ----------------------------------------------------------
;; THE DESIGN RECIPE FOR GENERATIVE RECURSION

;; 1. DATA DEFINITION (representation, interpretation)
;; try to think of these now as "representing problems" 
;; not info

;; 2. SIGNATURE/PURPOSE
;; annotate the purpose with an extra line:
;; "generative recursion: ... the idea ..."
;; I.e., *how* -- in structural rec, how=what.

;; 3. FUNCTIONAL EXAMPLES
;; display examples: inputs, expected outputs
;; ALSO: work thru them to illustrate the process idea

;; 4. TEMPLATE
;; this is different now: not data but process oriented

;; 5. CODE
;; fill in the gaps, use the examples!

;; 6. TEST
;; as before

;; 7. NEW: does it terminate?  Explain why.

#| ---------------------------------------------------------
   The Design Template for Generative Recursion 

   what we observed: 
   -- at least one case when recusion stops   
      ==> need a solution in those cases 

   -- at least one case with recursion 
      ==> need a function that generates input
      ==> need a function that uses the result of the
      recursion to compute the final result 
|#

#;
(define (gen-template in)
  (cond
    [(trivial-case1? in) (trivial-solution1 in)]
    ...
    [(trivial-caseN? in) (trivial-solutionN in)]
    ;; ---
    [(complex-case? in)
     (combine-results
       (gen-template (generate-different-input in))
       ...
       (gen-template (generate-different-input in)))]))

#| QUESTIONS:

   -- what are the trivial cases?
   -- what are the trivial solutions in these cases?

   -- what are the complex cases?
   -- how do you generate the inputs for the recursion? 
   -- how are the (sub)results combined into the final results? 
|#