什么是尾递归？

技术背景

递归是编程中一种重要的技术，它允许函数调用自身来解决问题。然而，传统递归在处理大规模数据时可能会导致栈溢出错误，因为每次递归调用都会在调用栈上创建一个新的栈帧，随着递归深度的增加，栈空间会被耗尽。尾递归是一种特殊的递归形式，它可以避免这种问题，通过优化，尾递归可以将递归调用转换为迭代，从而减少栈空间的使用。

实现步骤

传统递归实现求和函数

function recsum(x) {
    if (x === 0) {
        return 0;
    } else {
        return x + recsum(x - 1);
    }
}

当调用 recsum(5) 时，JavaScript 解释器的计算过程如下：

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + (1 + recsum(0)))))
5 + (4 + (3 + (2 + (1 + 0))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15

可以看到，在传统递归中，每个递归调用都必须完成后，解释器才会开始实际计算总和。

尾递归实现求和函数

function tailrecsum(x, running_total = 0) {
    if (x === 0) {
        return running_total;
    } else {
        return tailrecsum(x - 1, running_total + x);
    }
}

当调用 tailrecsum(5) 时，计算过程如下：

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

在尾递归中，每次递归调用时，running_total 都会更新。

核心代码

传统递归实现阶乘函数

function factorial(number) {
    if (number === 1) {
        return 1;
    } else {
        return number * factorial(number - 1);
    }
}

尾递归实现阶乘函数

function tailFactorial(x, totalSoFar = 1) {
    if (x === 0) {
        return totalSoFar;
    } else {
        return tailFactorial(x - 1, totalSoFar * x);
    }
}

Java 中尾递归实现斐波那契数列

public class Fibonacci {
    public int tailRecursive(final int n) {
        if (n <= 2)
            return 1;
        return tailRecursiveAux(n, 1, 1);
    }

    private int tailRecursiveAux(int n, int iter, int acc) {
        if (iter == n)
            return acc;
        return tailRecursiveAux(n, ++iter, acc + iter);
    }

    public int recursive(final int n) {
        if (n <= 2)
            return 1;
        return recursive(n - 1) + recursive(n - 2);
    }
}

最佳实践

识别尾递归模式：尾递归的关键特征是递归调用是函数的最后一个操作，并且没有其他计算需要在递归调用返回后执行。
使用累加器参数：为了实现尾递归，通常需要引入一个累加器参数来保存中间结果。
考虑语言支持：不同的编程语言对尾调用优化的支持不同。例如，Scheme 要求所有实现都必须优化尾递归函数，而 JavaScript 的大多数解释器目前不支持尾调用优化。