Fibonacci的SICP解，集“a b=a”，为什么不“a b=b”？

Question

我正在阅读SICP的树递归，其中fib是通过线性递归计算的。

我们还可以制定一个迭代过程来计算斐波那契数。其思想是使用一对整数a和b，初始化为Fib（1）=1和Fib（0）=0，并重复应用同时变换

不难证明，在应用该变换n次后，a和b将分别等于Fib（n1）和Fib（n）。因此，我们可以使用该过程迭代计算斐波那契数

（由Emacs Lisp重写，代替Scheme）

#+begin_src emacs-lisp :session sicp 
(defun fib-iter (a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

(defun fib (n)
  (fib-iter 1 0 n))

(fib 4)
#+end_src

“设置a b=a和b=a，我很难把我的思想围绕在它周围。”。

假设一个完整的斐波那契数表，通过从0一步一步跳转到X在表中搜索X。

解决方案几乎不直观。

设置a b=b，a=b是合理的：

(defun fib-iter (a b count)
  (if (= count 0)
      a
      (fib-iter b (+ a b) (- count 1))
  )
)
(defun fib(n)
  (fib-iter 0 1 n))

因此，作者的设置似乎只不过是反直觉地将b放入头部，没有任何特殊目的。

然而，我肯定承认SICP值得越来越深入地挖掘。

我遗漏了哪些关键点？为什么设置a b=a而不是a b=b？

Answer 1

递归以命令形式给出。例如，在通用Lisp中，我们可以在循环体中使用并行赋值：

(psetf a (+ a b) 
       b a)

为了减少混淆，我们应该从功能上考虑这一点，并给新旧变量不同的名称：

a=a“b”

b=a'

这不再是一个赋值，而是一对等式；我们有理由使用数学中的普通“=”运算符，而不是赋值箭头。

线性递归隐式地这样做，因为它避免了赋值。表达式（a b）的值作为参数a传递。但这是新范围内a的新实例，它使用相同的名称，而不是赋值；绑定只是诱导两者等价。

借助“斐波那契滑动法则”，我们也可以这样看：

    1  1  2  3  5  8  13
    ----------------------------- <-- sliding interface
             b' a' 
                b  a

当我们计算序列时，有一个双数窗口，我们调用其条目a和b，它沿着序列滑动。您可以直接从幻灯片规则中读取任何位置的等式：看，b=a'=5和a=b'a'=8。

您可能会对序列中较高位置的指代感到困惑。您可能会想到以下标签：

    1  1  2  3  5  8  13
    ------------------------
             a' b'
                a  b

事实上，在这种命名安排下，现在我们有了b=a‘b’，正如你们所期望的，和a=b’。

这只是一个问题，哪一个变量被指定为序列中更远的前导变量，哪一个是尾随变量。

“a领先”约定来自字母表中a在b之前的想法，因此它首先从序列中接收更新的“更新”，然后传递给b。

这似乎违反直觉，但这种模式出现在数学的其他领域，例如函数卷积。

Answer 2

据我所知，你们的问题是，你们不喜欢它，fib iter的参数顺序不是你们认为应该的。答案是函数的参数顺序通常是任意的和/或常规的：这是编写函数的人所做的选择。除了阅读或编写代码的人之外，这对任何人都无关紧要：这是一种文体选择。对于我来说，将fib定义为

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter next current n)
  (if (zero? n)
      current
      (fib-iter (+ next current) next (- n 1))))

而不是

(define (fib n)
  (fib-iter 0 1 n))

(define (fib-iter current next n)
  (if (zero? n)
      current
      (fib-iter (+ next current) current (- n 1))))

有些情况下这是不正确的。例如，标准Lisp（警告，PDF链接）定义了mapcar，因此映射的列表是第一个参数，函数是第二个参数。这意味着你不能像最近的方言那样扩展它，因此它需要任何正数的列表，函数应用于所有列表的相应元素。

同样，我认为反过来定义-或/的参数是非常不直观的。

但在很多情况下，这只是一个做出选择并坚持的问题。