格式中斐波那契尾递归的解释？

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

这一行到底发生了什么？我在任何地方都找不到解释。我是计划的新手，到目前为止语法非常混乱。

或者有人能解释每一行发生了什么吗？这是我的基本理解，但我不确定我是否正确：

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

谢谢

Answer 1

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

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

它的作用是调用fib-iter，初始值为a（=1）、b（=0）和count（=您想要的斐波那契数，这是n到fib的形式参数）。

将打印“语句”添加到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)`

Answer 2

fib过程中有一个输入错误（缺少左括号），应定义如下：

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

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

(fib-iter 1 0 n)

只是第一次给助手打电话。众所周知，斐波那契级数从n=0的值和n=1的值开始，这正是我们作为参数传递的值，以开始迭代循环，以及n的值，这是我们在停止之前要进行的迭代次数。

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

如果我们以命令式风格编写同一个算法，可能更容易描述发生了什么。下面是Python中使用显式循环构造和相同变量名的一个示例。这相当于方案实施：

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