Java编程内功-数据结构与算法「递归」（java基本数据结构和算法）-人工智能-知优网

递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得整洁.

概念

简单地说:递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得整洁.

递归能解决什么样的问题

各种数学问题如:八皇后问题,汉诺塔,阶乘问题,迷宫问题,球和篮子问题(google编程大赛).
各种算法中也会用到递归,比如快排,归并排序,二分查找,分治算法等.
将用栈解决的问题->递归代码比较简洁.

递归需要遵守的规则

执行一个方法时,就创建一个新的受保护的独立空间(栈空间).
方法的局部变量是独立的,不会相互影响.
如果方法中使用的变量是引用类型的变量(比如数组),就会共享该引用类型的数据.
递归必须向退出递归的条件逼近,否则就是无限递归.
当一个方法执行完毕,或者遇到return,就会返回,遵守谁调用就将结果返回给谁,同时当方法执行完毕或者返回时,该方法也就执行完毕.

递归回溯解决迷宫问题

在一个二维数组中,1表示墙,求小球从指定点到终点走过的路径.

packagecom.structures.recursion;
publicclassMiGong{
publicstaticvoidmain(String[]args){
//先创建二维数组模拟迷宫,地图
int[][]map=newint[8][7];
//使用1表示墙,迷宫的上下左右边全部置为1
for(inti=0;i<7;i++){
map[0][i]=1;
map[7][i]=1;
}
for(inti=0;i<8;i++){
map[i][0]=1;
map[i][6]=1;
}
//设置挡板
map[3][1]=1;
map[3][2]=1;
//输出地图
System.out.println("原始地图");
for(inti=0;i<8;i++){
for(intj=0;j<7;j++){
System.out.print(map[i][j]+"");
}
System.out.println();
}
//使用递归回溯找路
setWay(map,1,1);
System.out.println("按策略走过的路");
for(inti=0;i<8;i++){
for(intj=0;j<7;j++){
System.out.print(map[i][j]+"");
}
System.out.println();
}
/*
原始地图
1111111
1000001
1000001
1110001
1000001
1000001
1000001
1111111
按策略走过的路
1111111
1200001
1222001
1112001
1002001
1002001
1002221
1111111
*/
}
/**
*使用递归回溯来找路,如果能map[6][5]位置,则说明通路找到
*约定:当map[i][j]为0表示该点没有走过,当为1表示墙,当为2表示通路可以走,3表示该点已经走过,但是走不通
*在走迷宫时,需要确定一个策略(方法),下->右->上->左,如果走不通再回溯
*
*@parammap表示地图
*@parami从哪个位置开始行坐标
*@paramj从哪个位置开始列坐标
*@return如果找到通路,就返回true,否则返回false
*/
publicstaticbooleansetWay(int[][]map,inti,intj){
if(map[6][5]==2){
returntrue;
}else{
if(map[i][j]==0){//如果当前这个点没有走过
//按照策略下->右->上->左走
map[i][j]=2;//假定该点可以走通
if(setWay(map,i+1,j)){//向下走
returntrue;
}elseif(setWay(map,i,j+1)){//向右走
returntrue;
}elseif(setWay(map,i-1,j)){//向上走
returntrue;
}elseif(setWay(map,i,j-1)){//向左走
returntrue;
}else{
map[i][j]=3;//说明该点是死路,走不通
returnfalse;
}
}else{
//如果map[i][j]!=0,说明可能是1,2,3
returnfalse;
}
}
}
}

八皇后问题

在8*8的国际象棋上摆放8个皇后,使其不能相互攻击,即:任意两个皇后都不能处于同一行,同一列,同一斜线上,问有多少种摆法.

理论上应该创建一个二维数组来表示棋盘,但是实际上可以通过算法,用一个一维数组即可解决问题,arr[8]={0,4,7,5,2,6,1,3},对应arr下标表示第几行,即第几个皇后,arr[i]=val,val表示第i+1个皇后,放在第i+i行的val+1列.

packagecom.structures.recursion;
publicclassQueen8{
//表示共有多少个皇后
privateintmax=8;
//定义数组array,保存皇后放置位置的结果,比如arr[8]={0,4,7,5,2,6,1,3}
privateint[]array=newint[max];
staticintcount=0;
publicstaticvoidmain(String[]args){
Queen8queen8=newQueen8();
queen8.check(0);
System.out.printf("总共%d摆法\n",count);//92种
}
//放置第n个皇后
publicvoidcheck(intn){
if(n==max){//n=8说明前面已经放好
print();
count++;
return;
}
//依次放入皇后并判断是否冲突
for(inti=0;i<max;i++){
//先把当前的皇后n,放到改行的第1列
array[n]=i;
//判断当放置第n个皇后到第i列是,是否冲突.
if(judge(n)){
//接着放n+1皇后,开始递归
check(n+1);
}
}
}
//查看当放置第n个皇后时,就去检测该皇后是否前面已经摆放的皇后冲突
privatebooleanjudge(intn){
for(inti=0;i<n;i++){
//array[i]==array[n]表示第n个皇后是否与之前的皇后在同一列
//Math.abs(n-i)==Math.abs(array[n]-array[i])表示第n个皇后是否与之前在同一个斜线
if(array[i]==array[n]||Math.abs(n-i)==Math.abs(array[n]-array[i])){
returnfalse;
}
}
returntrue;
}
//将皇后摆放的位置输出
publicvoidprint(){
for(inti=0;i<array.length;i++){
System.out.print(array[i]+"");
}
System.out.println();
}
}