una función de Fibonacci recursiva en Clojure

Question

Soy un recién llegado a clojure que quería ver de qué se trata todo este alboroto. Pensar que la mejor forma de familiarizarme con esto es escribir un código simple, pensé que comenzaría con una función de Fibonacci.

Mi primer esfuerzo fue:

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

Para utilizar esto necesito para sembrar x con [0 1] cuando se llama a la función. Mi pregunta es, sin envolverlo en una función separada, ¿es posible escribir una función única que solo tome el número de elementos para devolver?

Haciendo un poco de lectura en torno me llevó a algunos mejores maneras de lograr la misma funcionalidad:

(defn fib2 [n] 
    (loop [ x [0 1]] 
    (if (< (count x) n) 
     (recur (conj x (+ (last x) (nth x (- (count x) 2))))) 
     x))) 

y

(defn fib3 [n] 
    (take n 
    (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))) 

De todos modos, más por el bien del ejercicio que cualquier otra cosa, puede alguien ayudarme con una mejor versión de una función de Fibonacci puramente recursiva? ¿O tal vez compartir una función mejor/diferente?

Answer 1

Para contestar la primera pregunta: ¿

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

Este tipo de definición de la función se llama definición de la función multi-aridad. Puede obtener más información al respecto aquí: http://clojure.org/functional_programming

En cuanto a una mejor función Fib, creo que su función fib3 es bastante impresionante y muestra una gran cantidad de conceptos de programación funcional.

Answer 2

Esto es rápido y fresco:

(def fib (lazy-cat [0 1] (map + fib (rest fib)))) 

de: http://squirrel.pl/blog/2010/07/26/corecursion-in-clojure/

Answer 3

Una buena definición recursiva es:

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

Esto devolverá un término específico. La expansión de este para volver n primeros términos es trivial:

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

Answer 4

Usted puede utilizar el operador de la candidiasis para limpiar # 3 un poco (dependiendo de a quién le pregunte, algunas personas les gusta este estilo, algunos lo odian; estoy simplemente señalando que es una opción):

(defn fib [n] 
    (->> [0 1] 
    (iterate (fn [[a b]] [b (+ a b)])) 
    (map first) 
    (take n))) 

dicho esto, probablemente me extraer el (take n) y sólo tienen la función fib ser una secuencia infinita pereza.

(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

En Clojure en realidad es recomendable evitar la repetición y en lugar de utilizar las formas especiales loop y recur. Esto convierte lo que parece ser un proceso recursivo en uno iterativo, evitando desbordamientos de pila y mejorando el rendimiento.

Aquí hay un ejemplo de cómo le gustaría implementar una secuencia de Fibonacci con esta técnica:

(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 construcción loop toma una serie de fijaciones, que proporcionan valores iniciales, y una o más formas del cuerpo. En cualquiera de estos formularios del cuerpo, una llamada al recur hará que el bucle sea llamado recursivamente con los argumentos provistos.

Answer 6

Para los recién llegados. respuesta aceptada es una expresión un poco complicado de esto:

(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

Por lo que vale la pena, he aquí estos años, por lo tanto, aquí está mi solución a 4Closure Problem #26: Fibonacci Sequence

(fn [x] 
    (loop [i '(1 1)] 
     (if (= x (count i)) 
      (reverse i) 
      (recur 
       (conj i (apply + (take 2 i))))))) 

yo no, de ninguna manera, que este es el enfoque óptimo o más idiomático. La razón por la que estoy realizando los ejercicios en 4Clojure ... y reflexionar sobre los ejemplos de código de Rosetta Code es aprender clojure.

Por cierto, soy consciente de que la secuencia de Fibonacci incluye formalmente 0 ... que este ejemplo debería loop [i '(1 0)] ... pero que no coincidiría con sus especificaciones. ni pasan sus pruebas unitarias a pesar de cómo han etiquetado este ejercicio. Está escrito como una función recursiva anónima para cumplir con los requisitos de los ejercicios 4Clojure ... donde debe "completar el espacio en blanco" dentro de una expresión determinada. (Estoy descubriendo que la noción de recursión anónima es un poco emocionante, entiendo que el formulario especial (loop ... (recur ... está restringido a tail-recursion ... pero sigue siendo una sintaxis extraña para mí).

Tomaré el comentario de @ [Arthur Ulfeldt], con respecto a fib3 en la publicación original, en consideración también. Solo he usado Clojure's iterate una vez, hasta ahora.

Answer 8

Aquí está la función recursiva más corto que he llegado con para calcular el enésimo número de Fibonacci:

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

Sin embargo, la solución con el lazo/recursividad debe ser más rápido para todos, pero los primeros valores de ' n 'ya que Clojure optimiza la cola en bucle/recurrencia.