Courses‎ > ‎Introduction to Computer Science 1‎ > ‎Konstantinovich‎ > ‎ML1 9/2012‎ > ‎labs‎ > ‎

Lab 03

posted Oct 5, 2012, 6:11 AM by Samuel Konstantinovich   [ updated Dec 21, 2012, 5:23 AM ]
;##########################################
;Notes:

;###### Regular Recursion ###### 
;the recursive call requires the recursion to complete before the works is done

;example:   5+fact(4)  requires fact(4) to evaluate BEFORE the multiplication. 
;This means the work is done from the tail end and propagates back to the start.
(define (Fact n)
  (if (= n 0)
      1
      (* n (Fact (- n 1)))))

;###### Iterative style recursion ######
;The work is done, then it is passed into the recursive call for it to do the work. 
;This requires an extra parameter to store the partially completed answer
;like the GCF needed a helper function with a 3rd parameter
;When the recursion hits the base case, the answer should already be known
;This is great because there are no pending operations waiting to be completed.

(define (helpFact n partialSolution)
        (if 
         (= n 0) 
         partialSolution ;when you reach 0, use the partial solution
         (helpFact (- n 1) (* n partialSolution) ) ;when it is too big, update the partial solution and run it again
         ))

(define (iterFact n)
  (helpFact n 1))
;start the product at 1. Help will then keep calculating the solution


;##########################################
;Actual Lab:
;Make sure you save your files on your account or email them to yourself if you are sharing a computer/using Guest 
;If I ever ask you to open up an old lab for reference starting with lab3, and you cannot produce it, I will be VERY ANGRY.
;###   1   ###
;trace through both versions using the stepper...R
;(change your language to beginning student)
;view -> Show tracing
;now you can press the step button
(Fact 8)
(iterFact 8)

;BEFORE you start writing code, discuss the lettered points below each question. 
;If you are done and you need to find someone to talk to, ask me to move around the room.

;### 2 ###
;Now try to write (SumAtoB a b) using an Iterative Style Solution!!!
;a. use a helper, what parameters are required?
;b. remember you should keep the partial solution updated at each step AND change the value.
;c. the stopping condition should be when the a and b are the same value.
;d. assume a<=b.

;### 3 ###
;Try to do Fibonacci (you need to store the partial solution AND the previous two results...
;a. How many parameters fib numbers are required to get the next number? 
;b. How many parameters are required?  
Comments