Clojure中的递归Fibonacci函数

Question

我是clojure的新手,他想看看所有的大惊小怪.找出感受它的最佳方法是编写一些简单的代码,我想我会从Fibonacci函数开始.

我的第一个努力是:

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

要使用它,我需要在调用函数时使用[0 1]对x进行种子处理.我的问题是,如果不将它包装在一个单独的函数中,是否可以编写一个只返回元素数量的函数？

做一些阅读让我有了一些更好的方法来实现相同的功能:

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

和

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

无论如何,更多的是为了锻炼而不是其他任何东西,任何人都可以帮助我使用纯粹的递归Fibonacci函数的更好版本吗？或者可能分享更好/不同的功能？

Answer 1

先回答你的问题:

(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)))

这种类型的函数定义称为多元函数定义.您可以在此处了解更多信息:http://clojure.org/functional_programming

至于更好的Fib函数,我认为你的fib3函数非常棒,并展示了很多函数式编程概念.

Answer 2

这很快又很酷:

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

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

Answer 3

你可以使用 thrush 操作符来清理#3（取决于你问的是谁；有些人喜欢这种风格，有些人讨厌它；我只是指出这是一个选项）：

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

也就是说，我可能会提取(take n)并让该fib函数成为一个惰性无限序列。

(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

Answer 4

在Clojure中,实际上建议避免递归,而是使用loop和recur特殊形式.这将看起来像递归过程变成迭代过程,避免堆栈溢出并提高性能.

以下是使用此技术实现Fibonacci序列的示例:

(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)))))))

该loop构造采用一系列绑定,提供初始值,以及一个或多个正文形式.在任何这些正文形式中,调用recur将导致使用提供的参数递归调用循环.