Scheme正数递归乘法的执行逻辑与函数栈疑问

先看你提供的完整代码：

;Recursive Arithmetic
(define increment
  (lambda (x)
    (+ x 1)))

(define decrement
  (lambda (x)
    (- x 1)))

(define recursive-add
  (lambda (x y)
    (if (zero? y)
        x
        (recursive-add (increment x) (decrement y)))))

"Define Multiplication Recursively"
(define recursive-mult
  (lambda (x y)
    (if (zero? y)
        0
        (recursive-add x (recursive-mult x (decrement y)))))) ;else

(recursive-mult 9 5)

核心执行逻辑：应用序求值 #

Scheme遵循应用序求值规则——调用函数前，会先计算该函数的所有参数，再执行函数本身。这是理解else分支执行顺序的关键。

对于recursive-mult的else分支(recursive-add x (recursive-mult x (decrement y)))，执行步骤是：

1. 先计算第一个参数x（直接取当前值，无需额外计算）
2. 计算第二个参数(recursive-mult x (decrement y))：
   • 先执行(decrement y)得到新的y值
   • 递归调用recursive-mult，直到触发base case（y=0时返回0）
3. 等第二个参数的递归计算完成，得到具体数值后，才会调用recursive-add

以(recursive-mult 9 5)为例的完整执行流程 #

我们一步步拆解函数栈的变化：

1. 递归向下压栈（计算recursive-mult的嵌套调用） #

• 初始调用：(recursive-mult 9 5) → y≠0，需要计算(recursive-add 9 (recursive-mult 9 4))，先处理(recursive-mult 9 4)
• (recursive-mult 9 4) → y≠0，需要计算(recursive-add 9 (recursive-mult 9 3))，先处理(recursive-mult 9 3)
• (recursive-mult 9 3) → y≠0，需要计算(recursive-add 9 (recursive-mult 9 2))，先处理(recursive-mult 9 2)
• (recursive-mult 9 2) → y≠0，需要计算(recursive-add 9 (recursive-mult 9 1))，先处理(recursive-mult 9 1)
• (recursive-mult 9 1) → y≠0，需要计算(recursive-add 9 (recursive-mult 9 0))，先处理(recursive-mult 9 0)
• (recursive-mult 9 0) → 触发base case，返回0，此时栈开始回溯

2. 回溯向上计算recursive-add #

• 拿到(recursive-mult 9 0)的结果0，执行(recursive-add 9 0) → 触发base case，返回9
• 拿到这个结果，执行上一层的(recursive-add 9 9) → 递归执行加法，最终返回18
• 继续上一层：(recursive-add 9 18) → 返回27
• 再上一层：(recursive-add 9 27) → 返回36
• 最外层：(recursive-add 9 36) → 返回45，即最终结果

纠正你的错误假设 #

• 假设1错误：先执行(decrement y)并递归调用recursive-mult，并不会导致recursive-add无法执行。递归调用是为了算出recursive-add需要的第二个参数，等所有嵌套的recursive-mult都返回结果后，recursive-add才会被逐层调用执行。
• 假设2错误：Scheme不会先执行recursive-add x，因为recursive-add需要两个完整参数才能调用。第二个参数没计算完成前，recursive-add根本不会启动。

函数栈的运作总结 #

每一次递归调用recursive-mult时，当前的x、y值以及后续要执行的recursive-add逻辑都会被压入调用栈。直到触发base case（y=0），栈开始弹出上下文，每弹出一层就用该层的x和下层返回的结果作为参数，执行recursive-add计算，再把结果传给上一层，直到栈空，返回最终结果。

内容的提问来源于stack exchange，提问作者chromechris