sicp-1-2-2-tree-recursion

#lang racket

;; 1.11

(define (recursive-f n)
  (cond [(< n 3) n]
        [else (+ (recursive-f (- n 1))
                 (* 2 (recursive-f (- n 2)))
                 (* 3 (recursive-f (- n 3))))]))

(recursive-f 1)
;; 1
(recursive-f 2)
;; 2
(recursive-f 3)
;; 4
(recursive-f 4)
;; 11
(recursive-f 5)
;; 25
(recursive-f 6)
;; 59

(define (iterative-f n)
  (define (f-iter a b c cnt)
    (cond [(zero? cnt) a]
          [else (f-iter (+ a (* 2 b) (* 3 c))
                        a
                        b
                        (sub1 cnt))]))
  (cond [(< n 2) n]
        [else (f-iter 2 1 0 (- n 2))]))

(iterative-f 1)
;; 1
(iterative-f 2)
;; 2
(iterative-f 3)
;; 4
(iterative-f 4)
;; 11
(iterative-f 5)
;; 25
(iterative-f 6)
;; 59

;; 1.12

(define (pascal row col)
  (cond [(or (= col 1) ; start of row
             (= row col)) ; end of row
         1]
        [else (+ (pascal (sub1 row) (sub1 col)) ; sum of two elements above
                 (pascal (sub1 row) col))]))

(pascal 5 1)
;; 1
(pascal 5 2)
;; 4
(pascal 5 3)
;; 6
(pascal 5 4)
;; 4
(pascal 5 5)
;; 1

;; 1.13

;; Note that phi ^ 2 = phi + 1 and psi ^ 2 = psi + 1 because phi and psi are roots
;; of x ^ 2 - x - 1 = 0.

;; claim:  Fib(n) = (phi ^ n - psi ^ n) / sqrt(5)

;; Go by induction.  The base cases n = 0 and n = 1 are true.

;; The induction step is
;; [phi ^ (n + 1) - psi ^ (n + 1)] / sqrt(5)
    ;; = [phi ^ 2 * phi ^ (n - 1) - psi ^ 2 * psi ^ (n - 1)] / sqrt(5)
    ;; = [(phi + 1) * phi ^ (n - 1) - (psi + 1) * psi ^ (n - 1)] / sqrt(5)
    ;; = [phi ^ n + phi ^ (n - 1) - psi ^ n - psi ^ (n - 1)] / sqrt(5)
    ;; = (phi ^ n - psi ^ n) / sqrt(5) + (phi ^ (n - 1) - psi ^ (n - 1)) / sqrt(5)
    ;; = Fib(n) + Fib(n - 1) by induction
    ;; = Fib(n + 1)

;; That Fib(n) is the closest integer to phi ^ n / sqrt(5) follows from the above
;; claim combined with the fact that abs(psi ^ n / sqrt(5)) < 0.5.

;; In particular Fib(n) = O(phi ^ n) is exponential.