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
Takanori Ishibashi

Takanori Ishibashi

Software engineer

More from Medium

What is C Programming?

What is C programming?

Modern C++ in Advent of Code: Day18

The concept of recursion

Rosetta Code: Object Oriented Programming Examples