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)