recursion - 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 语句只跳回到最里面的函数，也就是你原来问题中的匿名形式 #(if ...) ，在第二个版本中的形式为 (fn [it] ...)。

请注意，recur 只能“跳转”到最内层的 fn/loop 目标。您不能使用 recur 跳出内部匿名函数到达 flatten2。由于它只跳转到内部函数，因此 1-elem 集合 [2] 不会替换 mapcat 末尾的 ls 值调用，因此你得到了无限循环。

对于任何编程的最佳建议是“保持简单”。对于大多数问题，递归比循环/递归更简单。

在 JVM 上，每个堆栈帧都需要一些内存(请参阅有关增加 -Xs 开关的文档)。如果使用太多堆栈帧，最终会耗尽内存(由 -Xmx 开关控制)。你通常应该能够指望至少有 1000 个堆栈帧可用(你可以测试你是否喜欢你的机器和参数)。因此，根据经验，如果您的递归深度为 1000 或更小，请不要担心使用 loop/recur。