Đón lại Clojure với các yếu tố chính

Question

Tôi đang cố gắng tự dạy mình clojure và tôi đang sử dụng các nguyên tắc của các yếu tố chính Kata và TDD để làm như vậy.

Qua một loạt các xét nghiệm Midje như thế này:

(fact (primefactors 1) => (list)) 

(fact (primefactors 2) => (list 2)) 

(fact (primefactors 3) => (list 3)) 

(fact (primefactors 4) => (list 2 2)) 

tôi đã có thể để tạo ra các chức năng sau:

(defn primefactors 
    ([n] (primefactors n 2)) 
    ([n candidate] 
     (cond (<= n 1) (list) 
       (= 0 (rem n candidate)) (conj (primefactors (/ n candidate)) candidate) 
       :else (primefactors n (inc candidate)) 
     ) 
    ) 
) 

này hoạt động tuyệt vời cho đến khi tôi ném bài kiểm tra trường hợp cạnh sau vào nó:

(fact (primefactors 1000001) => (list 101 9901)) 

Tôi kết thúc với lỗi tràn ngăn xếp. Tôi biết tôi cần phải biến điều này thành một vòng lặp lại thích hợp nhưng tất cả các ví dụ mà tôi thấy có vẻ quá đơn giản và chỉ trỏ đến biến số truy cập hoặc số làm trọng tâm. Làm thế nào để làm cho đệ quy này?

Cảm ơn!

Answer 1

Dưới đây là một cái đuôi thực hiện đệ quy của thủ tục primefactors, cần làm việc mà không cần ném một lỗi stack overflow:

(defn primefactors 
    ([n] 
    (primefactors n 2 '())) 
    ([n candidate acc] 
    (cond (<= n 1) (reverse acc) 
      (zero? (rem n candidate)) (recur (/ n candidate) candidate (cons candidate acc)) 
      :else (recur n (inc candidate) acc)))) 

Bí quyết là sử dụng một tham số ắc để lưu trữ kết quả. Lưu ý rằng cuộc gọi reverse ở cuối đệ quy là tùy chọn, miễn là bạn không quan tâm nếu các yếu tố được liệt kê theo thứ tự ngược lại, chúng được tìm thấy.

Answer 2

Cuộc gọi đệ quy thứ hai của bạn đã ở vị trí đuôi, bạn chỉ có thể thay thế bằng recur.

(primefactors n (inc candidate)) 

trở thành

(recur n (inc candidate)) 

Bất kỳ chức năng quá tải sẽ mở ra một loop khối tiềm ẩn, do đó bạn không cần phải chèn đó bằng tay. Điều này nên đã cải thiện tình hình ngăn xếp một chút, vì nhánh này sẽ được phổ biến hơn.

Các đệ quy đầu tiên

(primefactors (/ n candidate)) 

không phải là ở vị trí đuôi như kết quả của nó được chuyển cho conj. Để đặt nó ở vị trí đuôi, bạn sẽ cần thu thập các thừa số nguyên tố trong một đối số cộng dồn bổ sung mà bạn có kết quả từ mức đệ quy hiện tại và sau đó chuyển đến recur trên mỗi lệnh gọi. Bạn sẽ cần điều chỉnh điều kiện chấm dứt của mình để trả lại bộ tích lũy đó.

Answer 3

Cách điển hình là bao gồm bộ tích lũy làm một trong các đối số hàm. Thêm một phiên bản 3-arity để định nghĩa hàm của bạn:

(defn primefactors 
    ([n] (primefactors n 2 '())) 
    ([n candidate acc] 
    ...) 

Sau đó, thay đổi hình thức (conj ...) gọi (recur ...) và vượt qua (conj acc candidate) như là đối số thứ ba. Đảm bảo bạn vượt qua các đối số ba đối số recur, tức là (recur (/ n candidate) 2 (conj acc candidate)), để bạn gọi phiên bản 3-arity là primefactors.

Và trường hợp (<= n 1) cần trả lại acc thay vì danh sách trống.

Tôi có thể đi vào chi tiết hơn nếu bạn không thể tìm ra giải pháp cho chính mình, nhưng tôi nghĩ tôi nên cho bạn cơ hội để cố gắng giải quyết nó trước.

Answer 4

Một đuôi đệ quy, ắc-miễn phí, lười biếng-chuỗi giải pháp: các cuộc gọi

(defn prime-factors [n] 
    (letfn [(step [n div] 
      (when (< 1 n) 
       (let [q (quot n div)] 
       (cond 
        (< q div)   (cons n nil) 
        (zero? (rem n div)) (cons div (lazy-step q div)) 
        :else    (recur n (inc div)))))) 
      (lazy-step [n div] 
      (lazy-seq 
       (step n div)))] 
    (lazy-step n 2))) 

Recursive nhúng trong lazy-seq không đánh giá trước khi lặp đi lặp lại theo trình tự, loại bỏ nguy cơ chồng tràn mà không cần đến một ắc .

Answer 5

Chức năng này thực sự không nên là đệ quy đuôi: thay vào đó nó sẽ tạo một chuỗi lười. Sau khi tất cả, nó sẽ không được tốt đẹp để biết rằng 4611686018427387902 là phi tố (nó chia hết cho hai), mà không cần phải crunch các con số và thấy rằng nguyên tố khác của nó là 2305843009213693951?

(defn prime-factors 
    ([n] (prime-factors n 2)) 
    ([n candidate] 
    (cond (<= n 1)() 
      (zero? (rem n candidate)) (cons candidate (lazy-seq (prime-factors (/ n candidate) 
                       candidate))) 
      :else (recur n (inc candidate))))) 

Ở trên là bản dịch khá phi lý tưởng của thuật toán bạn đã đăng; tất nhiên thuật toán tốt hơn tồn tại, nhưng điều này giúp bạn có được sự chính xác và lười biếng, và sửa lỗi tràn ngăn xếp.