尾递归

一、尾递归

一般的递归如果递归次数过多就可能会遇到栈溢出，这是由于每个线程在执行代码时，都会分配一定尺寸的栈空间（Windows系统中为1M），每次方法调用时都会在栈里储存一定信息（如参数、局部变量、返回地址等等），这些信息再少也会占用一定空间，成千上万个此类空间累积起来，自然就超过线程的栈空间了。不过这个问题并非无解，我们只需把递归改成如下形式即可（在这篇文章里我们不考虑非递归的解法）

int Factorial(int number, int accumulator)
{
     if (number < 0) {
         return 0;
     } else if (0 == number || 1 == number) {
         return accumulator;
     } else {
         return Factorial(number - 1, accumulator * number);
     }
 }

Factorial(5, 1);//计算5的阶乘

Factorial方法多了一个为accumulator（累加器）的参数，它的功能是在递归调用时 “积累”之前调用的结果，并将其传入下一次递归调用中——这就是所谓的“尾递归”。与普通递归相比，由于尾递归的调用处于方法的最后，而普通的递归会将结果返回来在进行必要的运算，因此方法之前所积累下的各种状态对于递归调用结果已经没有任何意义，完全可以把本次方法中留在堆栈中的数据完全清除，把空间让给最后的递归调用。这样的优化便使得递归不会在调用堆栈上产生堆积，意味着即使是“无限”递归也不会让堆栈溢出。当然，这些优化都是编译器替我们完成的。对比普通的递归，代码如下所示：

int Factorial(int number)
{
     if (number < 0) {
         return 0;
     } else if (0 == number || 1 == number) {
         return 1;
     } else {
         return Factorial number * (number - 1);
     }
 }

下面看一下Fibonacci的尾递归：

int Fibonacci(int number, int accumulator1, int accumulator2)
{
     if (0 == number) return accumulator1
     return Fibonacci(number - 1, accumulator2, accumulator1 + accumulator2)
 }

Fibonacci(5, 0, 1);

二、尾递归与lambda

阶乘的lambda写法：

int Factorial(int number, function<int(int)> continuation)
{
    if (0 == number) return continuation(1);
    return Factorial(number - 1, [=](int r) { return continuation(number * r); });
}

int main()
{
    auto continuation = [](int value) { return value; };
    Factorial(5, continuation);
    return 0;
}

Fibonacci的lambda写法，虽然是尾递归，但是该算法在计算第30项左右的结果时，依旧会栈溢出：

int Fibonacci(int number, function<int(int)> continuation)
{
    if (number < 2) return continuation(number);
    return Fibonacci(number - 1, [=](int x) { return Fibonacci(number - 2,
                                                              [=](int y) { return continuation(x + y); });});
}

int main()
{
    auto continuation = [](int value) { return value; };
    Fibonacci(5, continuaation);
    return 0;
}

三、是否使用尾递归

也有人发对使用尾递归，到底要不要使用尾递归是件仁者见仁，智者见智的问题。网上查阅，java，C#和python都不支持编译环境自动优化尾递归，这种情况下，当然是别用递归效率最高，但是C/C++编译器提供了这项服务，使用起来自然没问题。编译器对尾递归的优化实际上就是当他发现尾递归的时候，就不会去不断创建新的栈帧，而是就着当前的栈帧不断的去覆盖，一来防止栈溢出，二来节省了调用函数时创建栈帧的开销，用《算法精解》里面的原话就是：“When a compiler detects a call that is tail recursive, it overwrites the current activation record instead of pushing a new one onto the stack.”

一般尾递归很好理解，代码可读性强，但是与lambda结合以后就有点复杂了。而且能够写出尾递归，基本上就能够写出相应的非递归了(一般非递归比递归效率更高，但是代码难懂)。所以是否使用尾递归就全凭个人喜好。