一、简介

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

<>二、用一个例子引出递归概念
public static void test(int n){ if(n>2){ test(n-1); }
System.out.println("n="+n); }
打眼一看,很low,很简单,4,3,2无疑。

为了验证我的聪明才智,输出一把吧

三、递归调用规则(很重要)

1、执行一个方法时,就创建一个新的受保护的独立空间(栈空间);

2、方法的局部变量是独立的,不会相互影响,比如变量n;

3、如果方法中使用的是引用类型变量(比如数组),就会共享该引用类型的数据;

4、递归必须向退出递归的条件逼近,否则就是无限递归,StackOverflowError;

5、当一个方法执行完毕,或遇到return,就会返回,遵守谁调用就将结果返回给谁,同时当方法执行完毕或return时,该方法也就执行完毕。

四、递归能解决什么样的问题

<>1、各种数学问题

比如八皇后问题、哈诺塔、阶乘问题、迷宫问题、球和篮子的问题(Google编程大赛)。

<>2、各种算法中也会使用递归

比如快排、归并排序、二分查找、分治算法。

<>3、栈解决的问题都可以用递归

代码更加简洁。

五、迷宫问题

1、代码实现
package dataStructure.recursion; public class Labyrinth { public static void
main(String[] args) { //迷宫问题 //0 表示该点没有走过 当为 1 表示墙 ; 2 表示通路可以走 ; 3
表示该点已经走过,但是走不通 int[][] map = new int[8][7]; for(int i=0;i<8;i++){ for (int j =
0; j < 7; j++) { map[0][j] = 1; map[7][j] = 1; map[i][0] = 1; map[i][6] = 1; }
} //设置挡板, 1 表示 map[3][1] = 1; map[3][2] = 1; for (int i = 0; i < 8; i++) { for
(int j = 0; j < 7; j++) { System.out.print(map[i][j]+" "); }
System.out.println(); } setWay(map,1,1); System.out.println("迷宫走过之后地图"); for
(int i = 0; i < 8; i++) { for (int j = 0; j < 7; j++) {
System.out.print(map[i][j]+" "); } System.out.println(); } } //使用递归回溯来给小球找路
//说明 //1. map 表示地图 //2. i,j 表示从地图的哪个位置开始出发 (1,1) //3. 如果小球能到 map[6][5]
位置,则说明通路找到. //4. 约定: 当map[i][j] 为 0 表示该点没有走过 当为 1 表示墙 ; 2 表示通路可以走 ; 3
表示该点已经走过,但是走不通 //5. 在走迷宫时,需要确定一个策略(方法) 下->右->上->左 , 如果该点走不通,再回溯 private static
boolean setWay(int[][] map,int i,int j){ if(map[6][5] == 2){ return true;
}else{ if(map[i][j]==0){ map[i][j] = 2; if(setWay(map,i+1,j)){//下 return true;
}else if(setWay(map,i,j+1)){//右 return true; }else if(setWay(map,i-1,j)){//上
return true; }else if(setWay(map,i,j-1)){//左 return true; }else{ map[i][j] = 3;
return false; } }else { return false; } } } }
2、控制台输出

注:1表示墙,2表示你走的路,0表示没走的路。

这个还是挺简单的!

 

每一篇博客都是一种经历,程序猿生涯的痕迹,知识改变命运,命运要由自己掌控,愿你游历半生,归来仍是少年。

欲速则不达,欲达则欲速!

技术
©2019-2020 Toolsou All rights reserved,
详解ubuntu14.04如何设置静态IPQCustomPlot系列(5)-实时动态曲线比尔·盖茨:疫情后彻底恢复正常可能要到2022年末华为认证HCIA-AI人工智能Python基础知识整理笔记百度、阿里、腾讯内部岗位级别和薪资结构,附带求职建议!Jsp+Ajax+Servlet+Mysql实现增删改查(一)2021年1月程序员工资统计,平均14915元Faster RCNN系列算法原理讲解(笔记)经典算法-递归(生兔子案例)