java递归函数 Java递归算法经典实例

简单递归定义

什么是递归？(先定义一个相对简单的说法，对于理解不一定是真的)

递归:无限期调用这个函数，每次调用的时候总会改变一个键变量，直到这个键变量到达边界，就不会再调用了。

比如我要你先要个n！的结果

你说我会用循环(是的，但是现在我学递归)

privateintfactorial(intx,intans) { if(x==1) returnans; factorial(x-1,ans*x); }

好吧，如果你对Java基础有很好的把握，那么这段代码应该很好理解。递归顾名思义就是“传递”和“返回”。也就是说，在编写每一个递归函数的时候，都要在编写之前考虑清楚，在哪里体现“传递”，在哪里体现“返回”。

但是递归函数往往比较复杂，“传递”和“返回”似乎没有那么明显，这就需要我们进一步理解递归算法的思想。

举个例子，现在我想让你通过除以匝数和相位，求出两个数的最大公约数。递归函数如下:

privateintgcd(inta,intb) { returna%b==0?b:gcd(b,a%b); }

这是一个非常常用的代码，我们知道不求解答是最糟糕的学习。所以现在仔细看看。这里“送”和“退”在一条线上。一、判断a==b？(我们可以想象“返回”的内容，如果满足这个条件)。当然如果不符合这个判断，那么继续“通过”，也就是继续gcd(b，a % b)；

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

说对了一半，但是递归是一个想法，暂时无法解释。我们需要先比较循环和递归的异同(一个一个吃，不用担心)

递归与循环的区别与联系

相似之处:

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

差异:

递归通常是逆向思维，“传递”和“返回”不一定容易发现(难以理解)；循环需要从开始条件到结束条件来表达，包括中间的循环变量(相对简洁)。

简单来说，递归一般可以通过循环实现，但是如果可以通过递归实现，循环就不一定了。因为有些题目(1)只关注循环的结束条件和过程，而且往往这个结束条件不容易表达(也就是说不容易随循环写)；(2)只关注循环次数，不关注循环的开始和结束条件(这个循环更难开始)。

递归的经典应用

我们来看看“河内塔问题”

如图，汉诺塔问题是指有A、B、C、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时？

inti; // 记录步数 //i 表示进行到的步数,将编号为n的盘子由from柱移动到to柱(目标柱) privatevoidmove(intn,charfrom,charto){ System.out.println("第%d步:将%d号盘子%c---->%cn",i++,n,from,to); } //汉诺塔递归函数 //n表示要将多少个"圆盘"从起始柱子移动至目标柱子 //start_pos表示起始柱子,tran_pos表示过渡柱子,end_pos表示目标柱子 privatevoidHanio(intn,charstart_pos,chartran_pos,charend_pos) { if(n==1) //很明显,当n==1的时候,我们只需要直接将圆盘从起始柱子移至目标柱子即可. move(n,start_pos,end_pos); else { Hanio(n-1,start_pos,end_pos,tran_pos); //递归处理,一开始的时候,先将n-1个盘子移至过渡柱上 move(n,start_pos,end_pos); //然后再将底下的大盘子直接移至目标柱子即可 Hanio(n-1,tran_pos,start_pos,end_pos); //然后重复以上步骤,递归处理放在过渡柱上的n-1个盘子 //此时借助原来的起始柱作为过渡柱(因为起始柱已经空 了) } }

其实已经用了一点栈的思想(就是顶部先考虑变化)，但其实递归有时候真的可以理解为栈！

到了这个阶段，相信大家都应该明白了一些事情。其实循环是控制变量从开始条件到结束条件的过程(其他变量在循环的过程中顺便改变)，所以需要控制变量、开始条件和结束条件(都是必不可少的)。但是递归只告诉你什么是“返回”，怎么“传递”，不管过程是什么，只要计算结果就行了。

递归可以是多次“传递”，也可以是多次“返回”；循环从头到尾只由一个变量控制(即使几个变量同时被控制)

只有一个出口，每个周期只是一个“通行证”。

再看一个例子

用二分法建立二叉树(通常递归实现)，如线段树

//root 节点序号 //left 节点维护的左边界 //right 节点维护的右边界 privatevoid 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*2是用递归函数写的，但是没有赋值？为什么要这样写？因为不这样写的话，直接在外面写的话，一个子节点到达叶节点后，需要一个一个的回去(这里提到回溯的思想)，回溯会无故造成很多不必要的时间复杂度，降低递归效率(其实递归时间效率有点低)。

到目前为止，我只介绍了一些常见的简单递归，但接下来，我需要说一些更深层次的知识。

首先，我们必须明白什么是回溯

回溯:在递归过程中执行的一个步骤，因为变化的量需要反转到某个位置。

我们先来看一个简单的素环问题:

给n个从1到n的连续正整数(其中n暂时等于6)，填入下图的n个圆(当然不重复，也不省略)。要求是每个位置上面的数和与其相邻的数之和是素数。打印输出最终符合条件的情况。

首先了解起始条件是1，第一个位置填1，然后在剩下的n-1个数中找到一个满足与1的和是素数的数(当然如果有多个数，先考虑第一个)。接下来继续从剩下的n-2个数中找出一个是这个数和一个素数之和的数(当然如果有多个数，同上。)。。。只要最后一个数字和第一个数字1的和是素数(可以打印出这样的例子)，这种情况就满足了

但是事情并没有想象的那么简单。。。(告诉我，搜索到一半找不到当前数为素数的和怎么办？在线等。)

这说明这样的路终究是一条思路，你要回去！这符合我们对回溯的定义。这个时候，这个变化的量就需要倒着走，从另一个方向去寻找。(我们举栗子吧。)

例如:

1->；2->；3->；4突然发现5和6不符合要求

然后往回走，准备再找一个符合要求的数字

1->；2->；还发现3和5或3和6除4外不满足要求

然后继续倒退，继续准备另一个符合要求的数字

1->；2->；5->；6接下来，发现6和3或者6和4不符合要求

.....(想继续吗？乖，别这样，我也累了，就看一两个，啊！)最后发现其中一个条件是1->:4->；3->；2->；5->；六

大家应该都明白，上面的倒退其实是回溯。(暂时不能怪你犯错。)

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

privatevoiddfs(intx) { if(x==n+1&&prime(a[x-1]+a[1])) //如果满足条件就可以打印输出数据了，这里就是“归” { for(inti=1;i<n;i++) cout<<a[i]<<" "; cout<<a[n]<<endl; } else//否则就继续“递” { for(inti=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; //请注意，回溯点在这里 } } } }

大家之前可能都理解过，比如“pass”和“return”，vis[]标记数组等等。但是最后一个vis[i]=0是什么意思？是不是多余？

不是多余！我已经告诉过你递归的“工作原理”。首先是无限递归，然后达到一定条件后，回到上面的位置，继续向其他方向递归。而这个vis[i]=0是知道当前数的标志，意味着所有递归内容都是从当前节点清除空(即回溯)。然后，根据循环，按照以下方向继续递归。

摘要

(1)把递归写成一个复杂的循环，如果不理解过程，就把数据模拟几次；

(2)递归反写实现为栈(即符合先进先出的思想)；

(3)递归和回溯结合时，要了解递归次数和统计次数的做法和区别；

(4)但当递归中有多个“pass”和“return”时，选择一个键“pass”和“return”作为匹配，立即分析题目，注意随机应变。

推荐: