递归是编程中的一个强大工具，但它也有一个潜在的问题：栈溢出。尾递归优化（Tail Call Optimization，简称 TCO）是一种技术，可以帮助我们避免这个问题。一些语言的编译器可以自动帮我们实现尾递归优化，比如 Rust 和 Scala，GCC 在某些优化级别下也会尝试进行尾递归优化。在本文中，我们将深入探讨尾递归优化的原理和应用。

什么是递归？

递归是一个函数直接或间接地调用自己的过程。例如，计算阶乘的经典函数：

int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n-1);
}

这个函数调用自己来计算阶乘，是一个递归函数。

递归的问题

每当函数被调用时，都会在栈上为其分配一个新的栈帧。由于栈空间是有限的，深度递归可能会导致栈溢出。

什么是尾递归？

尾递归是一种特殊的递归，其中函数的 递归调用是其最后执行的操作。

在上面的例子中，函数 factorial(n) 的最后一步需要先得到 factorila(n - 1) 的结果，之后再用这个结果乘 n。因此他没有使用尾递归。

接下来我们把这个例子进行一定的修改，使其使用尾递归：

int tail_recursive_factorial(int n, int acc) {
    if (n == 0) return acc;
    return tail_recursive_factorial(n-1, n*acc);
}

在这个版本中，我们引入了一个累积器 acc 来保存中间结果。每次递归调用都是函数的最后一个操作，因此编译器或解释器可以优化它，使其不需要为每次调用分配新的栈帧。这样，即使 n 非常大，该函数也不会导致栈溢出。

需要注意的是，并不是所有的编程语言或编译器都支持尾递归优化。例如，Python 就不支持尾递归优化。

我们来手动模拟一下尾递归优化：
在这个阶乘代码中，递归退出的条件是 n == 0，在每次递归的结尾，n 变成了 n - 1，acc 变成了 n * acc。所以我们可以把本次递归中的变量手动进行变更，同时使他有相同的退出条件：

int tail_recursive_factorial(int n, int acc) {
    while (n > 0) {
        acc = n * acc;
        n = n - 1;
    }
    return acc;
}

尾递归优化的原理

尾递归优化的核心思想是：由于递归调用是函数的最后一个操作，所以没有必要为递归调用保留当前函数的栈帧。编译器可以重用当前函数的栈帧，从而避免栈溢出。

尾递归优化的应用

在阅读 Git 源码时，有阅读到代码中手动实现尾递归优化的例子：

static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,
	int line1, int count1, int line2, int count2)
{
	struct region lcs;
	int lcs_found;
	int result;
redo:
	result = -1;

	if (count1 <= 0 && count2 <= 0)				// 起点都小于等于0 （向前递归的出口）
		return 0;

	if (LINE_END(1) >= MAX_PTR)
		return -1;

	if (!count1) {
		while(count2--)
			env->xdf2.rchg[line2++ - 1] = 1;	// 若一边为空，另一边标记为新增
		return 0;
	} else if (!count2) {
		while(count1--)
			env->xdf1.rchg[line1++ - 1] = 1;
		return 0;
	}

	memset(&lcs, 0, sizeof(lcs));		// 接下来就是两边都不为空，填充 lcs
	lcs_found = find_lcs(xpp, env, &lcs, line1, count1, line2, count2);	// 返回 0 ， // 若返回 1 说明没有找到相同行，或是找到了匹配行，但是匹配行在 A 中出现超过 64 次
	if (lcs_found < 0)
		goto out;
	else if (lcs_found)
		result = fall_back_to_classic_diff(xpp, env, line1, count1, line2, count2);
	else {
		if (lcs.begin1 == 0 && lcs.begin2 == 0) {			// begin 下标从 1 开始，若为 0 即没找到公共子序列，把左右两边 line 全部标记为变化
			while (count1--)
				env->xdf1.rchg[line1++ - 1] = 1;
			while (count2--)
				env->xdf2.rchg[line2++ - 1] = 1;
			result = 0;
		} else {
			result = histogram_diff(xpp, env,
						line1, lcs.begin1 - line1,
						line2, lcs.begin2 - line2);	// 递归上面的部分
			if (result)
				goto out;
			/*
			 * result = histogram_diff(xpp, env,
			 *            lcs.end1 + 1, LINE_END(1) - lcs.end1,
			 *            lcs.end2 + 1, LINE_END(2) - lcs.end2);
			 * but let's optimize tail recursion ourself:			// 手动实现了尾递归优化
			*/
			count1 = LINE_END(1) - lcs.end1;
			line1 = lcs.end1 + 1;
			count2 = LINE_END(2) - lcs.end2;
			line2 = lcs.end2 + 1;
			goto redo;
		}
	}
out:
	return result;
}

在这里，通过使用 goto 语句，在函数的最后更新参数，goto到开始的位置，省去了递归调用时的栈帧分配。

如何确保尾递归优化？

1. 确保递归调用是函数的最后一个操作。
2. 使用编译器的优化选项。
3. 测试以确保优化确实发生了。