在Racket的递归中堆栈溢出

Question

作为函数式编程的一部分,在Racket中高度推广递归.但是,堆栈溢出是递归时通常提到的一个重要问题.在Racket中是否存在可能发生堆栈溢出的情况以及应采取哪些预防措施来防止此类事件发生？

Answer 1

不会.您将永远不会在Racket中获得堆栈溢出.这是因为Racket VM并不真正在OS级别调用堆栈中存储内存.但是,你可以做的就是耗尽你所有的机器内存.您可以通过使用要求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称为"优化"一样错误.}