プライムファクターを使用したClojureテール再帰

Question

私は自分自身に教材を教えようとしており、プライムファクターのKataとTDDの原則を使用しています。このようなMidjeの一連のテスト経由

：

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

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

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

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

私は次の関数を作成することができた。私はそれに次のエッジケースのテストを投げるまで

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

これは素晴らしい作品：

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

スタックオーバーフローエラーが発生します。私はこれを適切な反復ループに変える必要があることを知っていますが、私が見るすべての例はあまりにも単純すぎるようで、カウンタや数値変数に焦点を当てるだけです。これを再帰的にするにはどうすればよいですか？

ありがとうございます！

Answer 1

は、スタックオーバーフローエラーをスローせずに動作するはずです、primefactors手続きの末尾再帰の実装です：

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

トリックが結果を格納するアキュムレータのパラメータを使用しています。再帰の最後のreverseコールは、ファクタが見つかった逆の順序でリストされるかどうか気にしない限り、オプションです。

Answer 2

あなたの2番目の再帰呼び出しは既にテールポジションにありますが、それをrecurに置き換えることができます。

(primefactors n (inc candidate)) 

任意の関数のオーバーロードが暗黙のloopブロックを開き、あなたが手動で挿入する必要はありません

(recur n (inc candidate)) 

になります。このブランチはより一般的に採用されるため、これはスタックの状況をいくらか改善するはずです。その結果はconjに渡されるよう

第再帰

(primefactors (/ n candidate)) 

テール位置にありません。末尾に置くには、追加のアキュムレータ引数にプライムファクタを集めて、現在の再帰レベルの結果をconjにしてから、それぞれの呼び出しでrecurに渡す必要があります。アキュムレータを返すには、終了条件を調整する必要があります。

Answer 3

典型的な方法は、関数の引数の1つとしてアキュムレータを含めることです。あなたの関数定義に3-アリティのバージョンを追加します。

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

その後(recur ...)を呼び出し、3番目の引数として(conj acc candidate)を渡すために(conj ...)フォームを変更します。 の3つの引数をrecurに、つまり(recur (/ n candidate) 2 (conj acc candidate))に渡してください。これにより、3アリティバージョンprimefactorsが呼び出されます。

そして、(<= n 1)のケースでは、空のリストではなくaccを返す必要があります。

あなた自身で解決策を見つけられない場合は、さらに詳しく説明できますが、最初にそれを試してみるべきだと思いました。ここで

Answer 4

テール再帰、アキュムレータフリー、遅延シーケンス溶液：lazy-seqに埋め込ま

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

再帰呼び出しは、アキュムレータに頼ることなく、スタックオーバーフローのリスクを排除する、配列に反復前に評価されていません。

Answer 5

この関数は本当にtail-recursiveであってはいけません。代わりにレイジーシーケンスを構築する必要があります。結局のところ、4611686018427387902が非プライム（2で割り切れる）であることを知っていいのではないでしょうか。数字をクランチする必要はなく、他の素因数は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))))) 

上記は、あなたが投稿したアルゴリズムのかなり象徴的な翻訳です。もちろん、より良いアルゴリズムが存在しますが、これにより、正確さと怠惰が得られ、スタックのオーバーフローが修正されます。