斐波那契数列及其优化

在数学上，斐波那契数列是以递归的方法来定义：

用文字来说，就是斐波那契数列由0和1开始，之后的斐波那契系数就是由之前的两数相加而得出。首几个斐波那契系数是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

递归

(define (fib n)
  (if (< n 2) n
      (+ (fib (- n 1))
         (fib (- n 2)))))

迭代

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

  (fib-iter 1 0 n))

// 测试
(fib 8)
(fib 10)
// 输出
21
55

JavaScript版

function fib(n) {
  let [a, b] = [1, 0]
  while (n-- !== 0) {
    [a, b] = [a + b, a]
  }
  return b
}

以对数步数求出斐波那契数的巧妙算法

原题

(define (square x) (* x x))

(define (fib n)
  (define (fib-iter a b p q count)
    (cond ((= count 0) b)
          ((even? count) (fib-iter a
                                   b
                                   (+ (square p) (square q))
                                   (+ (* 2 p q) (square q))
                                   (/ count 2)))
          (else (fib-iter (+ (* b q) (* a q) (* a p))
                          (+ (* b p) (* a q))
                          p
                          q
                          (- count 1)))))

  (fib-iter 1 0 0 1 n))