recursion - Racket中递归的堆栈溢出

Question

作为函数式编程的一部分，递归在 Racket 中得到了高度推广。然而，堆栈溢出是递归中普遍提到的一个重要问题。 Racket 中是否存在任何可能发生堆栈溢出的情况，应该采取哪些预防措施来防止此类事件发生？

Answer 1

没有。你永远不会在 Racket 中遇到堆栈溢出。这是因为 Racket VM 并不真正将内存存储在操作系统级别的调用堆栈中。但是，您可以做的是用完所有机器内存。您可以通过使用需要 Racket VM 不断存储越来越多空间的函数来做到这一点。例如:

(define (f)
  (define x (random))
  (f)
  x)

在此函数中，Racket 在开始返回之前需要存储无限数量的随机 x 值，这将导致您的 VM 耗尽内存。

另一方面，如果您在函数中交换两行:

(define (f)
  (f)
  (define x (random))
  x)

您的函数仍然永远不会终止，并且内存耗尽所需的时间也会长得多。这是因为 VM 只需要记住在完成之前返回到之前对 f 的调用，而不需要为 x 存储空间。

最后，如果我们有这个函数:

(define (f)
  (define x (random))
  x
  (f))

该函数永远不会终止，但它也永远不会耗尽内存。这是因为它为 x 分配了一个空间，但在递归调用 f 时能够删除该空间。此外，由于递归调用是函数执行的最后一件事，它也不再需要存储对 f 的原始调用，这意味着每次递归函数调用都不需要新的空间。这称为尾调用消除。¹ 实际上，最后一个函数等同于 C 或 Java 中的无限循环。

_{¹请注意，有些人错误地称之为尾调用优化。这不是优化，因为它是语言核心语义的一部分。将其称为“优化”与将 Java 的 GC 称为“优化”一样错误。}