recursion - una función recursiva de Fibonacci 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 usar esto necesito sembrar x con [0 1] cuando llamo 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?

Hacer algunas lecturas me llevó a algunas formas mejores 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 ejercicio que cualquier otra cosa, ¿alguien puede 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

Aquí está la función recursiva más corta que he encontrado 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 los primeros valores de ''n'', ya que Clojure realiza la optimización de la cola en bucle / recurrencia.

Answer 2

En Clojure, en realidad, es aconsejable evitar la recursión y, en su lugar, utilizar el loop y recur formularios especiales. 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 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 de 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 sea llamado recursivamente con los argumentos proporcionados.

Answer 3

Esto es rápido y genial:

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

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

Answer 4

Para los rezagados. La 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)))

Answer 5

Para responder tu 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 función se llama definición de función multi-aria. 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 6

Por lo que vale, en estos años, esta es mi solución al problema 4Closure # 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. La razón por la que estoy haciendo los ejercicios en 4Clojure ... y reflexionar sobre los ejemplos de código del Código Rosetta 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 eso no coincidiría con su especificación. 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 toda la noción de recursión anónima es un poco emocionante, entiendo que (loop ... (recur ... la forma especial está restringida a tail-recursion ... pero sigue siendo raro sintaxis para mí).

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

Answer 7

Puedes usar el operador de aftas para limpiar un poco el número 3 (dependiendo de a quién le preguntes, a algunas personas les encanta este estilo, a otras les desagrada, solo señalo 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 el (take n) y simplemente fib función fib como una secuencia infinita.

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

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