递归的优化方法
递归的优化方法
递归的优化主要包括时间复杂度和空间复杂度两个方面的优化。如果递归能在空间上做到优化，不但能节省栈的空间，同时节省了调用函数的时间，也能大大加快程序的运行速度。
时间复杂度的优化
是否重复计算
在递归的过程中，很多时候一些子问题会被重复计算。以斐波那契数列为例：
int Fibonacci(int n)
{
if (n <= 1) return n;
return Fibonacci(n - 2) + Fibonacci(n - 1);
}
由上图可见，fib(4), fib(3), fib(2), fib(1)均被重复计算，此时时间复杂度为 O(2^n)。
优化方法
我们可以将计算的结果保存起来，就可以避免重复进行计算。可以用数组或者是哈希表进行存储，通过查表判断是否有重新计算过，如果有则无需再算。
int Fmap[1000]; // 这里用数组，将Fmap全部初始化为-1(代表未计算过）
int Fibonacci(int n)
{
if (n <= 1) return n;
if(Fmap[n] != -1) // 不等于-1 说明计算过
return Fmap[n];
Fmap[n] = Fibonacci(n - 2) + Fibonacci(n - 1);
return Fmap[n];
}
通过这样优化，只需要Fib(n), Fib(n-1), …, Fib(1)每个计算一次，因此时间复杂度为 O(n)。
PS: 如果有学习过动态规划的同学，会发现这种优化本质其实是动态规划的思想。
尾递归
尾递归，顾名思义，就是在函数体的尾部再进行递归（调用自己）。
void func1(int n) // 非尾递归
{
int i = 1;
return i + func1(n-1) // 先求func(n-1) 再计算加法 再返回
}
void func2(int n, ...) // 尾递归 省略号是指一般尾递归会有另外参数作为暂存变量
{
int i = 1;
return func2(n-1, ...) // 直接将func(n-1, ...)返回
}
通过上面两个例子，可以大致理解什么才叫作尾递归。在func1中，先计算func(n-1)，然而func(n)函数并没有结束，还要计算一个加法，所以并不是在函数的尾部才调用自己。在func2中，在return直接返回递归函数的下一层，才能称作尾递归。
斐波那契数列的尾递归写法
int Fibonacci(int n, int x, int total)
{
if (n <= 1) return x;
return Fibonacci(n - 1, total, x + total); // 实际上是一种迭代
}
int main()
{
cout << Fibonacci(3, 1, 1); // 斐波那契数列第三项
}
优化原理
非尾递归的情况，因为递归函数还需要返回，继续执行下面的部分代码（如上面例子的加法），所以每次进入下一层递归，会对当前层的局部变量进行入栈保存，如果递归层数太多，则会溢出。
尾递归的情况，因为函数在最后才进行递归，后面已经没有需要再计算的了，所以递归前面的局部变量无需进行保存。因此，其实尾递归只需用到一层栈，每到下一层递归，当前层函数就退栈，下一层函数就入栈。
然而并不是所有语言的编译器都能对尾递归进行优化，也就是说，就算你写成了尾递归的形式，有些编译器还是会随着递归不断入栈（而不是只用一层栈），因此便是需要手动写代码进行尾递归优化。
手动进行尾递归优化
尾递归，其实可以看做一种特殊的迭代，因此如果递归可以改写成尾递归（不是所有递归都可以），那么就可以通过写成迭代的方式，手动实现尾递归的优化。换句话说，尾递归是迭代的一种特殊写法，二者时间和空间复杂度是相同的。尾递归并没有对时间复杂度进行任何优化，单纯的只是将空间复杂度缩小为O(1)。
在函数体内多次递归
如果递归函数只是调用自己一次，相应的递归树是一棵斜树。如果调用自己两次，则是一棵二叉树。如果调用自己多次，则树的结点有多个分支。如果随着树的结点分支增多，一些子树的深度减小，则总体的递归树深度会减少，出现递归过深导致溢出的可能性就降低。
示例 快速排序
// 传统 未优化
void Qsort1(vector<int> &vec, int low, int high)
{
int pivot;
if(low < high)
{
pivot = Partition(vec, low, high);
Qsort1(vec, low, pivot - 1); // 对支点左边序列 快速排序
Qsort1(vec, pivot + 1, high); // 对支点右边序列 快速排序
}
}
// 对递归进行了优化
void Qsort2(vector<int> &vec, int low, int high)
{
int pivot;
if(low < high)
{
// 采用迭代方式 缩小栈的深度
while(low < high)
{
pivot = Partition(vec, low, high); // 分成左右两个“一小一大”序列
Qsort2(vec, low, pivot - 1); // 只对左半边进行快速排序
low = pivot + 1;
}
}
}
这是对传统的快速排序中递归的部分的一种优化方式。Qsort1是传统的快速排序，Qsort2是进行递归优化的快速排序。
Qsort2的原理：首先将序列分两半，取出左半边，进行快速排序。右半边先不排序，再次切两半，对右半边的左半边进行快速排序，右半边的右半边继续切两半，…如此迭代
可以得到Qsort2的递归方程
T(n) =T(\frac{n}{2}) +T(\frac{n}{4})+T(\frac{n}{8})+...+T(1)=\sum\nolimits_{i=1}^{logn} T(\frac{n}{2^i})
所以递归树的结点有logn个分支，且每个分支的深度不断减少。最左边的分支 T(\frac{n}{2}) ，有logn层，最右边的分支只有一层。
因此，传统的Qsort1的递归树是logn层的满二叉树，现在优化后的Qsort2的递归树是logn层的不对称的树（左边多，右边少）。两个算法使用的总的空间应该是一样的(树的结点数相同)，但是Qsort2只有最左边的分支达到了logn层，其他的分支的层数很小，因此很快就能释放，所以Qsort2不容易溢出。
ps:很多地方说快速排序的这种写法是尾递归优化，然而根据定义这显然是有误的。
综合应用
示例 x的n次方
通过递归的方式计算x的n次方
int xpow(int x, int n)
{
if (n == 0) return 1;
return xpow(x, n - 1) * x;
}
这个算法的时间复杂度为 O(n) ，有没有办法将它优化到 O(logn) ?
首先这个算法的递归树是斜树，可以想办法将结构变为二叉树。
int xpow(int x, int n)
{
if (n == 0) return 1;
if(n % 2 == 1)
return xpow(x, n/2) * xpow(x, n/2) * x
else
return xpow(x, n/2) * xpow(x, n/2);
}
考虑是否有重复计算的部分（是否能优化树的部分分支）
可以很明显看出 xpow(x, n/2) 重复计算
int xpow(int x, int n)
{
if (n == 0) return 1;
int t = xpow(x, n/2);
if(n % 2 == 1)
return t * t * x
else
return t * t;
}
优化后该算法的时间复杂度为 O(logn)
总结一下，虽然上述例子稍微有点特殊，但是思路是可以借鉴的。一连串的递归首先考虑是否能转化成树的结构，然后再观察树的一些分支是否重复计算来进行优化。