algorithm - 什么是尾调用优化？

Question

很简单，什么是尾调用优化？

更具体地说，有哪些小代码片段可以应用，哪些不能应用，并解释原因？

Answer 1

尾调用优化是您可以避免为函数分配新堆栈帧的地方，因为调用函数将简单地返回它从被调用函数获得的值。最常见的用途是尾递归，其中为利用尾调用优化而编写的递归函数可以使用常量堆栈空间。

Scheme 是少数在规范中保证任何实现都必须提供此优化的编程语言之一，因此这里有两个 Scheme 中阶乘函数的示例:

(define (fact x)
  (if (= x 0) 1
      (* x (fact (- x 1)))))

(define (fact x)
  (define (fact-tail x accum)
    (if (= x 0) accum
        (fact-tail (- x 1) (* x accum))))
  (fact-tail x 1))

第一个函数不是尾递归的，因为在进行递归调用时，函数需要跟踪调用返回后需要对结果进行的乘法运算。因此，堆栈如下所示:

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

相比之下，尾递归阶乘的堆栈跟踪如下所示:

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

如您所见，每次调用 fact-tail 时，我们只需要跟踪相同数量的数据，因为我们只是将直接获得的值返回到顶部。这意味着即使我调用 (fact 1000000)，我也只需要与 (fact 3) 相同的空间量。这不是非尾递归事实的情况，并且如此大的值可能会导致堆栈溢出。