scheme - 我如何在 Scheme 中找到斐波那契数列？

Question

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

只是享受 SICP 带来的乐趣。我完全理解斐波那契算法的思想，但这段代码让我陷入困境。与命令式样式相比，最后一行到底做了什么(这只是一个基本的递归还是)？

Answer 1

该过程将斐波那契数列实现为一个迭代 过程。在这种情况下，fib 是调用 fib-iter 的主要过程，它通过迭代完成实际工作。请注意，count 用于控制我们想要的迭代次数，而 a 和 b 用于存储斐波那契数列的结果n-1 和 n-2 分别。 (fib-iter (+ a b) a (- count 1)) 行将迭代推进到下一个值。

请花时间阅读书中有关迭代与递归过程的内容，还请阅读有关尾递归的内容 - 这些是您需要掌握的概念，才能真正理解示例中发生的事情。

为了比较，让我们看看使用更传统的语法(Python 的)相同过程的外观:

def fib(n):
  return fib_iter(1, 0, n)

def fib_iter(a, b, count):
  while count != 0:  # same as asking `(if (= count 0) ...)`
    a, b = a + b, a  # same as passing `(+ a b) a` to recursive call
    count -= 1       # same as `(- count 1)`
  return b           # same as returning `b` at end of recursion

如您所见，fib_iter 过程只是迭代由 count 变量控制的一系列值，分配 a 和 b 到系列中的下一个值，直到完成多次迭代；此时结果在b中并被返回。