-
-
Save r00k/4658025 to your computer and use it in GitHub Desktop.
(defn fib [n] | |
(take n (map first (iterate (fn [[a b]] [b (+ a b)]) [1 1])))) | |
(fib 5) => (1 1 2 3 5) |
More lazy sequence porn: http://stackoverflow.com/questions/2213791/thinking-in-lazy-sequences
That's really pretty =)
I'm also fond of the Haskell version:
fibs = (1:1:zipWith (+) fibs (tail fibs))
fib n = take n fibs
My coffeescript version per https://twitter.com/raganwald/status/295968805123944448
fib = (x) -> it[0] for it in [a = [1, 1]].concat(while --x then a = [a[1], a[0] + a[1]])
... which is neither recursive nor elegant ;)
Cool!
http://www.4clojure.com/problems is your go-to place for Clojure porn. Just follow the top users and see their solutions after you've solved each problem yourself.
The beauty of the solution:
(def fibs (map first (iterate (fn [[a b]] [b (+ a b)]) [0N 1N])))
is that the Fibonacci numbers are a sequence of all of the Fibonacci numbers rather than some function that calculates the nth Fibonacci number. Therefore, the way to interact with fibs is to just reach in and get what you want:
(first fibs)
;;=> 0
(nth fibs 100)
;;=> 354224848179261915075N
(nth fib 1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875N
If you again want to get the value of the 100th Fibonacci number then just grab it again, Clojure will not calculate it again. I Fibonacci function is kinda cool, but all of the Fibonacci numbers is way cooler.
You can do something similar in JS though it's not as pretty:
function allfibs(end) {
var x = 0, y = 1, count = 1;
yield 1;
while (count++ < end) {
[x,y] = [y,x + y];
yield y;
}
}
function fibs(x) {
return [ i for (i in allfibs(x)) ]
}
fibs(5) // [1,1,2,3,5]
Wouldn't be hard to write some library functions like take() to get the nth element etc.
Found, not created, btw.
Original here: http://stackoverflow.com/questions/8939970/a-recursive-fibonacci-function-in-clojure