algorithm - 斐波那契的 SICP 解，设置 `a + b = a`，为什么不使用 `a + b = b`？

Question

我正在阅读SICP 的树递归，它 fib是由线性递归计算的。

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

不难证明，在应用此变换n 次后，a和b将分别等于Fib(n + 1)和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”，我很难绕开它。

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

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

该解决方案几乎不直观。

合理地设置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？

标签： algorithmlispelispfibonaccisicp

Answer 1

据我所知，你的问题是你不喜欢它的论点顺序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使被映射的列表是第一个参数，而被映射的函数是第二个参数。这意味着您不能以它为更新的方言扩展的方式扩展它，因此它需要任何正数的列表，并将函数应用于所有列表的相应元素。

-同样，我认为定义论点或/其他方式将非常不直观。

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