让我们通过一个简单的例子来说明：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中并不成立，因此大的值可能导致堆栈溢出。