递归优化技巧

学习技巧2：主动归纳总结，强化记忆 #生活技巧# #学习技巧# #终身学习态度#

递归的几种优化 时间复杂度的优化是否重复计算 空间复杂度的优化1 尾递归2 在函数体内多次递归 综合应用

  递归的优化包括时间复杂度上的优化以及空间复杂度上的优化两种。
  如果递归能在空间上做到优化，不但能节省栈的空间，同时节省了调用函数的时间，也能大大加快程序的运行速度。

时间复杂度的优化 是否重复计算

在递归的过程，很多时候一些子问题是被重复计算的

斐波那契数列

int Fibonacci(int n) { if (n <= 1) return n; return Fibonacci(n - 2) + Fibonacci(n - 1); } 12345

由上图可见，fib(4), fib(3), fib(2), fib(1)均被重复计算，此时时间复杂度为 O ( 2 n ) O(2^n) O(2n)

优化方法
我们可以将计算的结果保存起来，就可以避免重复进行计算。
可以用数组或者是哈希表进行存储，通过查表判断是否有重新计算过，如果有则无需再算。

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]; } 123456789101112

通过这样优化，只需要Fib(n), Fib(n-1), …, Fib(1)每个计算一次，因此时间复杂度为 O ( n ) O(n) O(n)
PS: 如果有学习过动态规划的同学，会发现这种优化本质其实是动态规划的思想。

空间复杂度的优化 1 尾递归

尾递归，顾名思义，就是在函数体的尾部再进行递归（调用自己）。

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, ...)返回 } 1234567891011

通过上面两个例子，可以大致理解什么才叫作尾递归。
在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); // 斐波那契数列第三项 } 1234567891011

优化原理
非尾递归的情况，因为递归函数还需要返回，继续执行下面的部分代码（如上面例子的加法），所以每次进入下一层递归，会对当前层的局部变量进行入栈保存，如果递归层数太多，则会溢出。

尾递归的情况，因为函数在最后才进行递归，后面已经没有需要再计算的了，所以递归前面的局部变量无需进行保存。因此，其实尾递归只需用到一层栈，每到下一层递归，当前层函数就退栈，下一层函数就入栈。

然而并不是所有语言的编译器都能对尾递归进行优化，也就是说，就算你写成了尾递归的形式，有些编译器还是会随着递归不断入栈（而不是只用一层栈），因此便是需要手动写代码进行尾递归优化。

手动进行尾递归优化
  尾递归，其实可以看做一种特殊的迭代，因此如果递归可以改写成尾递归（不是所有递归都可以），那么就可以通过写成迭代的方式，手动实现尾递归的优化。
  换句话说，尾递归是迭代的一种特殊写法，二者时间和空间复杂度是相同的。尾递归并没有对时间复杂度进行任何优化，单纯的只是将空间复杂度缩小为O(1)。

2 在函数体内多次递归

如果递归函数只是调用自己一次，相应的递归树是一棵斜树。如果调用自己两次，则是一棵二叉树。如果调用自己多次，则树的结点有多个分支。如果随着树的结点分支增多，一些子树的深度减小，则总体的递归树深度会减少，出现递归过深导致溢出的可能性就降低。

示例 快速排序

// 传统 未优化 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; } } }

123456789101112131415161718192021222324252627

这是对传统的快速排序中递归的部分的一种优化方式。Qsort1是传统的快速排序，Qsort2是进行递归优化的快速排序。

Qsort2的原理：首先将序列分两半，取出左半边，进行快速排序。右半边先不排序，再次切两半，对右半边的左半边进行快速排序，右半边的右半边继续切两半，…如此迭代

可以得到Qsort2的递归方程
T ( n ) = T ( n 2 ) + T ( n 4 ) + T ( n 8 ) + . . . + T ( 1 ) = ∑ i = 1 l o g n T ( n 2 i ) 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}) T(n)=T(2n​)+T(4n​)+T(8n​)+...+T(1)=∑i=1logn​T(2in​)
所以递归树的结点有logn个分支，且每个分支的深度不断减少。
最左边的分支 T ( n 2 ) T(\frac{n}{2}) T(2n​)，有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; } 12345

这个算法的时间复杂度为 O ( n ) O(n) O(n)，有没有办法将它优化到 O ( l o g n ) O(logn) 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 elsereturn xpow(x, n/2) * xpow(x, n/2); } 123456789

考虑是否有重复计算的部分（是否能优化树的部分分支）
可以很明显看出 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 elsereturn t * t; } 12345678910

优化后该算法的时间复杂度为 O ( l o g n ) O(logn) O(logn)

总结一下，虽然上述例子稍微有点特殊，但是思路是可以借鉴的。一连串的递归首先考虑是否能转化成树的结构，然后再观察树的一些分支是否重复计算来进行优化。

网址：递归优化技巧 https://www.yuejiaxmz.com/news/view/548797

相关内容

常数优化技巧
递归思想——关于递归的多个例子详解
算法优化大揭秘：12个加速算法运行速度的实用技巧
Python中递归阶乘
浅谈简单的程序优化技巧（C++）
递归和动态规划（python)
大臣的旅行费用与递归
【考试技巧】输入输出优化
优化技巧
二叉树非递归遍历

随便看看