S3. Recursion notes/problems

posted Oct 10, 2012, 6:18 AM by Samuel Konstantinovich   [ updated Nov 15, 2012, 5:12 AM ]
;Numerical Recursion Wrap Up:

;The tools we used with recursion so far:

;A. generate a sequence of numbers, 
;   -incrementing with + or - (count uses + or - 1)
;   -fibonacci like patterns
;   -other patterns halving/doubling/etc.  

;B. separate an integer digit by digit
;   -remainder by 10 gives the last digit
;   -quotient by 10 gives the rest of the number 
;
;Now decide what do you do with all those values? 
;Do you add/multiply them all together?
;Do you add/multiply some of them?


;C. Iterative solutions (formerly head recursion)
;   -Keeps the answer partly done as you go along
;   -More challenging conceptually
;   -This topic is going to be an extra credit topic
;    (on the last scheme exam, and the final exam)



;More recursive Problems: (easy/medium/hard)
;1. (sumOddDigits n) 
;   this adds all of the digits that are odd, ignores the rest 
;   (sumOddDigits 12345) -> 9  because you add the 1 3 and 5 only.

;2. lets analyze the fib function regular recursion we started with (see below):

(define (fib n)
  (cond
    ((= n 0 ) 0)
    ((= n 1 ) 1)
    (else (+ (fib (- n 2))(fib(- n 1))))))

;assume each comparison (=) costs $0.01
;assume each + or - costs $1.00
;(fibcost 0) is 0.01, because fib would use the 1st =
;(fibcost 1) is 0.02, because fib used the 1st and 2nd =
;(fibcost 2) fib uses both ='s, then uses + and two -'s, and calls more fibs.
; this means the cost of fib2 is the cost of fib2, PLUS the cost
; of the other two fib calls. This means the fibcost function
; grows like the fib sequence grows. (Write some costs out on paper!)
; This requires some thinking and writing out on paper

;CHALLENGE:
;3.(reverseDigits n) n is any integer (requires exponents, and numdigit) this is more challenging
;   (reverseDigits 123) -> 321  
;   (reverseDigits 32451) -> 15423


;SOLUTIONS TO 2 and 3:
(define (fibcost n)
  (cond
    ((= n 0) .01)
    ((= n 1) .02)
    (else (+ 3.02 (fibcost (- n 1))(fibcost(- n 2))))))

(display "fibcost(3)=")
(fibcost 3)
(display "fibcost(4)=")
(fibcost 4)
(display "fibcost(5)=")
(fibcost 5)



;3 CHALLENGE PROBLEM:
(define (len x)
  (if (< x 10) 1 (+ 1 (len (quotient x 10)))))
(define (MyReverse x)
  (if (=(quotient x 10)0)
      x
      (+ (* (remainder x 10)
            (expt 10 (- (len x)1) ))
         (MyReverse (quotient x 10)))))

(display "reverse(51234)=")
(MyReverse 51234)


;Iterative challenge problem (no exponents!)
(define (reverseIterative x)
  (helpRev x 0))

(define (helpRev  x s)
  (if (= x 0)
      s
      (helpRev  (quotient x 10) (+ (remainder x 10)(* 10 s)))))

(display "reverse(5123114)=")
(reverseIterative 5123114)


Comments