前言
刚开始接触递归的时候会,我相信大部分小伙伴肯定和我一样一脸懵,又感叹太神奇了,这么短短的几行代码,竟然做了这么多事。
其实我们不要畏惧它就很好学了,无非就是思考递归边界和递归式这两个概念如何运用.把原问题分解为若干个子问题,我们只要写出递归式和边界,剩下的交给电脑处理,我们就是老板，它是为我们服务的.不懂的代码我们尽量画出递归图帮助理解,尽量不要在脑子里去思考他们的压栈过程,我们的脑子能压几个栈啊！！反而把自己搞得混乱.
最近我看了挺多关于递归的知识,跟大家谈谈我的看法,希望能给你带来一点点帮助.
递归的基本概念
有一个看似玩笑的对递归的定义:“要理解递归,你要先理解递归,直到你能理解递归",但是这对递归的解释算是十分直观的,递归就在于反复调用自身函数,但是每次把问题缩小,直到范围缩小到可以直接得出边界数据的结果,然后再在返回的路上求出对应的解。在这点看来,递归很适合用来实现分治思想.
递归的三大要素
为了更好的引出三大要素,我们先举个简单的例子:使用递归求解n的阶乘
1.找重复(子问题)——递归式
首先给出n!的计算式:n!=1*2*3*......*n;这个递推形式n!=n*(n-1)!,于是就把规模为n的问题转换成了求解规模为n-1的问题.如果用f(n)表示n!,就可以写成f(n)=f(n-1)*n(递归式),这样我们就达到了我们的目的把规模变小了——子问题。(注:找递归式是递归中最难的一步,需要我们多接触题目去总结经验,下面我会跟大家一起练几题,下去一定要多加练习,把遇到的循环改成递归试试)
int f(n) { return f(n-1)*n }
2.找重复中的变化量——参数
变化的量应该做为参数,这道题只有一个变量n,很显然做为参数,这点的作用在这道题看上去就不是那么重要了,下面我会讲解一道数组求和题目,体现出它的价值.
3.找参数变化趋势——设计出口
上面的代码存在自己调用自己的情况,那么这就叫做递归,但是上面的代码不够规范,甚至出现了问题,它会不断调用自己,掉入无底洞,最后出现栈溢出的错误.
那么我们就要为其找“出口",也就是我们需要找出当参数为啥时，递归结束，之后直接把结果返回.
很显然上面的例子,当n==1时,为出口此时f(1)=1;下面我们来完善代码
int f(int n) { if (n == 1) { return 1; } return f(n - 1) * n; }
到此,我们f(n)功能内部的代码也就完成了.
上面我们说过,不懂的代码要画递归图帮助其理解,就以这个为例跟大家画一个
为了更好的掌握递归的三要素,下面我和大家一起进行做题练习
切蛋糕思维:递归简单练习题
数组求和:
#include<iostream> int main() { int a[]={1,2,3,4,5,6,7}; //递归函数sum return 0; }
1.找重复——递归式
找递归式我们就遵循把原问题化成若干个子问题,就像我们切蛋糕一样,先切一块吃掉,剩下的用递归交给下一步吃掉,这道题我们只划第一个元素出来，剩下的交给递归处理
int sum(int a[]) { return a[0]+sum(a); }
这一步我们就完成了
2.找重复中的变化量——参数
在这个重复的过程中我们会发现数组的区间在不停的缩小,数组的起始点在变化,发现有个东西在不断的往右走.但是上面写的递归式是没有变化区间的，一直是从头开始递归.分析到这我们会发现我们应该去找重复中变化的量,来添加一个参数.我这里多加个参数n,来记录数组的长度
int sum(int a[],int n,int begin) { return a[begin]+sum(a,n,begin+1); }
3.找参数变化的趋势——设计出口
如果begin等于数组的最后一个元素下标,我们直接返回,此时就是出口
int sum(int a[],int n,int i) { if (i == n-1) { return a[i]; } return a[i] + sum(a, n,i+1); }
这样就搞定啦,是不是很简单,肯定有大佬吐槽这个题目简单,刚开始嘛,咱们先从简单入手熟练运用三要素,遇到难题也是一样的套路.话不多说,再来一个
翻转字符串
int main() { string sa = "wewe89r"; cout << f(sa); return 0; }
1.找重复——递归式
这道题我们依旧可以用切蛋糕思维来找出递归式,为了更方便理解，我画个图
int f(string str) { return f(str.substr(1))+str.substr(0,1); //substr(0,1)表示从下标0开始取一个字符形成的串 //substr(1)表示从下标1开始到结尾形成的串 }
2.找重复中的变化量——参数
这道题字符串的长度在不停的变化,所以我们把字符串长度做为参数,而这里我运用了substr这个函数,不需要再添加新的参数,不过本质还是不断的缩小字符串的长度.
3.找参数变化的趋势——设计出口
如果字符串的长度小于等于1,这个程序就要结束了,找到此出口
string f(string str) { int len = str.length(); if (len <= 1) return str; return f(str.substr(1)) + str.substr(0, 1); //substr(0,1)表示从下标0开始取一个字符形成的串 } //substr(1)表示从下标1开始到结尾形成的串
好了到这里这道题也就结束了.相信到这里大家对三要素也有进一步的认识,以后练题就可以根据这个模式去想,想单靠一篇博客去深入一个思想那是不太现实的,所以还要靠自己平时多练习.
这一块就到这里,下面我带大家更深一步的学习。
巧用递推公式解最大公约数
正整数a与b的最大公约数是指a与b的所有公约数中最大的那个公约数,例如4和6的最大公约数是2,3和9的最大公约数是3。一般用gcd(a,b)来表示a和b的最大公约数,而求解最大公约数常用欧几里得算法。
欧几里得算法基于下面这个定理:
设a,b均为正整数,则gcd(a,b)=gcd(b,a%b);(证明略过）
由上面这个定理可以发现,如果a<b,那么定理的结果就是a和b交换;如果a>b,那么通过这个定理总可以将数据规模变小,并且减小的很快。这样似乎可以很快得到结果,知识还需要一个东西:递归边界,即数据规模减小到什么程度使得可以算出结果来.很简单,众所周知:0和任意一个整数a的最大公约数都是a，个结论就可以当作递归边界.由此我们很容易想到将其写成递归的形式,因为递归的两个关键已经得到:
1.递归式:gcd(a,b)=gcd(b,a%b);
2.递归边界:gcd(a,0)=a.
于是得到下面的代码:
int gcd(a,b) { if(a==0) return a; else return gcd(b,a%b); }
别有洞天:递归形式进行插入排序
对于几种算法前面我已经有详细介绍,有忘记的伙伴可以看下我这篇博客:常见的七种排序算法
直接上代码:(还是按照上面的三要素即可)
#include<iostream> using namespace std; void InsertSort(int* a, int n) { if (n == 0) { return; } InsertSort(a, n - 1); int x = a[n]; int index = n - 1; while (index>-1&&x < a[index]) { a[index + 1] = a[index]; index--; } a[index+1] = x; } int main() { int a[] = { 1,3,4,2,6,5 }; InsertSort(a, sizeof(a)/sizeof(int)-1); for (auto x : a) { cout << x << " "; } return 0; }
二分查找的递归解法
全范围二分查找
等价于三个子问题
* 左边找(递归)
*中间比
*右边找(递归)
#include<iostream> using namespace std; int binarySearch(int* a, int left, int right, int key) { while (left < right) { int mid = left + ((right - left) >> 1); int number = a[mid]; if (number < key) { return binarySearch(a, mid + 1, right, key); } else if (number > key) { return binarySearch(a, left, mid - 1, key); } else return mid; } } int main() { int a[] = { 1,2,3,4,5,6,7,8,9,10 }; int find=binarySearch(a, 0, sizeof(a)/sizeof(int)-1, 5); cout << find << endl; return 0; }
多分支递归:斐波那契数列
斐波那契数列满足f(0)=1,f(1)=1,f(n)=f(n-1)+f(n-2)(n>=2)的数列,数列的前几项为1,1,2,3,5,8，，，。由于从定义中已经熟悉递归边界为f(0)=1和f(1)=1，且递归式为f(n)=f(n-1)+f(n-2)(n>=2)，因此我们可以照仿求解n的阶乘的写法,写出其第n项的程序:
int f(int n) { if(n==1||n==2) return 1; else return f(n-1)+f(n-2); }
我们也知道这样写代码虽然简洁易懂，但是十分低效，低效在哪里？假设 n = 15，请画出递归树：
这个递归树怎么理解,当要计算f(15)时,就要计算f(14)和f(13)，要计算f(14)就要计算 f(13)和f(12)，以此类推。最后遇到 f(1) 或者 f(2) 的时候，结果已知，就能直接返回结果，递归树不再向下生长了。
很明显的观察到在进行递归计算的时候重复计算了f(13),f(12)等式子,计算数越大重复计算越多,这个是很恐怖的事情,所以我们要想办法进行优化.
浅谈递归的一些优化思路
明确了问题，其实就已经把问题解决了一半。即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。
一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典），思想都是一样的。
int f(int n) { if(n ==0||n==1) { return 1; } //先判断有没计算过 if(arr[n] != -1) { // 已经计算过，不用再计算了 return arr[n]; } else { // 没有计算过，递归计算,并且把结果保存到 arr数组里 arr[n] = f(n-1) + f(n-1); reutrn arr[n]; } }
至此，带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。实际上，这种解法和常见的动态规划解法已经差不多了，只不过这种解法是「自顶向下」进行「递归」求解，我们更常见的动态规划代码是「自底向上」进行「递推」求解。
啥叫「自顶向下」？注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 这两个 base case，然后逐层返回答案，这就叫「自顶向下」。
啥叫「自底向上」？反过来，我们直接从最底下、最简单、问题规模最小、已知结果的 f(1) 和 f(2)（base case）开始往上推，直到推到我们想要的答案 f(20)。这就是「递推」的思路，这也是动态规划一般都脱离了递归，而是由循环迭代完成计算的原因。
自底向上:
public int f(int n) { if(n == 1||n==2) return 1; int f1 = 1; int f2 = 2; int sum = 0; for (int i = 3; i <= n; i++) { sum = f1 + f2; f1 = f2; f2 = sum; } return sum; }
当然还有一些递归加速——剪枝,递归和回溯的操作来优化递归,这里不做过多赘述，以后会讲解.
题目实战
下面两道比较经典的递归练习,可以练一下手
最后总结
以上就是我对递归的理解,希望能起到一点抛砖引玉的作用,有什么不懂的地方可以评论区留言,大家一起讨论,言而总之，总而言之,就是要熟悉我上面说的递归三要素,多练习总结,融会贯通。
