23

リストを再帰的に逆にしようとしていますが Can only recur from tail position、実行中です。これは正確には何を意味し、コードが機能するようにどのように改善できますか?

(defn recursive-reverse [coll]
  (loop [coll coll]
    (if (< (count coll) 2) '(coll)
      (conj (first coll) (recur (rest coll)))
      )))

編集

Oscar のソリューションの出力。リストでは機能しますが、ベクトルでは機能しませんか?

user=> (= (recursive-reverse [1 2 3 4 5]) (recursive-reverse '(1 2 3 4 5)))
false
user=> (= '(1 2 3 4 5) [1 2 3 4 5])
true
user=> (recursive-reverse [1 2 3 4 5])
[1 2 3 4 5]
user=> (recursive-reverse '(1 2 3 4 5))
(5 4 3 2 1)
4

3 に答える 3

23

このエラーは、関数の再帰部分の最後の式としてCan only recur from tail position呼び出していないことを意味します。実際、コードでは最後の式です。recurconj

コードを機能させるためのいくつかの改善:

  • コレクションの長さが 2 未満かどうかを比較するのではなく、基本ケースとしてコレクションが空であるかどうかを尋ねます。
  • conj要素ではなく、最初のパラメーターのコレクションを受け取ります
  • cons代わりに使用することをお勧めします(ドキュメントconjによると、コレクションの具体的なタイプに応じて、さまざまな場所に新しい要素を追加します)。このようにして、入力コレクションがリストまたはベクターの場合、返されるコレクションは逆になります (ただし、入力コレクションのタイプに関係なく、返されるコレクションのタイプは常に になります)。clojure.lang.Cons
  • は、実際のコレクションではなく'(coll)、単一の要素 (記号coll) を持つリストであることに注意してください。
  • リストを正しく反転するには、入力リストを反復処理し、各要素を出力リストの先頭に追加する必要があります。これにはアキュムレータ パラメータを使用します
  • recur関数の末尾位置での末尾再帰呼び出しを利用するため。このようにして、各再帰呼び出しは一定量のスペースを取り、スタックは無限に大きくなりません

これがあなたが目指していたものだと思います：

(defn recursive-reverse [coll]
  (loop [coll coll
         acc  (empty coll)]
        (if (empty? coll)
            acc
            (recur (rest coll) (cons (first coll) acc)))))
于 2012-06-02T18:22:21.113 に答える
7

Clojure では末尾の位置からのみ recur を呼び出すことができます。これは言語の設計の一部であり、JVM に関連する制限です。

recur を使用せずに (再帰を使用して) 関数名を呼び出すことができ、遅延シーケンスを使用するかどうかなど、プログラムの構造によっては、スタックが爆発しない場合があります。しかし、recur を使用した方がよいでしょう。recur で loop を使用すると、いくつかのローカル バインドが可能になります。

これは、再帰なしで再帰が使用されている4Clojure.comの例です。

(fn flt [coll]
  (let [l (first coll) r (next coll)]
    (concat 
      (if (sequential? l)
        (flt l)
        [l])
      (when (sequential? r)
        (flt r)))))
于 2012-06-02T17:18:09.867 に答える
2

コードを機能させる最も簡単な方法は、代わりに関数名を使用することですrecur。

(defn recursive-reverse [coll]
  (loop [coll coll]
    (if (< (count coll) 2) '(coll)
      (conj (first coll) (recursive-reverse (rest coll)))
      )))

もちろん、コールスタックが巨大になり、十分な大きさの入力に対してエラーが発生します。

recursive-reverse の末尾呼び出しに適したバージョンを作成する別の方法を次に示します。

(defn recursive-reverse [s]
  (letfn [
    (my-reverse [s c]
      (if (empty? s)
        c
        (recur (rest s) (conj c (first s)))))]
    (my-reverse s '())))

入力リストの先頭からアイテムを取り出し、アキュムレータ リストの先頭に追加します。

「テール位置」recurは、関数が戻る前に関数によって最後に実行されることを意味します。これは、自分自身を呼び出してから戻るまでの間に関数によってまだ作業が行われている「自然再帰」ソリューションとは異なります。

于 2012-06-02T19:40:08.440 に答える