SICP练习1.16：所编写的exp过程属于递归还是迭代？

你的exp过程属于递归过程，并非迭代过程，递归与迭代过程有明确的区分标准，核心看计算过程中是否存在需要推迟的操作，以及状态的保存方式：

递归与迭代过程的区分标准 #

• 迭代过程：计算的每一步，所有必要状态都通过参数传递，没有需要后续完成的推迟操作（即尾调用），程序不需要额外保存中间栈帧来记住后续要做的事情。这类过程的状态可以用固定数量的变量完全描述，每一步仅更新这些变量，直到满足终止条件。
• 递归过程：计算过程中存在推迟的操作，比如调用自身后还需要进行运算（乘法、加法等），此时程序必须在栈中保存当前上下文，等递归调用返回后再完成推迟的操作，依赖栈来存储中间状态。

你的代码分析 #

看你编写的exp过程：

(define (exp b n)
        (cond ((= n 1) b)
              ((even? n) (exp (square b) (/ n 2)))
              (else (* b (exp (square b) (/ (- n 1) 2))))))
(define (square x) (* x x))
(define (even? x) (= (remainder x 2) 0))

• 当n为奇数时，执行(* b (exp ...))：exp调用返回后，还需要将结果与b相乘，这个乘法就是推迟的操作，程序必须记住这个乘法要在递归调用完成后执行，因此会在栈中保存当前状态，属于递归过程。
• 哪怕n是2的幂时，表面上没有推迟操作，但过程结构本身不是尾递归（终止条件直接返回b，而非通过累积变量），本质上仍是递归过程的特例，不是迭代过程。

符合要求的迭代版本 #

按照练习提示，引入额外状态变量a保持a*b^n的乘积不变，正确的迭代过程应为尾递归形式：

(define (exp-iter b n a)
  (cond ((= n 0) a)
        ((even? n) (exp-iter (square b) (/ n 2) a))
        (else (exp-iter (square b) (/ (- n 1) 2) (* a b)))))

(define (exp b n)
  (exp-iter b n 1))

这个版本中，每一步的exp-iter调用都是尾调用，所有状态都保存在a、b、n三个变量中，没有任何推迟操作，计算到n=0时直接返回累积结果a，属于对数步数的迭代求幂过程。

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