SICP学习笔记 1.2.1 线性的递归和迭代
? 练习1.9
? ? 对于过程
? ? (define (+ a b)
? ? ? (if (= a 0)
? ? ? ? b
? ? ? ? (inc (+ (dec a) b))))
? ? 计算(+ 4 5)时的替换过程为
? ? -->(+ 4 5)?
? ? -->(if (= 4 0) 5 (inc (+ (dec 4) 5)))
? ? -->(inc (+ 3 5))
? ??-->(inc (if (= 3 0) 5 (inc (+ (dec 3) 5))))
? ??-->(inc (inc (+ 2 5)))
? ??-->(inc (inc (if (= 2 0) 5 (inc (+ (dec 2) 5)))))
? ??-->(inc (inc (inc (+ 1 5))))
? ??-->(inc (inc (inc (if (= 1 0) 5 (inc (+ (dec 1) 5))))))
? ??-->(inc (inc (inc (inc (+ 0 5)))))
? ??-->(inc (inc (inc (inc (if (= 0 0) 5 (inc (+ (dec 0) 5)))))))
? ??-->(inc (inc (inc (inc 5))))
? ??-->(inc (inc (inc 6)))
? ??-->(inc (inc 7))
? ??-->(inc 8)
? ??-->9
? ? 为线性递归;
? ??对于过程
? ??(define (+ a b)
??? ??(if (= a 0)
? ? ??? ??b
? ? ??? ??(+ (dec a) (inc b))))
? ??计算(+ 4 5)时的替换过程为
? ??-->(+ 4 5)
? ??-->(if (= 4 0) 5 (+ (dec 4) (inc 5)))
? ??-->(+ 3 6)
? ??-->(if (= 3 0) 6 (+ (dec 3) (inc 6)))
? ??-->(+ 2 7)
? ??-->(if (= 2 0) 7 (+ (dec 2) (inc 7))) ?
? ??-->(+ 1 8)
? ??-->(if (= 1 0) 8 (+ (dec 1) (inc 8)))?
? ??-->(+ 0 9)
? ??-->(if (= 0 0) 9 (+ (dec 0) (inc 9)))
? ??-->9 ? ? ? ??
? ??为线性迭代.
?
? 练习1.10
?
? ? (A 1 10)-->(A 0 (A 1 9))
? ? ? ? -->(* 2 (A 1 9))
? ? ? ? -->(* 2 (A 0 (A 1 8)))
? ? ? ? -->(* 2 (* 2 (A 1 7)))
? ? ? ? -->......
? ? ? ? -->2^10
? ? (A 2 4) -->(A 1 (A 2 3))
? ? ? ? -->(A 1 (A 1 (A 2 2)))
? ? ? ? -->(A 1 (A 1 (A 1 (A 1 (A 2 1)))))
? ? ? ? -->(A 1 (A 1 (A 1 (A 1 2))))
? ? ? ? -->(A 1 (A 1 (A 1 2^2)))
? ? ? ? -->(A 1 (A 1 2^4))
? ? ? ? -->(A 1 2^8)
? ? ? ? -->2^16
? ? (A 3 3) -->(A 2 (A 3 2))
? ? ? ? -->(A 2 (A 2 (A 3 1)))
? ? ? ? -->(A 2 (A 2 2))
? ? ? ? -->(A 2 2^2)
? ? ? ? -->2^16
?
? ? (A 0 n) -->2n
? ? (A 1 n) -->2^n
? ? (A 2 n) -->2^(2^n)
