Как я могу сгенерировать последовательность Фибоначчи с помощью Clojure?

(ns src.helloworld)

(defn fibonacci[a b] (println a b (fibonacci (+ b 1) a + b)))

(fibonacci 0 1)

Я новичок в функциональном программировании и решил начать изучение Clojure, так как он сильно отличается от C#. Я хотел бы расширить свой кругозор.

Вот ошибка, которую я получаю:

Clojure 1.2.0
java.lang.IllegalArgumentException:
Wrong number of args (4) passed to:
helloworld$fibonacci
(helloworld.clj:0) 1:1 user=>
#<Namespace src.helloworld> 1:2 src.helloworld=>

Математические задачи никогда не были моей сильной стороной, и я никогда не делал ничего, что могло бы манипулировать числами, как это, поэтому я хотел бы услышать ваше руководство.

Пожалуйста, не давайте мне все решение.

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


clojure fibonacci
person Only Bolivian Here    schedule 16.04.2011    source источник

Ответы (5)


arrow_upward
1
arrow_downward

Другие ответы объясняют вам ошибку в вашем вызове функции. После исправления этого вы должны изучить использование loop/recur, которое будет выполнять оптимизацию хвостового вызова и, следовательно, не использовать стек для каждого рекурсивного вызова. Было бы довольно сложно привести пример, не дав вам всего: -/ Вот еще один поток, в котором они вычисляют факториал с использованием рекурсии в clojure: Factorial

person jberg    schedule 16.04.2011
comment
Гораздо проще превратить простую рекурсивную функцию, такую ​​как !, в версию с хвостовой рекурсией, чем сделать это для fibonacci, которая имеет два самовызова. Вы больше не можете делать это механически; вместо этого вы должны воспользоваться специфическими для предметной области знаниями о том, как выглядит дерево рекурсии Фибоначчи. В данном случае это возможно, но не для каждой дважды рекурсивной функции. - person amalloy; 16.04.2011
comment
@amalloy: в функции fibonacci Серджио есть только один рекурсивный вызов. - person sepp2k; 16.04.2011

arrow_upward
4
arrow_downward 

(fibonacci (+ b 1) a + b)

Здесь вы вызываете функцию fibonacci с четырьмя аргументами: результат (+ b 1), значение переменной a, функция + и значение переменной b. Поскольку fibonacci было определено так, чтобы принимать только два аргумента, вы получаете ошибку, которую делаете.

Как только вы это исправите, вы получите ошибку переполнения стека, не видя никакого вывода. Это потому, что вы поместили рекурсивный вызов fibonacci в качестве аргумента println. Таким образом, он попытается выполнить рекурсивный вызов перед выполнением println. Поскольку рекурсия бесконечна, вызов println никогда не произойдет. Что вам нужно сделать, так это сначала напечатать число, а затем рекурсивно вызвать fibonacci.

Как только вы это сделаете, программа напечатает много чисел, но в конце концов стек все равно переполнится. Это связано с тем, что clojure не оптимизирует хвостовые вызовы, поэтому даже при использовании хвостовой рекурсии бесконечная рекурсия вызовет переполнение стека. Чтобы предотвратить это, используйте форму recur вместо обычной рекурсии.

В дополнение к этим точкам ваша программа будет печатать неправильные числа, так как вы неправильно реализовали последовательность Фибоначчи.

person sepp2k    schedule 16.04.2011

arrow_upward
3
arrow_downward

Вот подсказка о том, почему вы получили ошибку, которую вы сделали. Вы передали следующие четыре аргумента fibonacci:

  • (+ b 1)
  • a
  • +
  • b.

Это все равно не даст вам работающую функцию, и вот один намек на это: что когда-либо заставит код прекратить выполнение и вернуть значение пользователю?

person dfan    schedule 16.04.2011

arrow_upward
1
arrow_downward

Когда я изучал некоторые подобные кодовые ката, я нашел этот сайт очень полезным. Ката кодирования. У них есть последовательность вымысла как ката желтого пояса. У них также есть решения, опубликованные людьми на нескольких языках (Clojure — один из них). Таким образом, вы сможете сравнить свой ответ с другими и посмотреть, сможете ли вы подобрать какие-либо советы или способы ведения дел получше.

person carinmeier    schedule 16.04.2011

arrow_upward
0
arrow_downward

Когда вы закончите, вы можете взглянуть на решение Фибоначчи Кристофа Гранда в Programming Clojure Стью Хэллоуэя. Это самое элегантное решение, которое я видел. Это находится на странице 137 в 1-м издании (так как я слышал, что будет 2-е издание).

person Julien Chastang    schedule 26.05.2011