让我们演示一个简单的例子：在C中实现的阶乘函数。

我们开始使用明显的递归定义

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    return n * fac(n - 1);
}

如果函数返回前的最后一个操作是另一个函数调用，则函数以尾调用结束。如果此调用调用相同的函数，则它是尾递归的。

尽管fac()乍一看似乎是尾递归，但实际发生的是

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    unsigned acc = fac(n - 1);
    return n * acc;
}

也就是最后一次操作是乘法而不是函数调用。

但是，可以通过将累积值作为附加参数向下传递并仅将最终结果作为返回值向上传递来将 fac() 重写为尾递归：

unsigned fac(unsigned n)
{
    return fac_tailrec(1, n);
}
unsigned fac_tailrec(unsigned acc, unsigned n)
{
    if (n < 2) return acc;
    return fac_tailrec(n * acc, n - 1);
}

现在，为什么这有用？因为我们在尾调用后立即返回，所以可以在在尾位置调用函数之前丢弃先前的堆栈帧，或在递归函数的情况下原样重用堆栈帧。

尾调用优化将我们的递归代码转换为

unsigned fac_tailrec(unsigned acc, unsigned n)
{
TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

这可以内联到fac()中，我们到达

unsigned fac(unsigned n)
{
    unsigned acc = 1;
TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

这相当于

unsigned fac(unsigned n)
{
    unsigned acc = 1;
    for (; n > 1; --n)
        acc *= n;
    return acc;
}

正如我们在这里所看到的，足够先进的优化器可以用迭代替换尾递归，这比避免函数调用开销并仅使用常量数量的堆栈空间要高效得多。

尾递归优化是指在函数调用时，由于调用函数返回的值是被调用函数的值，因此可以避免为函数分配新的堆栈帧。最常见的用法是尾递归，其中编写为利用尾递归优化的递归函数可以使用常量堆栈空间。

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）相同的空间。这在非尾递归的fact中并不是这种情况，因此大的值可能会导致堆栈溢出。