Подтвердить что ты не робот

Рекурсивная функция Фибоначчи в 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]))))

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

4b9b3361

ОТВЕТЫ

Ответ 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 приведет к тому, что цикл будет вызываться рекурсивно с предоставленными аргументами.

Ответ 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.