帕斯卡三角迭代过程归类判定及状态规模影响探讨

背景 #

最初误读了SICP习题1.12的要求，把题目需要的递归过程误判为迭代过程。尝试用固定数量的标量表示计算状态失败后，改用列表存储帕斯卡三角的上一行作为状态，实现了如下过程：

主过程 #

(define (pascal i j)
  (define (update t)
    (concat (cons 1 (zipWith+ (cdr t) t)) '(1)))
  (define (pascal-impl i t)
    (if (= i 0)
        t
        (pascal-impl (- i 1) (update t))))
  (element (pascal-impl i '(1)) j))

辅助过程 #

(define (zipWith+ a b)
  (if (null? a)
      '()
      (cons (+ (car a) (car b)) 
            (zipWith+ (cdr a) (cdr b))))

(define (concat a b)
  (if (null? a)
      b
      (cons (car a) 
            (concat (cdr a) b))))

(define (element xs i)
  (if (= i 0)
      (car xs)
      (element (cdr xs) (- i 1))))

问题解答 #

1. 上述过程是否属于迭代过程？ #

是。按照SICP对迭代过程的定义：迭代过程的每一步都能被一组状态变量完整描述，后续计算仅依赖这组变量；同时过程是尾递归结构——即最后一步操作是调用自身，没有需要挂起的未完成计算。

这里的pascal-impl是尾递归，每次递归调用时，之前的调用无需保留任何上下文信息，所有必要的计算状态都存在参数t（当前帕斯卡三角的行）中。每次迭代仅更新t为下一行，完全符合迭代过程的核心特征。

2. 迭代状态规模随迭代深度增长是否影响迭代过程的性质？ #

二者是正交属性。

迭代过程的判定标准是尾递归结构+状态可通过当前步骤完全更新，和状态的规模大小无关。哪怕状态（比如这里的列表）随迭代次数变长，只要每一步都是尾调用、没有未完成的计算需要留存，就依然是迭代过程。状态规模增长只会影响空间复杂度，但不会改变过程的迭代本质。

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