Recursion in JVM

1. 素朴な再帰

(defn stack-consuming-fibo [n]
(cond
(= n 0) 0
(= n 1) 1
:else (+ (stack-consuming-fibo (- n 1))
(stack-consuming-fibo (- n 2)))))
sample.core=> (stack-consuming-fibo 10000)StackOverflowError clojure.lang.Numbers$LongOps.combine (Numbers.java:419)

2. 末尾再帰

(defn tail-fibo [n]
(letfn [(fib
[current next n]
(if (zero? n)
current
(fib next (+ current next) (dec n))))]
(fib 0N 1N n)))
sample.core=> (tail-fibo 10000)StackOverflowError   clojure.lang.BigInt.add (BigInt.java:148)

3. recurを使った自己再帰

(defn recur-fibo [n]
(letfn [(fib
[current next n]
(if (zero? n)
current
(recur next (+ current next) (dec n))))]
(fib 0N 1N n)))

4. 遅延シーケンス

(defn lazy-seq-fibo
([]
(concat [0 1] (lazy-seq-fibo 0N 1N)))
([a b]
(let [n (+ a b)]
(lazy-seq
(cons n (lazy-seq-fibo b n))))))
sample.core=> (nth (lazy-seq-fibo) 10)
55N

--

--

Software engineer

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store