SICP

Lec1b.md

Computational modle

substition modle

Linear Iteration time = O(n) space = O(1)

Linear Recursion time = O(x) space = O

Recursion

Fibonacci

(DEFINE (fib n)
  (if ( < n 2)
      n
      (+ fib(- n 1) fib(- n 2))))

time = O(log(n)), some fib was calculated (as tree nodes)

Towers of Hanoi

square_root.scm

(define (square x) 
  (* x x))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (average x y)
  (/ (+ x y) 2))

(define (improve guess x)
  (average guess (/ x guess)))                

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
    guess
    (sqrt-iter (improve guess x) x)))

(define (sqrt x)
  (sqrt-iter 1.0 x))

(sqrt 9) ; 3.00009155413138