什么是尾调用优化？ [英] What Is Tail Call Optimization?

问题描述

很简单，什么是尾部调用优化？更具体地讲，任何人都可以表现出一些小的code片段，它可以适用，并在不与一个解释，为什么？

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?

推荐答案

尾调用优化是你能避免功能分配一个新的堆栈帧，因为调用函数将简单的返回它从得到的值调用的函数。最常见的用途是尾递归，在这里写了一个递归函数来充分利用尾部调用优化可以使用常数堆栈空间。

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.

计划是这保证了规范，任何实现必须提供这种优化的一些编程语言之一的（JavaScript的也会，一旦ES6定稿）的，所以这里的阶乘函数的两个例子方案：

Scheme is one of the few programming languages that guarantee in the spec that any implementation must provide this optimization (JavaScript will also, once ES6 is finalized), so here are two examples of the factorial function in 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

正如你所看到的，我们只需要跟踪的数据相同数量的每次调用的事实尾因为我们只返回我们得到的权利，通过顶端的价值。这意味着，即使我打电话（其实1000000），我需要的只是空间相同数量的（其实3）。这是不与非尾递归事实，并且因此大的值可能导致堆栈溢出的情况。

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). This is not the case with the non-tail-recursive fact, and as such large values may cause a stack overflow.

这篇关于什么是尾调用优化？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！