a recursive Fibonacci function in Clojure

Question

I'm a newcomer to clojure who wanted to see what all the fuss is about. Figuring the best way to get a feel for it is to write some simple code, I thought I'd start with a Fibonacci function.

My first effort was:

(defn fib [x, n]
  (if (< (count x) n) 
    (fib (conj x (+ (last x) (nth x (- (count x) 2)))) n)
    x))

To use this I need to seed x with [0 1] when calling the function. My question is, without wrapping it in a separate function, is it possible to write a single function that only takes the number of elements to return?

Doing some reading around led me to some better ways of achieving the same funcionality:

(defn fib2 [n]
  (loop [ x [0 1]] 
    (if (< (count x) n) 
      (recur (conj x (+ (last x) (nth x (- (count x) 2)))))
      x)))

and

(defn fib3 [n] 
  (take n 
    (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1]))))

Anyway, more for the sake of the exercise than anything else, can anyone help me with a better version of a purely recursive Fibonacci function? Or perhaps share a better/different function?

Solution 1

To answer you first question:

(defn fib
  ([n]
     (fib [0 1] n))
  ([x, n]
     (if (< (count x) n) 
       (fib (conj x (+ (last x) (nth x (- (count x) 2)))) n)
       x)))

This type of function definition is called multi-arity function definition. You can learn more about it here: http://clojure.org/functional_programming

As for a better Fib function, I think your fib3 function is quite awesome and shows off a lot of functional programming concepts.

Solution 2

This is fast and cool:

(def fib (lazy-cat [0 1] (map + fib (rest fib))))

from: http://squirrel.pl/blog/2010/07/26/corecursion-in-clojure/

Solution 3

In Clojure it's actually advisable to avoid recursion and instead use the loop and recur special forms. This turns what looks like a recursive process into an iterative one, avoiding stack overflows and improving performance.

Here's an example of how you'd implement a Fibonacci sequence with this technique:

(defn fib [n]
  (loop [fib-nums [0 1]]
    (if (>= (count fib-nums) n)
      (subvec fib-nums 0 n)
      (let [[n1 n2] (reverse fib-nums)]
        (recur (conj fib-nums (+ n1 n2)))))))

The loop construct takes a series of bindings, which provide initial values, and one or more body forms. In any of these body forms, a call to recur will cause the loop to be called recursively with the provided arguments.

Solution 4

You can use the thrush operator to clean up #3 a bit (depending on who you ask; some people love this style, some hate it; I'm just pointing out it's an option):

(defn fib [n] 
  (->> [0 1] 
    (iterate (fn [[a b]] [b (+ a b)]))
    (map first)
    (take n)))

That said, I'd probably extract the (take n) and just have the fib function be a lazy infinite sequence.

(def fib
  (->> [0 1] 
    (iterate (fn [[a b]] [b (+ a b)]))
    (map first)))

;;usage
(take 10 fib)
;;output (0 1 1 2 3 5 8 13 21 34)
(nth fib 9)
;; output  34

Solution 5

A good recursive definition is:

(def fib 
  (memoize 
   (fn [x]
       (if (< x 2) 1
       (+ (fib (dec (dec x))) (fib (dec x)))))))

This will return a specific term. Expanding this to return first n terms is trivial:

(take n (map fib (iterate inc 0)))

View more solutions