(defn fib [n]
  (if (< n 2) 
      n
      (+ (fib (dec n)) (fib (- n 2)))))
 
(fib 10)
;=> 55
 
(time (fib 37))
;>> "Elapsed time: 10946.491718 msecs"
;=> 24157817

시간 복잡도는 O(n^2)이다.

memorize를 통해 한 번 계산한 것은 저장하여 쓰면, 계산 속도가 빨라진다.

(defn fib [n]
  (if (< n 2) 
      n
      (+ (fib (dec n)) (fib (- n 2)))))
 
(def fib (memoize fib))
 
(time (fib 37))
;>> "Elapsed time: 0.058307 msecs"
;=> 24157817
 
(fib 50)
;>> "Elapsed time: 0.774006 msecs"
;=> 12586269025
 
(fib 100)
;>> ArithmeticException integer overflow

정수 오버플로우가 발생한다.

(defn fib [n]
  (cond 
    (= n 0) 0N
    (= n 1) 1N
    :else (+ (fib (dec n)) (fib (- n 2)))))
 
(def fib (memoize fib))
 
(time (fib 100))
;>> "Elapsed time: 0.08705 msecs"
;=> 354224848179261915075N
 
(fib 1000)
;=> StackOverflowError 

스택 오버플로우가 발생한다.

(defn fib1 [n]
 (nth ((fn f [a b] (cons a (lazy-seq (f b (+ b a))))) 0N 1N) n))
 
(time (fib 1000))
;>> "Elapsed time: 1.200634 msecs"
;=> 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875N

완성!