Clojure：furの名前による再帰と再帰の比較

Question

私はClojureの初心者ですが、私は4clojure.comの問題を試しています。そこで私はflattenの実装を書かなければならない練習問題を見つけました。 「通常」の再帰（適切な用語があるかどうかはわからない）とは対照的に、

は、私は基本的には末尾呼び出しの最適化の概念を理解、そしてどのようにrecurはスタックを消費しないことができます。

そして、私はここで何が起こっているかを取得しない理由です：

(defn foo1 [x] 
    (if (> x 0) 
    (do (println x) 
     (foo1 (dec x))))) 

(defn foo2 [x] 
    (if (> x 0) 
    (do (println x) 
     (recur (dec x))))) 

予想通りfoo1とfoo2の両方が機能的に同じですが、（私の場合は100000）十分な大きさのパラメータを与え、スタックオーバーフロー™はfoo1に、foo2は正常終了します。

は今、flatten問題へ上：

(defn flatten1 [ls] 
    (mapcat 
    #(if (coll? %) 
     (flatten1 %) 
     (list %)) 
    ls)) 

(defn flatten2 [ls] 
    (mapcat 
    #(if (coll? %) 
     (recur %) 
     (list %)) 
    ls)) 

テストケース：

(flatten [1 [2] 3 [4 [5 6 [7] 8]]]) 
(flatten1 [1 [2] 3 [4 [5 6 [7] 8]]]) 
(flatten2 [1 [2] 3 [4 [5 6 [7] 8]]]) 

期待される結果：'(1 2 3 4 5 6 7 8)

まあ、flatten1（それはとにかく小さな入力です）[OK]を動作します。しかし、flatten2は無期限にハングアップします。 recurは再帰ポイントをdefnに設定していませんか？関数を名前で再帰させたときの違いは何ですか？プログラムを少し変更することにより

Answer 1

あなたが問題を見ることができます：コードを実行する

(ns clj.core 
    (:require [tupelo.core :as t]) 
    (:gen-class)) 
(t/refer-tupelo) 

(defn flatten1 [ls] 
    (mapcat 
    (fn [it] 
     (println "f1: it=" it) 
     (if (coll? it) 
     (flatten1 it) 
     (list it))) 
    ls)) 

(defn flatten2 [ls] 
    (mapcat 
    (fn [it] 
     (println "f2: it=" it) 
     (if (coll? it) 
     (recur it) 
     (list it))) 
    ls)) 

(defn -main 
    [& args] 
    (newline) (println "main - 1") 
    (spyx (flatten [1 [2] 3 [4 [5 6 [7] 8]]])) 

    (newline) (println "main - 2") 
    (spyx (flatten1 [1 [2] 3 [4 [5 6 [7] 8]]])) 

    (newline) (println "main - 3") 
    (flatten2 [1 [2] 3 [4 [5 6 [7] 8]]]) 

は、この出力を生成します

main - 1 
(flatten [1 [2] 3 [4 [5 6 [7] 8]]]) => (1 2 3 4 5 6 7 8) 

main - 2 
f1: it= 1 
f1: it= [2] 
f1: it= 2 
f1: it= 3 
f1: it= [4 [5 6 [7] 8]] 
f1: it= 4 
f1: it= [5 6 [7] 8] 
f1: it= 5 
f1: it= 6 
f1: it= [7] 
f1: it= 7 
f1: it= 8 
(flatten1 [1 [2] 3 [4 [5 6 [7] 8]]]) => (1 2 3 4 5 6 7 8) 

main - 3 
f2: it= 1 
f2: it= [2] 
f2: it= [2] 
f2: it= [2] 
f2: it= [2] 
f2: it= [2] 
f2: it= [2] 
f2: it= [2] 
f2: it= [2] 

だから、それは[2]項目に立ち往生見ることができ、入力リストの2番目の要素。

recurステートメントは、元の問題の匿名形式#(if ...)である第2版の(fn [it] ...)という最も内側の関数にジャンプするだけです。

recurは、最も内側のfn/loopターゲットにのみジャンプできます。 recurを使用して内部無名関数から飛び越してflatten2に到達することはできません。内部関数にジャンプするだけなので、1 elemコレクション[2]は、mapcat呼び出しの最後にlsの値を置き換えないため、無限ループになります。

プログラミングにとって最良のアドバイスは、「簡単に保つ」ことです。再帰は、ほとんどの問題のループ/再帰より簡単です。

JVM上では、各スタックフレームにいくらかのメモリが必要です（増加するには、-Xsスイッチのドキュメントを参照してください）。多すぎるスタックフレームを使用すると、最終的にメモリが不足します（-Xmxスイッチによって制御されます）。あなたは通常、少なくとも1000のスタックフレームが利用可能であることを数えることができます（あなたのマシンのためにあなたが好きかどうかテストすることができます& params）。経験則として、再帰の深さが1000以下の場合は、loop/recurの使用について心配しないでください。