Tail Recursion

两个 fibonacci 函数

第一个不是尾递归的，第二个是。比较一下速度。

(define fibonacci
  (lambda (n)
    (let fib ((i n))
      (cond
        ((= i 0) 0)
        ((= i 1) 1)
        (else (+ (fib (- i 1)) (fib (- i 2))))))))

(fibonacci 30)

(define fibonacci1
  (lambda (n)
    (if (= n 0)
        0
        (let fib ((i n) (a1 1) (a2 0))
          (if (= i 1)
              a1
              (fib (- i 1) (+ a1 a2) a1))))))

(fibonacci1 30)

发现第一个在 (fibonacci 35) 的时候已经慢得无法忍受。因为这里 的递归调用成指数增长。

而第二个版本却很快。因为它是尾递归，调用次数是线性增长。