在Scheme中解释Fibonacci尾递归？

Question

我一直在尝试理解Scheme中的尾递归，并且很难理解使用尾递归计算斐波那契数列的go to示例中正在发生什么......

如果这是斐波那契数列的尾递归或迭代版本的代码：

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

我基本上可以理解每一行的内容，除了这里：

。

(fib-iter 1 0 n))

这行代码实际在做什么？我找不到任何解释。我对Scheme很陌生，语法目前还很困惑。

或者，有人能解释一下每行代码在做什么吗？这是我的基本理解，但我不确定是否正确：

(define (fib n) ;;define the function fib and variable n
  (fib-iter 1 0 n)) ;;?? no idea

(define (fib-iter a b count) ;;define function fib-iter, variables a, b and count
  (if (= count 0) ;;if the count is equal to 0, 
    b ;;return b
    (fib-iter (+ a b) a (- count 1)))) ;;recursively calling function fib-iter with 3 parameters (a+b), a and (count - 1)

thanks!

- Sarah

---

(define (fib n) ;定义函数fib和变量n，不完全是这样--这个定义了一个名为fib的函数，它接受一个名为n的参数。同样，(define (fib-iter ...)定义了一个名为fib-iter的函数，它接受3个参数，第1个命名为a，第2个命名为b，第3个命名为count。为了可视化尾递归的工作原理，请画两条水平线，分别位于(fib-iter a b count)的上方和下方。你得到的是一个框架——一个带有三个插槽（在本例中）的命名盒子。然后，每次调用(fib-iter x y z)只是将三个值x y z放入框架的三个插槽中，并（重新）启动其执行。 - Will Ness

Answer 1

在 fib 过程中有一个打字错误（缺少一个左括号），它应该定义如下：

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

话虽如此，迭代的fib过程使用一个名为fib-iter的辅助程序来实现实际迭代。这行代码：

(fib-iter 1 0 n)

这里是第一次调用helper函数。正如你所知，斐波那契数列以值n=0时的0和值n=1时的1开始，这也是我们传递给参数的确切值，用于启动迭代循环，同时还有我们想要在停止之前执行的迭代次数n。

从此以后，a将包含n-1的斐波那契值，b将包含n-2的斐波那契值，每个迭代步骤都会相应地更新a和b变量，直到n为零，此时我们停止并返回结果。

如果用命令式的方法来写同样的算法，可能更容易理解。以下是使用Python具体循环结构和相同变量名的示例。这等效于Scheme实现：

def fib(n):
    count = n
    a, b = 1, 0
    while count != 0:
        a, b = a + b, a
        count = count - 1
    return b

- Óscar López

---

我不明白为什么它不是（fib-iter 0 1 n）。 - Sarah

非常感谢！我终于能够理解它了。 - Sarah

@Sarah 如果 fib-iter 被写成 (if (zero? count) a (fib-iter b (+ a b) (- count 1))) 这样略有不同的方式，它会更好。但在你的情况下，a 和 b 的角色被从它们通常意义上进行了交换。 - C. K. Young

Answer 2

您的代码中有一个错误；fib 应该是一个过程：

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

它所做的是调用具有初始值a（= 1），b（= 0）和计数（=您想要的斐波那契数，即fib的形式参数n）的fib-iter函数。将打印语句添加到fib-iter中可以显示发生的情况，在此示例中为(fib 7)。

a=1  b=0  count=7 ; initial values as given by `fib`
a=1  b=1  count=6
a=2  b=1  count=5
a=3  b=2  count=4
a=5  b=3  count=3
a=8  b=5  count=2
a=13  b=8  count=1
a=21  b=13  count=0
13 ; the returned value for `(fib 7)`

- uselpa