2

Clojure 是我第一次涉足 lisp 世界。我决定尝试一个简单的递归函数，它将一个数字提高到整数幂。很简单。

(defmulti pow #(compare %2 0))
(defmethod pow 0 [a n] 1)
(defmethod pow 1 [a n] (* a (pow a (dec n))))
(defmethod pow -1 [a n] (/ 1 (pow a (* -1 n))))

如果你只传递整数幂，它就可以正常工作。但是当我使用它来提升到足够大的功率时，我得到了堆栈溢出（可以预见）。

问题是，我怎样才能知道函数在死前的递归深度？大致了解我可以递归多深的一种方法是执行以下操作：

(defn max-depth [n] 
    (try
        (max-depth (inc n))
    (catch StackOverflowError err (do
        (printf "%s at %d\n" err n)
        n)
)))

（Clojure 是我第一次尝试 lisp，所以我真的不知道如何让代码看起来可读。）这段代码只是无限递归，直到它溢出堆栈，然后返回在它爆炸之前发生的递归次数。这只能让我大致了解我可以走多远……这种方法存在很多问题。

我可以做的另一件事是捕获异常并尝试自己展开堆栈......但我真的看不到从异常中获取我想要的信息的方法。在http://docs.oracle.com/javase/6/docs/api/java/lang/StackOverflowError.html上查看StackOverflowError 的 javadoc我看到了一些看起来很有希望的方法，但没有任何结果。看。

我尝试运行 (count (.getStackTrace error)) ，其中错误是我捕获的堆栈溢出，但结果仅为 1024，因为“在某些情况下，可能会省略堆栈帧”。所以那没有用。

我能想到的唯一另一件事是在连续更大的指数上运行 pow，但这并不能真正告诉我调用堆栈有多深，它只告诉我可以提高到多大的指数（因为函数调用其他函数，两个答案不一样）。

我也不知道在 java 中有什么方法可以做到这一点，但如果有的话，那么这个答案也可能会有所帮助。

有任何想法吗？谢谢，--斯科特

4

2 回答 2

2

我原以为这(.getStackTrace error)是你最好的选择——你为什么认为它不起作用？

在为一个简单的函数炸毁堆栈之前，递归深度为 1024 听起来符合我的预期。

请记住，单个 Clojure 函数通常会转换为多个 JVM 方法调用，因此实际的 JVM 堆栈深度可能比您的递归 valable 更深n。如果您想从堆栈跟踪转换回n，您可能需要计算对多方法的递归调用出现在堆栈跟踪中的次数。

于 2013-06-02T09:30:09.017 回答
0

所以，我实际上不会回答你的问题——因为我认为尝试调试调用堆栈深度是解决这个问题的错误方法。相反，我将建议在 Clojure 中使用一种更有效的递归方法，这不会有破坏调用堆栈的风险。

重要的概念是“尾调用消除”——这基本上意味着如果函数 F 是一个递归函数，并且它所做的最后一件事是调用自身，则可以对其进行优化。对于 F 的第 n 次递归调用，它所做的最后一件事是调用 F 的第 n+1 次递归调用并将该值返回给 F 的第 n-1 次调用 - 这样您就可以覆盖与第 n 次调用有关的所有堆栈数据F，并让第 n+1 次调用将其值直接返回给第 n-1 次调用。所以这基本上意味着您只需要堆栈上的一个位置，而不是数百或数千。

JVM 本身并不支持函数调用的这种优化 - 否则您的示例可能会起作用。相反，Clojure 提供了 recur 运算符，它重用当前循环或函数调用，而不是增加堆栈。我会用它来重写你的函数（为了简单起见，我省略了你对负指数的支持）：

user=> (defn pow
  #_=>   ([base exp] (pow base exp base)) ; default the accumulator argument to the base of the power
  #_=>   ([base exp acc] (if (= exp 1)
  #_=>                         acc ; base case - return the accumulated power
  #_=>                         (recur base (dec exp) (* base acc))))) ; recur, decrementing the power
#'user/pow
user=> 

user=> (pow 1 10000000) ; stack not blown
1
user=> (pow 2 10)
1024

另见：http ://clojure.org/functional_programming#Functional%20Programming--Recursive%20Looping和http://en.wikipedia.org/wiki/Tail_call

当然，这种 pow 的实现只是一个递归示例——任何阅读本文的人都应该使用 Math/pow 来代替实际工作。

user=> (time (Math/pow 1 10000000))
"Elapsed time: 0.166723 msecs"
1.0
user=> (time (pow 1 10000000))
"Elapsed time: 2991.321703 msecs"
1
user=> (time (pow 2 1000))

ArithmeticException integer overflow  clojure.lang.Numbers.throwIntOverflow (Numbers.java:1388)
user=> (time (Math/pow 2 1000))
"Elapsed time: 0.069109 msecs"
1.0715086071862673E301
于 2013-06-06T00:23:11.437 回答