SICP 1.2.1
Posted on 2015-02-12 07:59:53 +0900 in SICP
1.9
(define (+ a b)
(if (= a 0) b (inc (+ (dec a) b))))
(define (+ a b)
(if (= a 0) b (+ (dec a) (inc b))))The first version is recursive and the second one is iterative. For the compilers such as Lisp, which implemented tail call optimiztion, they make no difference. But for other compilers such as C, Python, it would make big difference on memory usage and speed.
1.10
(A 0 n) = 2n
(A 1 n) = (A 0 (A 1 (- n 1))) = 2 * (A 1 (- n 1)) = 2 ^ n
(A 2 n) = (A 1 (A 2 (- n 1))) = 2 ^ (A 2 (- n 1)) = 2 ^ (2 ^ n)Hide Comments
comments powered by Disqus