在数学上，斐波那契数列是以递归的方法来定义：
用文字来说，就是斐波那契数列由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))
