una función recursiva de Fibonacci en Clojure

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

Aquí hay un ejemplo de cómo implementaría 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 enlaces, que proporcionan valores iniciales, y una o más formas de cuerpo. En cualquiera de estas formas corporales, una llamada a recur hará que el bucle se llame recursivamente con los argumentos proporcionados.

Esto es rápido y fresco:

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

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

Puedes usar el operador thrush para limpiar #3 un poco (dependiendo de a quién le preguntes; algunas personas aman este estilo, otras lo odian; solo estoy 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 extraería la (take n) y solo tendría la función fib ser una secuencia infinita perezosa.

(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

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. Expandir esto para devolver los primeros n términos es trivial:

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

Para los recién llegados. Respuesta aceptada es una expresión ligeramente complicada 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)))

Por lo que vale, lo estos años por lo tanto, aquí está mi solución a 4problema de cierre # 26: Secuencia de Fibonacci

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

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

Por cierto, soy muy consciente de que la secuencia de Fibonacci incluye formalmente 0 ... que este ejemplo debe loop [i '(1 0)] ... pero eso no coincidiría con sus especificaciones. ni pasar sus pruebas unitarias a pesar de cómo han etiquetado este ejercicio. Se escribe como una función recursiva anónima con el fin de cumplir con los requisitos para los ejercicios 4Clojure ... donde tienes que "llenar el espacio en blanco" dentro de una expresión dada. (Estoy encontrando que toda la noción de recursión anónima es un poco un doblador mental; entiendo que la forma especial (loop ... (recur ... está limitada a recursión de cola... pero sigue siendo una sintaxis extraña para me).

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

Aquí está la función recursiva más corta que se me ocurrió 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 bucle/recursión debería ser más rápida para todos menos los primeros valores de 'n' ya que Clojure hace una optimización de cola en bucle/recursión.