返回一个大小随迭代而增加的列表的迭代过程与返回标量的列表有什么不同吗？

Question

这实际上是因为我最初误读了练习1.12的文本。

这个要求确实是

编写一个程序，通过递归过程计算帕斯卡三角形的元素。

我严重地将递归误认为是迭代，并花了相当多的时间试图理解在世界上哪里我可以想出一些可以描述任何给定阶段的计算状态的数字，但我没有'想不出任何办法。恰恰相反，我认为你不能只用恒定数量的标量来表示三角形的计算状态。

所以我最终重新阅读了练习陈述，意识到了我的错误并按照预期的方式完成了练习。

但是，事实上，在接下来的练习中也不需要该解决方案的迭代过程，这让我认为这样的解决方案可能不存在，或者它具有一些属性，使其与实现的其他递归过程根本不同作为迭代过程。

无论如何，我很好奇，所以想：如果状态不是数字而是列表怎么办？在这种情况下，计算的状态很自然地是三角形的前一行；即，需要计算三角形第 n 行的每个元素和所有元素就是第 n-1 行。

所以我想出了这个程序

(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))

其中

pascal-impl

进行三角形（行）和计数

t

计算的状态

i

。然后主函数

pascal

从所需的行中选择适当的条目。

现在，抛开由于使用裸列表而导致的可以理解的低效率，我想知道

• 如果上述过程被归类为迭代，
• 以及迭代状态是否/如何成为大小随迭代深度增加的实体影响迭代过程的属性。或者，相反，状态增加大小和过程的迭代性质是“正交”属性？

---

我假设这些实用程序或者它们的性能更好的版本可用：

(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))))

Answer 1

“迭代”简单来说就是不递归。因此，你的

pascal-impl

，是尾递归的，实际上描述了一个循环，所以确实是迭代的。

国家的规模确实是一个正交问题。在你的函数中，第 n 步骤确实增长为 ~ 2n。

顺便说一句，

zipWith+

可以编码为列表尾部的右折叠（即其迭代的

cdr

），从而消除了对

concat

的需要。