SICP1.2.1 Recursion & Iteration
Published: 2020-06-14T18:28:16.000Z
Ok, second subchapter is more challenging, so I'll go by subsections.
Exercise 1.9
This is trivial. This procedure generates recursive process:
(define (+ a b)
(if (= a 0)
b
(inc (+ (dec a) b))))
And this iterative:
(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b))))
We could see this even without substitution model, if function returns itself in the and without any additional operation on its result - it is tail-recursive, so generates iterative process, otherwise - recursive.
Exercise 1.10 (Ackerman function)
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))
(A 1 10)
=> (A 0 (A 1 9))
=> (* 2 (A 1 9))
=> (* 2 (*2 (A 1 8)))
...
=> (* 2^9 (A 1 1))
=> 2^10
(A 2 4)
=> (A 1 (A 2 3))
=> 2^(A 2 3)
;;; see below ;;;
=> 2^16
(A 2 3)
=> (A 1 (A 2 2))
=> 2^(A 2 2)
;;; see below ;;;
=> 2^4 => 16
(A 2 2)
=> (A 1 (A 2 1))
=> (A 1 2)
=> (A 0 (A 1 1))
=> (* 2 2)
=> 4
(A 3 3)
=> (A 2 (A 3 2))
=> (A 2 (A 2 (A 3 1)))
=> (A 2 (A 2 2))
;;; see one above ;;;
=> (A 2 4)
;;; see 3 above ;;;
=> 2^16
(define (f n) (A 0 n))
f(n) = 2n
(define (g n) (A 1 n))
g(n) = 2^n
(define (h n) (A 2 n))
h(1) = 2
h(n) = 2^(h(n-1))