Java递归算法经典实例【黑马java培训】

更新时间:2019年07月26日 10时48分38秒来源:黑马程序员论坛

简单递归定义

什么叫递归？（先定义一个比较简单的说法，为了理解，不一定对）

递归：无限调用自身这个函数，每次调用总会改动一个关键变量，直到这个关键变量达到边界的时候，不再调用。

比如说我要你先求一个N!的结果

你说我会用循环啊（没错，但是现在是学递归）

[AppleScript] 纯文本查看 复制代码

private int factorial(int x,int ans)
{
if(x==1)
return ans;
factorial(x-1,ans*x);
}

怎么样，对于Java基础如果掌握的还行的话，这段代码应该很好理解。递归，顾名思义就是“递”和“归”。也就是说，写每一个递归函数的时候，都应该在写之前考虑清楚，哪里体现了“递”，哪里体现了“归”。

但是常常递归函数会比较复杂， “递”和“归”看起来并不是那么明显，这就需要我们进一步来理解递归算法的思想。

比如说我现在要你用辗转相除法求出两个数的最大公约数，递归函数如下：

[AppleScript] 纯文本查看 复制代码

private int gcd(int a,int b)
{
return a%b==0?b:gcd(b,a%b);
}

这是一段很常用的代码，我们知道，在学习过程中不求甚解是最不应该的。因此现在来仔细看一看。这里的“递”和“归”放在同一行。首先进行判断a==b?（我们可以想象成“归”的内容，如果这个条件符合的话）。当然，如果不符合这个判断，那就继续“递”，也就是继续进行gcd(b,a%b);

看到这里，你就会发现，递归不就是循环的另一种方式么？

说对了一半，不过递归是一种思想，现在还暂时不能说透，需要大家先比较一下循环和递归的相同点和不同点（饭一口一口吃，别着急）

递归与循环的区别与联系

相同点：

都是通过控制一个变量的边界（或者多个），来改变多个变量为了得到所需要的值，而反复而执行的；
都是按照预先设计好的推断实现某一个值求取；（请注意，在这里循环要更注重过程，而递归偏结果一点）

不同点：

递归通常是逆向思维居多，“递”和“归”不一定容易发现（比较难以理解）；而循环从开始条件到结束条件，包括中间循环变量，都需要表达出来（比较简洁明了）。

简单的来说就是：用循环能实现的，递归一般可以实现，但是能用递归实现的，循环不一定能。因为有些题目①只注重循环的结束条件和循环过程，而往往这个结束条件不易表达（也就是说用循环并不好写）；②只注重循环的次数而不注重循环的开始条件和结束条件（这个循环更加无从下手了）。

递归的经典应用

来看看“汉诺塔问题”

如图，汉诺塔问题是指有三根杆子A,B,C。C杆上有若干碟子，把所有碟子从A杆上移到C杆上，每次只能移动一个碟子，大的碟子不能叠在小的碟子上面。求最少要移动多少次？

这是一个循环只注重循环次数的常见例子，我们知道，用循环有点无从下手（就目前作者水平来看），但是递归就很好写了。

汉诺塔，什么鬼，我不会啊？

别急，慢慢来。

我们首先需要一点思维：解决n块盘子从A移动到C，那么我只需要先把n-1块盘子从A移到B，然后把最下面的第n块盘子从A移到C，最后把n-1块盘子从B移到C（这就完成了）。

等等，那么如何把n-1块盘子从A移到B？

很好，这说明你已经开始递归入门了。

同样这样去想：解决n-1块盘子从A移动到B，那么我只需要先把n-2块盘子从A移动到C，然后把倒数第二块盘子从A移到B，最后把n-2块盘子从C移到B（这就完成了）。

这就是递归的“递”！

那么“归”呢？n==1的时候？

实际上这里面已经使用到了一点点栈的思想（即最上面的最先考虑变化），但其实递归有的时候就是真的可以理解为栈！

到了这一步，相信大家应该已经有所明白。循环其实就是一个控制变量从开始条件走到结束条件的过程（在循环的过程顺带把其他变量也改变一下），因此需要控制变量，开始条件，结束条件（缺一不可）。但是递归只要告诉你“归”是什么，如何去“递”，不管过程如何，只要计算结果即可。

递归可以是多个“递”，也可以是多个“归”；而循环由始至终都只由一个变量控制（就算有几个变量同时控制）

也只有一个出口，每次循环也只是一个“递”。

再看一个例子

用二分思想建立二叉树（通常的是递归实现），比如说线段树

[AppleScript] 纯文本查看 复制代码

//root 节点序号
//left 节点维护的左边界
//right 节点维护的右边界
private void build(int root,int left,int right)
{
if(left==right)
return ;
int mid=(left+right)/2;
build(root*2，left,mid);
build(root*2+1,mid+1,right);
}

如果你是新手看不太懂也没关系，现在最主要的是明白：在这个程序里面只有一个“归”，但是有两个“递”。那么如果学过一点但是对这一块还不明白的怎么办呢？别急，听我来解释：

实际上，这两个 “递”是按照先后分别进行的，等到第一个“递”执行完（也就是到了“归”的条件之后），才开始执行第二个“递”。也就是说，通常在建树的时候，都不是一层一层同时建的，而是先建一棵子树，等到这棵子树全部建完之后，才开始建立另外一棵子树。

那就会有人问了，一棵子树建完了之后root值不会变么，root值变了之后还怎么建另外一棵子树呢？

root值不会变！大家请注意，这里root*2是写在递归函数里面的，实际上并没有赋值？为什么要这样写？因为如果不这样写，你直接写在外边的话，一棵子节点到达叶子节点之后，需要一层一层往上回溯（在这里提到了回溯的思想），而回溯就会无故产生很多不必要的时间复杂度，降低了递归效率（实际上递归的时间效率本来就有一点偏低）。

所以到目前为止，我只是介绍一些很常见的简单的递归，但是在接下来，我就需要说一些比较深层一点的知识了。

首先要理解一下什么是回溯

回溯：在递归的过程中由于改变的量需要倒退到某一个位置而执行的步骤。

先来看一个简单的素数环问题：

给出1到n的n个连续的正整数（这里n暂时等于6），并且把这n个数填写在如下图的n个圆圈里面（当然是不重复不遗漏了）。要求是每一个位置上面的数跟他相邻的数之和都为一个素数，打印并输出最后满足条件的情况。

首先明白，开始条件是 1，把1填写在第一个位置，然后在剩下的n-1个数字里找到一个满足与1的和是一个素数的数（当然如果有多个，先靠前的先考虑）。接下来再继续从剩下n-2个数字里找到一个与这个数的和又是一个素数的数（当然如果有多个，同上。）。。。最后的一个数只要满足与最开始的数1之和是一个素数的话，这个情况就满足了（就可以打印输出这样一个例子了）

但事情并没有想象的那么简单。。。（告诉我如果在中途寻找的过程中从剩下的数里找不到与当前数的的和是一个素数的情况出现怎么办？在线等）

这就表明这样一条路终归是一条思路，你要往回走了！这就很符合我们给回溯的定义了，此时这个改变的量需要倒退的前面一步从另外一个方向寻找了。（还是举栗子吧）

比如说：

1->2->3->4 突然发现5和6都不满足要求了

那么就倒退，准备找另外满足要求的数

1->2->3 又发现除了4以外3跟5或者3跟6也不满足要求

那就继续倒退，继续准备找另外满足要求的数

1->2->5->6 接下来发现6跟3或者6跟4不满足要求

…(还想继续下去？乖，别这样，我也累啊，看一两个就行了，啊！) 最后发现满足条件的一个是1->4->3->2->5->6

大家应该已经懂了，上面的倒退，实际上就是回溯。（暂时这样简单的理解吧，错了也不能怪你们）

实际上，递归+回溯就已经是dfs(深度优先搜索)的内容范畴了。

[AppleScript] 纯文本查看 复制代码

private void dfs(int x)
{
if(x==n+1&&prime(a[x-1]+a[1])) //如果满足条件就可以打印输出数据了，这里就是“归”
{
for(int i=1;i<n;i++)
cout<<a[i]<<" ";
cout<<a[n]<<endl;
}
else //否则就继续“递”
{
for(int i=2;i<=n;i++)
{
if(!vis[i]&&prime(i+a[x-1]))
{
vis[i]=1; //vis[]是一个标记数组，表示当前的数字已经被使用过了
a[x]=i;
dfs(x+1); //“递”的入口
vis[i]=0; //请注意，回溯点在这里
}
}
}
}

大家可能前面都看懂了，比如说“递”和“归”，vis[]标记数组什么的。但是最后一个vis=0是啥意思？难道不多余么？

不多余！前面我已经拿建树给大家讲过递归的“工作原理”，它是先无限递归，然后到达某个条件之后，回溯到上面一个位置，继续向其他方向递归。而这个vis=0就是清楚当前数字的标记，表示从当前节点开始，之后递归过的内容统统清空（也就是回溯）。然后根据循环，进行下面一个方向的继续递归。

总结
（1）把递归当成复杂的循环来写，如果不明白过程，多模拟几遍数据；
（2）把递归逆向写的时候当做一个栈来实现（即符合先进先出的思想）；
（3）当递归和回溯结合在一起的时候需要明白递归次数和统计次数之间的练习和区别；
（4）但递归有多个“递”和“归”的时候，选择一个重点的“递”和“归”作为匹配，即时题目即时分析，注意随机应变即可。

推荐了解热门学科

java培训	Python人工智能	Web前端培训	PHP培训
区块链培训	影视制作培训	C++培训	产品经理培训
UI设计培训	新媒体培训	产品经理培训	Linux运维
大数据培训	智能机器人软件开发

传智播客是一家致力于培养高素质软件开发人才的科技公司，“黑马程序员”是传智播客旗下高端IT教育品牌。自“黑马程序员”成立以来，教学研发团队一直致力于打造精品课程资源，不断在产、学、研3个层面创新自己的执教理念与教学方针，并集中“黑马程序员”的优势力量，针对性地出版了计算机系列教材50多册，制作教学视频数+套，发表各类技术文章数百篇。

传智播客从未停止思考

传智播客副总裁毕向东在2019IT培训行业变革大会提到，“传智播客意识到企业的用人需求已经从初级程序员升级到中高级程序员，具备多领域、多行业项目经验的人才成为企业用人的首选。”

中级程序员和初级程序员的差别在哪里?
项目经验。毕向东表示，“中级程序员和初级程序员最大的差别在于中级程序员比初级程序员多了三四年的工作经验，从而多出了更多的项目经验。“为此，传智播客研究院引进曾在知名IT企业如阿里、IBM就职的高级技术专家，集中研发面向中高级程序员的课程，用以满足企业用人需求，尽快补全IT行业所需的人才缺口。

何为中高级程序员课程?

传智播客进行了定义。中高级程序员课程，是在当前主流的初级程序员课程的基础上，增加多领域多行业的含金量项目，从技术的广度和深度上进行拓展。“我们希望用5年的时间，打造上百个高含金量的项目，覆盖主流的32个行业。”传智播客课程研发总监于洋表示。

黑马程序员热门视频教程【点击播放】

Python入门教程完整版（懂中文就能学会）	零起点打开Java世界的大门
C++\| 匠心之作从0到1入门学编程	PHP\|零基础入门开发者编程核心技术
Web前端入门教程_Web前端html+css+JavaScript	软件测试入门到精通

全国中心

Java递归算法经典实例【黑马java培训】

相关阅读