6

私は自分自身で clojure を学ぼうとしており、そうするために Prime Factors 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))

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

ありがとう！

4

5 に答える 5

12

プロシージャの末尾再帰実装を次に示し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してください。ただし、因子が見つかった逆の順序でリストされてもかまわない限りです。

于 2012-03-04T16:42:08.843 に答える
5

2 番目の再帰呼び出しは既に末尾の位置にあります。それを に置き換えるだけrecurです。

(primefactors n (inc candidate))

になる

(recur n (inc candidate))

関数のオーバーロードは暗黙的なloopブロックを開くため、手動で挿入する必要はありません。この分岐がより一般的に行われるため、これにより、スタックの状況が多少改善されるはずです。

最初の再帰

(primefactors (/ n candidate))

結果が に渡されるため、 は末尾の位置にありませんconj。conj末尾の位置に配置するには、現在の再帰レベルの結果を追加のアキュムレータ引数で収集し、recur呼び出しごとに渡す必要があります。そのアキュムレータを返すには、終了条件を調整する必要があります。

于 2012-03-04T16:09:16.337 に答える
5

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

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

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

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

自分で解決策を見つけられない場合は、さらに詳しく説明できますが、最初に解決策を試す機会を与えるべきだと思いました.

于 2012-03-04T16:09:30.303 に答える
2

末尾再帰、アキュムレータ不要、遅延シーケンス ソリューション:

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

に埋め込まれた再帰呼び出しはlazy-seq、シーケンスの反復前に評価されないため、アキュムレータに頼ることなくスタック オーバーフローのリスクが排除されます。

于 2013-11-28T20:13:04.600 に答える