une récursif de la fonction de Fibonacci en Clojure
je suis un nouveau venu à clojure qui voulait voir ce que tout ce tapage est. Trouver la meilleure façon d'avoir une idée de ce que C'est est d'écrire un code simple, j'ai pensé que je commencerais avec une fonction Fibonacci.
mon premier effort a été:
(defn fib [x, n]
(if (< (count x) n)
(fib (conj x (+ (last x) (nth x (- (count x) 2)))) n)
x))
pour utiliser ceci je dois semer x avec [0 1] lors de l'appel de la fonction. Ma question est, sans l'enveloppant dans une fonction distincte, est-il possible d'écrire une fonction qui ne prend que le nombre de les éléments de retour?
en lisant un peu autour de moi, j'ai trouvé de meilleures façons d'atteindre la même fonctionnalité:
(defn fib2 [n]
(loop [ x [0 1]]
(if (< (count x) n)
(recur (conj x (+ (last x) (nth x (- (count x) 2)))))
x)))
et
(defn fib3 [n]
(take n
(map first (iterate (fn [[a b]] [b (+ a b)]) [0 1]))))
quoi qu'il en soit, plus pour le plaisir de l'exercice que toute autre chose, est-ce que quelqu'un peut m'aider avec une meilleure version d'une fonction Fibonacci purement récursive? Ou peut-être partager une fonction meilleure/différente?
8 réponses
pour vous répondre première question:
(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)))
ce type de définition de fonction est appelée définition de fonction multi-arité. Vous pouvez en savoir plus ici: http://clojure.org/functional_programming
quant à une meilleure fonction Fib, je pense que votre fonction fib3 est tout à fait impressionnant et montre un grand nombre de concepts de programmation fonctionnelle.
dans Clojure, il est conseillé d'éviter la récursion et d'utiliser plutôt les formulaires spéciaux loop et recur . Cela transforme ce qui ressemble à un processus récursif en un processus itératif, en évitant les débordements de la pile et en améliorant les performances.
voici un exemple de la façon dont vous mettriez en œuvre une séquence de Fibonacci avec cette technique:
(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)))))))
la construction loop prend une série de reliures, qui fournissent des valeurs initiales, et une ou plusieurs formes du corps. Dans l'une de ces formes de corps, un appel à recur provoquera l'appel récursif de la boucle avec les arguments fournis.
C'est rapide et frais:
(def fib (lazy-cat [0 1] (map + fib (rest fib))))
de l': http://squirrel.pl/blog/2010/07/26/corecursion-in-clojure /
vous pouvez utiliser l'opérateur thrush pour nettoyer un peu le #3 (selon qui vous demandez; certaines personnes aiment ce style, d'autres le détestent; Je ne fais que souligner que c'est une option):
(defn fib [n]
(->> [0 1]
(iterate (fn [[a b]] [b (+ a b)]))
(map first)
(take n)))
cela dit, je vais probablement extraire le (take n) et juste avoir la fonction fib être une séquence infinie paresseuse.
(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
une bonne définition récursive est:
(def fib
(memoize
(fn [x]
(if (< x 2) 1
(+ (fib (dec (dec x))) (fib (dec x)))))))
ceci renvoie un terme spécifique. Étendre cela pour rendre n premiers termes est trivial:
(take n (map fib (iterate inc 0)))
pour les retardataires. Accepté réponse est un peu compliqué expression:
(defn fib
([n]
(fib [0 1] n))
([x, n]
(if (< (count x) n)
(recur (conj x (apply + (take-last 2 x))) n)
x)))
pour ce que ça vaut, voici donc ma solution pour 4closure Problem #26: Fibonacci Sequence
(fn [x]
(loop [i '(1 1)]
(if (= x (count i))
(reverse i)
(recur
(conj i (apply + (take 2 i)))))))
Je ne pense pas que ce soit l'approche optimale ou la plus idiomatique. La raison pour laquelle je fais les exercices à 4Clojure ... et réfléchir sur les exemples de code de code Rosetta est d'apprendre clojure .
incidemment je suis bien conscient que la séquence de Fibonacci inclut formellement 0 ... que cet exemple devrait loop [i '(1 0)] ... mais ça ne correspondrait pas à leurs spécifications. ils ne passent pas non plus le test de l'unité malgré la façon dont ils ont étiqueté cet exercice. Il est écrit comme une fonction de récursion anonyme afin de se conformer aux exigences pour les exercices 4Clojure ... où vous devez "remplir le vide" dans une expression donnée. (Je trouve que toute la notion de récursion anonyme est un peu un trouble de l'esprit; je comprends que le La forme spéciale (loop ... (recur ... est limitée à queue-recursion ... mais c'est toujours une syntaxe bizarre pour moi).
je vais prendre @[Arthur Ulfeldt] ' s commentaire, concernant fib3 dans l'affichage original, à l'étude aussi bien. Je n'ai utilisé le iterate de Clojure qu'une fois, jusqu'à présent.
Voici la fonction récursive la plus courte que j'ai trouvée pour calculer le nième nombre de Fibonacci:
(defn fib-nth [n] (if (< n 2)
n
(+ (fib-nth (- n 1)) (fib-nth (- n 2)))))
cependant, la solution avec boucle/récursion devrait être plus rapide pour toutes les valeurs sauf les premières de 'n' puisque Clojure fait l'optimisation de queue sur boucle/récur.