Lesson Plan - 6.001 SP04 - recitation 3

Recursion

Special form - cond

(cond clause
      clause
      clause)

clause -  (test cons)
       or (else alt)

substitution model
recursive procedures
recursive vs iterative

state the plan!
ask the right questions 

ask fact of 0 1 2 5

(define fact
  (lambda (n)
    (if (= n 0)
        1
        (* n (fact (- n 1))))))

ask rem of (5 7) (7 345) (6 5) (11 5)

(define remainder
  (lambda (num divisor)
    (if (> divisor num)
        num
        (remainder (- num divisor) divisor))))

iterative / recursive?

compute-e
1. look it up
2. use exp (exp 1)
3. use formula
(define (find-e n)
  (if (= n 0)
      1.
      (+ (/ (fact n)) (find-e (- n 1)))))

Compute nth fibonacci number
plan: compute it from sum of n-1 and n-2th fib nums
      fib 0 = 1, fib 1 = 1
(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

Compute golden ratio
plan: ratio of adjacent fibonacci numbers
(define (find-golden-ratio n)
  (/ (fib n) (fib (- n 1))))

Compute pi
plan: monte carlo method
(define (guess-pi count)
  (* (/ (throw-n-darts count) count) 4))

(define (throw-n-darts n)
  (if (= n 0)
      0
      (if (< (sum-of-squares (random 1.0) (random 1.0)) 1)
	  (+ 1 (throw-n-darts (- n 1)))
	  (throw-n-darts (- n 1)))))

(guess-pi 10000)
;Value: 3.1444