尾递归和普通递归思想的差异

以前写的递归大都是普通递归，因此大都通过返回值层层返回。但是还有一类递归函数没有返回值，通过对一个变量的层层操作最终使得此变量就是最终答案。

递归一般用于解决三类问题：

　 (1)数据的定义是按递归定义的。（Fibonacci函数，n的阶乘）

　 (2)问题解法按递归实现。（分治、回溯、第n步可以由n-1步规律得到）

　 (3)数据的结构形式是按递归定义的。（二叉树的遍历，图的搜索）

递归的缺点：

　　递归解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，因此递归次数过多容易造成栈溢出。

下面是我们常见的普通递归，用计算机的思维把复杂问题变简单，求第n项斐波那契数列的值只需要让n-1和n-2项斐波那契数列的值相加即可，我们充分相信FibonacciRecursive(n-1)、FibonacciRecursive(n-2)能够算出第n-1和n-2项的值，直接返回即可。

 int FibonacciRecursive(int n)
 {
     if( n < 2)
         return n;
     return (FibonacciRecursive(n-1)+FibonacciRecursive(n-2));
 }

下面是尾递归方式计算第n项斐波那契数列值：

 int FibonacciTailRecursive(int n,int ret1,int ret2)
 {
    if(n==0)
       return ret1;
     return FibonacciTailRecursive(n-1,ret2,ret1+ret2);
 }

尾递归就是把当前的运算结果（或路径）放在参数里传给下层函数，深层函数所面对的不是越来越简单的问题，而是越来越复杂的问题，因为参数里带有前面若干步的运算路径。 尾递归更像是人类的思维，在我看来和循环的逻辑一致的。其实在汇编层面调用函数就是一句call指令，这条指令会跳转到被调用函数的入口地址；而循环在汇编层面其实也可以用jmp来实现，不符合跳出条件时一直使用jmp跳到函数开始执行的地址处。所以如果使用尾递归，就是在函数结束前的最后阶段再次调用此函数，相当于又跳转回函数入口处重新执行程序，和循环每次回到程序初始状态的逻辑一致。只不过尾递归需要涉及到不断地参数传递，每次递归调用都对若干固定的变量进行计算，循环也是如此。尾递归和循环都是按照人类思维由易到难对变量进行操作的。

例子1： 尾递归实现冒泡排序

就相当于递归函数里是一层内循环，尾递归本身是一层外循环。最终跳出条件就是外层循环结束条件，此时arr内的数值已经排好序了。

 // 冒泡排序
 void BubbleSort(vector<int>& arr,int begin,int end)
 {
     if (end == 0) return;
 ​
     if (end >= begin)
     {
         for (int i = begin; i <= end; i++)
         {
             if (arr[i] < arr[i - 1])
             {
                 swap(arr[i], arr[i - 1]);
             }
         }
     }
     BubbleSort(arr, begin, end - 1);
 }

再来对比一下循环版本：

 ​
 void BubbleSort(vector<int>& arr)
 {
     for (int end = arr.size() - 1; end >= 1;end--)
     {
 ​
         for (int begin = 1; begin <= end; begin++)
         {
             if (arr[begin] < arr[begin - 1])
             {
                 swap(arr[begin], arr[begin - 1]);
             }
         }
 ​
     }
 }

发现尾递归和循环的逻辑完全一致，只不过循环可以直接在语法中定义循环条件和循环跳出条件，而尾递归需要在函数中自己定义if语句判断循环进行和终止。