algorithm - 什么是尾叫优化？(What Is Tail Call Optimization?)

Question

Very simply, what is tail-call optimization?

(很简单，什么是尾叫优化？)

More specifically, Can anyone show some small code snippets where it could be applied, and where not, with an explanation of why?

(更具体地说，任何人都可以显示一些小的代码片段，在何处可以使用它，而在何处不可以，并解释其原因？)

  ask by majelbstoat translate from so

Answer 1

Tail-call optimization is where you are able to avoid allocating a new stack frame for a function because the calling function will simply return the value that it gets from the called function.

(尾调用优化可以避免为函数分配新的堆栈帧，因为调用函数将简单地返回它从被调用函数获得的值。)

The most common use is tail-recursion, where a recursive function written to take advantage of tail-call optimization can use constant stack space.

(最常见的用途是尾部递归，其中利用尾部调用优化编写的递归函数可以使用恒定的堆栈空间。)

Scheme is one of the few programming languages that guarantee in the spec that any implementation must provide this optimization (JavaScript does also, starting with ES6) , so here are two examples of the factorial function in Scheme:

(Scheme是在规范中保证任何实现都必须提供此优化的少数编程语言之一（JavaScript也是从ES6开始） ，因此这是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))

The first function is not tail recursive because when the recursive call is made, the function needs to keep track of the multiplication it needs to do with the result after the call returns.

(第一个函数不是尾递归，因为在进行递归调用时，该函数需要跟踪在调用返回后需要对结果进行的乘法运算。)

As such, the stack looks as follows:

(这样，堆栈如下所示：)

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

In contrast, the stack trace for the tail recursive factorial looks as follows:

(相反，尾部递归阶乘的堆栈跟踪如下所示：)

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

As you can see, we only need to keep track of the same amount of data for every call to fact-tail because we are simply returning the value we get right through to the top.

(如您所见，对于事实尾部的每次调用，我们只需要跟踪相同数量的数据，因为我们只是将获得的值返回到顶部。)

This means that even if I were to call (fact 1000000), I need only the same amount of space as (fact 3).

(这意味着即使我要调用（事实1000000），我也只需要与（事实3）相同的空间。)

This is not the case with the non-tail-recursive fact, and as such large values may cause a stack overflow.

(非尾递归事实并非如此，因为如此大的值可能会导致堆栈溢出。)