尾递归的本质

先直接上两个例子：求n的阶乘，仔细观察对比一下

例子1：

int fact(int n)

{

    if(n<0)

      return 0;

    else if(n ==0 || n==1)

      return 1;

    return  n * fact(n-1);

}
           

例子2：

int fact(int n)

{

    return  fact_iter(n , 1 ,1);

}

int fact_iter(int n ,int count ,int result)

{

    if(n<0)

      return 0;

    if(count > n)

      return  result;

    return  fact_iter(n , count+1 ,result * count);

}
           

        上边的两个例子一个是正常的递归实现，另外一个是尾递归实现，初次看这两个例子会感觉递归很容易理解而尾递归看着怪怪的，的确，尾递归有点“违反”常规。

首先我们看看函数与递归的本质：

        函数调用的本质是: 我们在做一件事过程中，我们发现必须要先完成另外一件事，于是中断当前的工作，并把当前的工作信息保存到栈(stack); 当别的事情完成了再继续当前的工作(从stack 中取出工作信息并继续)。

        而递归的本质也就是函数调用，只不过当前的工作与另外一件事是相同的执行步骤，不同的只是工作内容。

        下面介绍一下，尾递归的来源。我们知道递归的实现本质就是用栈保存每一层的局部信息、返回地址等等，递归一层一层递进调用自己的时候，对应的栈也要一层一层的分配空间保存信息，递进到最后一层时再逐层返回，对应的栈空间也一层一层回收。从递归的实现可以看出，它对栈的空间要求随着递归递进的层数增加而增加，如果层数很大，因为对于一个程序来说，栈的大小是有最大值的，如果超过这个值，那么就会导致栈溢出而使程序崩溃，解决递归调用栈溢出的一个方法就是尾递归。

        下边直接先摆出尾递归的本质：将当前层运算的结果以函数参数的形式传递给下一层调用。

        为什么这么说，因为这体现了尾递归的来源，这样做就是为了解决栈溢出的。那为什么这样就可以解决栈溢出呢？首先我们来回忆一下这样一个知识，通常我们利用函数实现某一个功能的时候，我们有两种方式获得结果，第一种方法是直接在函数中利用return语句返回结果，这是最直接的方法直接调用函数就可以获得结果，另外一种方法就是给函数设置一个参数专门用来保存函数的返回值，这种方法选择了另外一个变量作为函数参数传入函数，函数执行完毕后该变量就保存了函数的返回结果。

        好了，有了上边的一些回忆，我们仔细看一下第二个例子中的fact_iter(int n ,int count ,int result)函数，因为我们将结果result以一个函数的参数形式体现，上一层的调用结果直接反映到下一层的函数调用实参中，这样可以实现上下层之间没什么联系了，不用逐层返回了，nice，要的就是这个效果，有了这样一个好处后，我们可以不用每一层都新分配一些栈空间，直接覆盖原来的栈空间就行了，因为原来的栈空间没什么用了，就这样，大功告成，栈空间不会一层一层不断分配以及回收，也就不会出现栈溢出了。

        OK，上边都是讲尾递归怎么怎么好，那么问题来了，尾递归它也是递归，具体到实际当中，这种特殊的递归其栈空间覆盖是怎么实现的呢？事实上，一般是由编译器来对代码进行优化实现的，尾递归有一个显著的特点就是它的递归调用语句总是放在函数的最末尾，这其实是给编译器一个信号，表明自己身份，当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活跃记录而不是在栈中去创建一个新的通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。

        最后，我们似乎不能高兴的太早，各种语言编译器或者解释器都能够自动优化尾递归么？答案不那么美好，据网上查阅：java、C#和python都不支持编译环境自动优化尾递归，在这种情况下我们可以手动将递归改造成循环，但是对于C语言来说，编译器提供了自动优化，不用白不用，毕竟递归代码好理解。