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

Question

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

Моя первая работа была:

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

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

Делая некоторое чтение вокруг привел меня к некоторым более эффективным способам достижения того же funcionality:

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

Этот тип определения функции называется мульти-Arity определение функции. Вы можете узнать больше об этом здесь: 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

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

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

Это будет возвращать определенный срок. Расширение для возврата первых п членов тривиально:

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

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

В 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 6

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

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

Answer 7

Для чего это стоит, вот эти годы отсюда, вот мое решение 4Closure Problem #26: Fibonacci Sequence

(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 ... ограничена tail-recursion ... но это все еще странный синтаксис для меня).

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

Answer 8

Здесь кратчайшее рекурсивная функция Я придумал для вычисления п-й ряд Фибоначчи:

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

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