先把两个函数的代码贴出来:
(分别用 plus1 与 plus2 表示)

(define (plus1 a b)
  (if (= a 0)
    b
    (inc (plus1 (dec a) b))))

(define (plus2 a b)
  (if (= a 0)
    b
    (plus2 (dec a) (inc b))))

进行代换 (因为上述的 plus/inc/dec 都是普通函数/过程, 所以应该先求值参数, 也就是应用序)
对于 (plus1 4 5):

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

对于 (plus2 4 5):

(plus2 4 5)
(plus2 3 6)
(plus2 2 7)
(plus2 1 8)
(plus2 0 9)
9

第一种是线性递归过程, 因为形状是先展开后收缩(递归), 而且步骤数量与参数成正比(线性)
第一种是线性迭代过程, 因为形状是固定的(迭代), 而且步骤数量与参数成正比(线性)

这两个函数, 都是 递归过程, 要分清 递归计算过程 与 递归过程 的概念

当某个过程的定义中引用了该过程本身, 则是 递归过程
当某个递归过程计算时具有某种模式/形状时, 称这种模式为 递归计算过程

上一篇: 1-8
下一篇: 1-10