a recursive Fibonacci function in Clojure

问题:

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?

回答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.

回答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/

回答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.

回答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

回答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)))

回答6:

For latecomers. Accepted answer is a slightly complicated expression of this:

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

回答7:

For what it's worth, lo these years hence, here's my solution to 4Closure Problem #26: Fibonacci Sequence

(fn [x] 
    (loop [i '(1 1)]
        (if (= x (count i))
            (reverse i)
            (recur 
              (conj i (apply + (take 2 i)))))))

I don't, by any means, think this is the optimal or most idiomatic approach. The whole reason I'm going through the exercises at 4Clojure ... and mulling over code examples from Rosetta Code is to learn clojure.

Incidentally I'm well aware that the Fibonacci sequence formally includes 0 ... that this example should loop [i '(1 0)] ... but that wouldn't match their spec. nor pass their unit tests despite how they've labelled this exercise. It is written as an anonymous recursive function in order to conform to the requirements for the 4Clojure exercises ... where you have to "fill in the blank" within a given expression. (I'm finding the whole notion of anonymous recursion to be a bit of a mind bender; I get that the (loop ... (recur ... special form is constrained to tail-recursion ... but it's still a weird syntax to me).

I'll take @[Arthur Ulfeldt]'s comment, regarding fib3 in the original posting, under consideration as well. I've only used Clojure's iterate once, so far.

回答8:

Here is the shortest recursive function I've come up with for computing the nth Fibonacci number:

(defn fib-nth [n] (if (< n 2)
                n
                (+ (fib-nth (- n 1)) (fib-nth (- n 2)))))

However, the solution with loop/recursion should be faster for all but the first few values of 'n' since Clojure does tail-end optimization on loop/recur.