Clojure：通過fn名稱的遞歸與遞歸

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工程確定（這是一個很小的輸入反正）。但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]項目時，輸入列表的第二個元素。

失敗的原因是recur語句只跳回到最裏面的功能，這是在第二版形式(fn [it] ...)在你原來的問題匿名形式#(if ...)。

請注意，recur只能「跳轉」到最內層的fn/loop目標。您不能使用recur跳出您的內部匿名功能以達到flatten2。由於它只跳轉到內部函數，1-elem集合[2]不會替代mapcat調用結束時的ls值，因此您將獲得無限循環。

任何編程的最佳建議是「保持簡單」。對於大多數問題，遞歸比循環/重複更簡單。

在JVM上，每個堆棧幀都需要一些內存（請參閱有關-Xs開關的文檔以增加內存）。如果使用太多堆棧幀，最終會導致內存不足（由-Xmx開關控制）。您通常應該能夠依靠至少1000個可用的堆棧框架（您可以測試您的機器是否適用於您的機器& params）。因此，根據經驗法則，如果您的遞歸深度爲1000或更小，請不要擔心使用loop/recur。