SICP中使用迭代过程的斐波那契数列，不能完全理解

Question

这是在 SICP 中计算斐波那契数列的过程的迭代示例。思路是：

a = fib(n+1) = a+b
b = fib(n) = a

(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(n+1) 。我发现我们可以写。

;; a and b are first and second integers respectively
;; in the recursive call, b would be replaced by a+b because it is the next number in the sequence
;; so now a will be replaced by the previous value of b because it is the previous value.
(define (fib2 n) 
  (fib-iter 1 0 n))
(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter b (+ a b) (- count 1))))

现在，我真的觉得第一个例子，一直到 n+1 的例子真的是多余的。我不明白为什么这是必要的。我提出的迭代示例有什么问题？

Answer 1

没有错。两种方法给出相同的结果。

#lang racket
(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))))

(define (fib2 n) 
  (fib-iter2 1 0 n))

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

(define xs '(0 1 2 3 4 5 6 7 8 9 10))
(map fib  xs)
(map fib2 xs)

输出为：

'(0 1 1 2 3 5 8 13 21 34 55)
'(0 1 1 2 3 5 8 13 21 34 55)

这表明你确实在计算相同的序列。

Answer 2

机器人程序产生正确的结果。但是，第一个保留了 a 和 b 之间的关系： a 是 Fib(i+1) 并且 b 是 Fib(i) 其中 i=n-count .第二种方法使用第一次迭代来交换 a 和 b ，从而引入一个冗余迭代。这可以通过跟踪程序看出：

> (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))))
> (trace fib-iter)
> (fib 3)
>(fib-iter 1 0 3)
>(fib-iter 1 1 2)
>(fib-iter 2 1 1)
>(fib-iter 3 2 0)
<2
2
> (define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter b (+ a b) (- count 1))))
> (trace fib-iter)
> (fib 3)
>(fib-iter 1 0 3)
>(fib-iter 0 1 2)
>(fib-iter 1 1 1)
>(fib-iter 1 2 0)
<2
2

你真正想要的是这样的：

> (define (fib n)
  (if (zero? n)
      0
      (fib-iter 0 1 (- n 1))))

(define (fib-iter a b count)
  (if (zero? count)
      b
      (fib-iter b (+ a b) (- count 1))))

> (trace fib-iter)
> (fib 3)
>(fib-iter 0 1 2)
>(fib-iter 1 1 1)
>(fib-iter 1 2 0)
<2
2

注意，少了一次迭代。但是，我在 fib.

过程中做了额外的工作

SICP中使用迭代过程的斐波那契数列，不能完全理解

fibonacci sequence using iterative process in SICP, cannot completely understand

lisp

scheme

loops

sicp

fibonacci