рекурсивная функция Фибоначчи в Clojure

Question

Я новичок в clojure, который хотел посмотреть, о чем идет речь. Чтобы понять, как лучше понять это, - написать простой код, я подумал, что начну с функции Фибоначчи.

Мое первое усилие было:

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

Чтобы использовать это, мне нужно заполнить x с [0 1] при вызове функции. Мой вопрос заключается в том, что, не заключая ее в отдельную функцию, можно ли написать одну функцию, которая принимает только количество возвращаемых элементов?

Чтение вокруг привело меня к некоторым лучшим способам достижения той же функциональности:

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

Во всяком случае, ради упражнения больше, чем что-либо еще, кто-нибудь может мне помочь с лучшей версией чисто рекурсивной функции Фибоначчи? Или, может быть, разделяют лучшую / другую функцию?

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

В Clojure на самом деле желательно избегать рекурсии и вместо этого использовать специальные формы loop и recur. Это превращает то, что выглядит как рекурсивный процесс, в итеративный, избегая переполнения стека и повышая производительность.

Вот пример того, как вы реализуете последовательность Фибоначчи с помощью этой техники:

(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 вызовет рекурсивный вызов цикла с предоставленными аргументами.

Answer 4

Вы можете использовать оператор молочницы, чтобы немного убрать # 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 5

Хорошее рекурсивное определение:

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

Это вернет определенный срок. Расширение этого для возврата первых n слагаемых тривиально:

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

Answer 6

Вот самая короткая рекурсивная функция, которую я придумал для вычисления n-го числа Фибоначчи:

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

Однако решение с циклом / рекурсией должно быть быстрее для всех, кроме первых нескольких значений'n', поскольку Clojure выполняет хвостовую оптимизацию в цикле / повторении.

Answer 7

Что бы это ни стоило, вот эти годы, вот мое решение 4Закрытие проблемы № 26: Последовательность Фибоначчи

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

Я, ни в коем случае, не думаю, что этоэто оптимальный или самый идиоматический подход.Вся причина, по которой я выполняю упражнения в 4Clojure ... и обдумываю примеры кода из Rosetta Code , состоит в том, чтобы выучить clojure .

Кстати, яхорошо известно, что последовательность Фибоначчи формально включает 0 ... что этот пример должен loop [i '(1 0)] ... но это не будет соответствовать их спецификации.и не сдавайте свои юнит-тесты, несмотря на то, как они пометили это упражнение.Он написан как анонимная рекурсивная функция, чтобы соответствовать требованиям для упражнений 4Clojure, где вы должны «заполнить пробел» в данном выражении.(Я нахожу, что само понятие анонимной рекурсии немного смущает ум; я получаю, что специальная форма (loop ... (recur ... ограничена хвостовой рекурсией ... но это все еще странный синтаксисмне).

Я возьму комментарий @ [Arthur Ulfeldt], касающийся fib3 в исходной публикации, также на рассмотрении.До сих пор я использовал iterate Clojure только один раз.

Answer 8

для опоздавших.Принятый ответ является несколько сложным выражением этого:

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