Clojure: recur和递归的fn名称之间的区别

Question

Clojure: recur和递归的fn名称之间的区别

4

我只是一个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 处设置的递归点进行操作吗？与通过名称递归函数有什么区别（除了优化之外）？

- alepeino

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alan Thompson · Accepted Answer

通过稍微修改程序，您可以看到问题所在：

(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个元素的集合[2]不会替换mapcat调用末尾的ls值，因此你会得到无限循环。任何编程的最好建议是"保持简单"。对于大多数问题，递归比loop/recur更简单。在JVM上，每个堆栈帧都需要一些内存（请查阅有关-Xs开关的文档以进行增加）。如果使用太多堆栈帧，最终将耗尽内存（由-Xmx开关控制）。通常应该能够指望至少有1000个堆栈帧可用（可以测试一下你的机器和参数）。因此，作为一个经验法则，如果递归深度为1000或更少，请不要担心使用loop/recur。