Рекурсивная функция Фибоначчи в Clojure
Я новичок в 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]))))
Во всяком случае, больше ради упражнения, чем что-либо еще, может ли кто-нибудь помочь мне с лучшей версией чисто рекурсивной функции Фибоначчи? Или, возможно, использовать лучшую/различную функцию?
Ответы
Ответ 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 довольно удивительна и демонстрирует множество концепций функционального программирования.
Ответ 2
В 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
приведет к тому, что цикл будет вызываться рекурсивно с предоставленными аргументами.
Ответ 3
Это быстро и круто:
(def fib (lazy-cat [0 1] (map + fib (rest fib))))
от:
http://squirrel.pl/blog/2010/07/26/corecursion-in-clojure/
Ответ 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
Ответ 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)))
Ответ 6
Для опоздавших. Принятый ответ - это несколько сложное выражение:
(defn fib
([n]
(fib [0 1] n))
([x, n]
(if (< (count x) n)
(recur (conj x (apply + (take-last 2 x))) n)
x)))
Ответ 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
один раз, пока.
Ответ 8
Вот кратчайшая рекурсивная функция, которую я придумал для вычисления n-го числа Фибоначчи:
(defn fib-nth [n] (if (< n 2)
n
(+ (fib-nth (- n 1)) (fib-nth (- n 2)))))
Однако решение с циклом/рекурсией должно быть быстрее для всех, кроме первых нескольких значений 'n', поскольку Clojure выполняет оптимизацию хвоста в loop/recur.