Fibonacci 的 SICP 解决方案，设置 `a + b = a`，为什么不是 `a + b = b`？

Question

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

We can also formulate an iterative process for computing the Fibonacci numbers. The idea is to use a pair of integers a and b, initialized to Fib(1) = 1 and Fib(0) = 0, and to repeatedly apply the simultaneous transformations

It is not hard to show that, after applying this transformation n times, a and b will be equal, respectively, to Fib(n + 1) and Fib(n). Thus, we can compute Fibonacci numbers iteratively using the procedure

（由 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

"Set a + b = a and b = a"，我很难理解它。

找到 fib 的一般思路很简单：

假设一个完整的斐波那契数table，从0逐步跳到X，在table中搜索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

据我所知，您的问题是您不喜欢 fib-iter 的参数顺序不是您认为应该的顺序。答案是函数参数的顺序通常是任意的 and/or 约定俗成的：这是编写函数的人做出的选择。除了阅读或编写代码的人之外，这对任何人都没有关系：这是一种风格选择。将 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))))

有些情况并非如此。例如 Standard Lisp（警告，PDF link）定义了 mapcar，因此被映射的列表是 first 参数，函数被映射到第二。这意味着您不能按照它为更新的方言扩展的方式扩展它，因此它需要任何正数的列表并将函数应用于所有列表的对应元素。

同样，我认为以相反的方式定义 - 或 / 的参数是非常不直观的。

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

Answer 2

递归以命令式形式给出。例如，在 Common 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

当我们计算序列时，有一个双数 window 我们称其条目为 a 和 b , 它沿着序列滑动。您可以直接从计算尺读取任何位置的等式：看，b = a' = 5 和 a = b' + a' = 8.

您可能会对 a 指的是序列中较高的位置感到困惑。你可能会想到这个标签：

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

确实，在这种命名安排下，现在我们有 b = a' + b'，如你所料，a = b'.

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

“a 领先”的约定源于 a 在 b[=59= 之前的想法] 在字母表中，因此它首先从序列中接收较新的“更新”，然后传递给 b.

这似乎违反直觉，但这种模式出现在数学的其他地方，例如 convolution 函数。

Fibonacci 的 SICP 解决方案，设置 `a + b = a`，为什么不是 `a + b = b`？

SICP solution to Fibonacci, set `a + b = a`, why not `a + b = b`?

lisp

algorithm

elisp

sicp

fibonacci