sicp-1-2-1-linear-recursion-and-iteration

#lang racket

;; 1.9

(define (inc x) (add1 x))
(define (dec x) (sub1 x))

;; plus is recursive but not tail recursive hence not iterative

(define (plus a b)
  (if (zero? a)
      b
      (inc (plus (dec a) b))))

;; (plus 4 5)
;; (inc (plus 3 5))
;; (inc (inc (plus 2 5)))
;; (inc (inc (inc (plus 1 5))))
;; (inc (inc (inc (inc (plus 0 5)))))
;; (inc (inc (inc (inc 5))))
;; (inc (inc (inc 6)))
;; (inc (inc 7))
;; (inc 8)
;; 9

;; new-plus is tail recursive hence iterative

(define (new-plus a b)
  (if (zero? a)
      b
      (new-plus (dec a) (inc b))))

;; (new-plus 4 5)
;; (new-plus 3 6)
;; (new-plus 2 7)
;; (new-plus 1 8)
;; (new-plus 0 9)
;; 9

;; 1.10

;; Ackermann function a very fast-growing recursive function

(define (A x y)
  (cond [(zero? y) 0]
        [(zero? x) (* 2 y)]
        [(= y 1) 2]
        [else (A (sub1 x)
                 (A x (sub1 y)))]))

(A 1 10)
;; 1024
(A 2 4)
;; 65536
(A 3 3)
;; 65536

(define (f n) (A 0 n))
;; f(n) = 2 * n by definition

(f 0)
;; 0
(f 1)
;; 2
(f 2)
;; 4

(define (g n) (A 1 n))
;; g(n) = 2 ^ n for n > 0 because
;; g(1) = A(1, 1) = 2 by definition and
;; g(n) = A(1, n)
     ;; = A(0, A(1, n - 1))
     ;; = f(A(1, n - 1))
     ;; = 2 * A(1, n - 1)
     ;; = 2 * g(n - 1)

(g 0)
;; 0
(g 1)
;; 2
(g 2)
;; 4
(g 3)
;; 8
(g 4)
;; 16
(g 5)
;; 32

(define (h n) (A 2 n))
;; h(n) = an exponentiation tower of n 2's for n > 0 because
;; h(1) = A(2, 1) = 2 by definition and
;; h(n) = A(2, n)
     ;; = A(1, A(2, n - 1))
     ;; = g(A(2, n - 1))
     ;; = 2 ^ A(2, n - 1)
     ;; = 2 ^ h(n - 1)

(h 0)
;; 0
(h 1)
;; 2
(h 2)
;; 4
(h 3)
;; 16
(h 4)
;; 65536 ; 2 ^ 16