một hàm Fibonacci đệ quy trong Clojure

Question

Tôi là một người mới đến clojure, những người muốn xem tất cả những gì phiền phức. Tìm cách tốt nhất để có được một cảm giác cho nó là viết một số mã đơn giản, tôi nghĩ tôi sẽ bắt đầu với một hàm Fibonacci.

nỗ lực đầu tiên của tôi là:

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

Để sử dụng này, tôi cần để gieo rắc x với [0 1] khi gọi hàm. Câu hỏi của tôi là, không bao bọc nó trong một hàm riêng biệt, có thể viết một hàm duy nhất chỉ lấy số lượng các phần tử cần trả về không?

Làm một số đọc xung quanh dẫn tôi đến một số những cách tốt hơn để đạt được các funcionality cùng:

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

và

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

Dù sao, hơn vì lợi ích của tập thể dục hơn bất cứ điều gì khác, có thể bất cứ ai giúp tôi với một phiên bản tốt hơn của một hàm Fibonacci hoàn toàn đệ quy? Hoặc có lẽ chia sẻ một chức năng tốt hơn/khác nhau?

Answer 1

Để trả lời bạn câu hỏi đầu tiên:

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

Đây là loại định nghĩa hàm được gọi định nghĩa hàm đa arity. Bạn có thể tìm hiểu thêm về điều này tại đây: http://clojure.org/functional_programming

Đối với chức năng Fib tốt hơn, tôi nghĩ chức năng fib3 của bạn khá tuyệt vời và thể hiện rất nhiều khái niệm lập trình chức năng.

Answer 2

Đây là nhanh và hấp dẫn:

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

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

Answer 3

Một tốt định nghĩa đệ quy là:

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

này sẽ trả về một thuật ngữ cụ thể. Mở rộng này để trả lại về n đầu tiên là tầm thường:

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

Answer 4

Bạn có thể sử dụng toán tử nấm để làm sạch # 3 một chút (tùy thuộc vào người bạn hỏi, một số người thích phong cách này, một số ghét nó; tôi chỉ cần chỉ ra nó là một tùy chọn):

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

Điều đó nói rằng, tôi có thể trích xuất các (take n) và chỉ có fib chức năng là một chuỗi vô hạn lười biếng.

(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

Trong Clojure nó thực sự nên tránh đệ quy và thay vào đó sử dụng các hình thức đặc biệt loop và recur. Điều này biến những gì trông giống như một quá trình đệ quy vào một quá trình lặp đi lặp lại, tránh tràn ngăn xếp và cải thiện hiệu suất.

Dưới đây là một ví dụ về cách bạn muốn thực hiện một dãy Fibonacci với kỹ thuật này:

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

Các loop xây dựng mất một loạt các cam kết ràng buộc, trong đó cung cấp các giá trị ban đầu, và một hoặc các hình thức thêm mạnh mẽ. Trong bất kỳ dạng nào trên cơ thể, một cuộc gọi đến recur sẽ làm cho vòng lặp được gọi là đệ quy với các đối số được cung cấp.

Answer 6

Đối với những người đến trễ. Câu trả lời được chấp nhận là một biểu hiện hơi phức tạp về điều này:

(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

Đối với những gì nó có giá trị, lo những năm này vì thế, đây là giải pháp của tôi để 4Closure Problem #26: Fibonacci Sequence

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

tôi không, bởi bất kỳ phương tiện nào, nghĩ rằng đây là cách tiếp cận tối ưu hoặc thành ngữ nhất. Toàn bộ lý do tôi sẽ trải qua các bài tập tại 4Clojure ... và nghiền ngẫm các ví dụ mã từ Rosetta Code là tìm hiểu clojure.

Ngẫu nhiên tôi nhận thức được rằng dãy Fibonacci chính thức bao gồm 0 ... ví dụ này nên loop [i '(1 0)] ... nhưng điều đó sẽ không khớp với thông số của chúng. cũng không vượt qua các bài kiểm tra đơn vị của họ mặc dù họ đã dán nhãn bài tập này như thế nào. Nó được viết dưới dạng một hàm đệ quy ẩn danh để phù hợp với các yêu cầu cho bài tập 4Clojure ... nơi bạn phải "điền vào chỗ trống" trong một biểu thức đã cho. (Tôi đang tìm kiếm toàn bộ khái niệm đệ quy nặc danh để có một chút tâm trí bender; Tôi nhận được rằng hình thức đặc biệt (loop ... (recur ... bị ràng buộc để tail-recursion ... nhưng nó vẫn là một cú pháp lạ đối với tôi).

Tôi sẽ nhận nhận xét của [Arthur Ulfeldt] về fib3 trong bài đăng gốc, cũng đang được xem xét. Tôi đã chỉ sử dụng iterate của Clojure một lần, cho đến nay.

Answer 8

Dưới đây là hàm đệ quy ngắn nhất tôi đã đi lên với để tính số Fibonacci thứ n:

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

Tuy nhiên, giải pháp với vòng/đệ quy nên nhanh hơn cho tất cả ngoại trừ một vài giá trị đầu tiên của ' n 'kể từ khi Clojure thực hiện tối ưu hóa đuôi trên vòng lặp/lặp lại.