递归算法：自己调用自己
简单实例引入递归:
斐波拉契树列： 1,1,2,3,5,8...n 规则：前面俩个数的和等于第三个数。注意：n=1或者n=2的时候算法不成立(特殊性)
public static void main(String[] args) {
//斐波拉契数列 循环实现
// int num1 = 1;
// int num2 = 1;
// int num3 = 0;
// int n = 6;
//
// for (int i = 3;i<=n;i++){
// num3 = num1 + num2;
// num1=num2;
// num2=num3;
// }
// System.out.println(num3);
//递归实现
int run = run(6);
System.out.println(run);
}
static int run(int n){
if(n == 1 || n == 2){
return 1;
}else {
return run(n-1) + run(n -2);
}
}
递归在普通情况下使用性能是很低的，那么什么时候使用递归呢？看下面实例
树遍历：(文件夹的遍历)
public static void main(String[] args) {
//树遍历, 文件夹....
play(new File("D:\\Tools"));
}
static void play(File file){
//获取当前文件夹下所有子文件夹
File[] files = file.listFiles();
for (int i=0; i<files.length; i++){
if (files[i].isFile()){ //文件
System.out.println(files[i].getName());
}else { //文件夹
play(files[i]);
}
}
}
排序算法-快速排序: 5,3,8,6,4,2,9
java代码实现，如下：
public static void main(String[] args) {
//树遍历, 文件夹....
// play(new File("D:\\Tools"));
//排序---快速排序
int[] ints = {5,3,7,8,2,4,9,6};
sort(ints,0,ints.length-1);
for (int m=0; m < ints.length; m++){
System.out.print(ints[m]+","); // 4,3,2,5,8,7,9,6
}
}
static void sort(int[] ints, int s, int e){
if(s < e){
int index = sortUnit(ints, s , e);
sort(ints,s, index-1);
sort(ints,index+1, e);
}
}
//快速排序
static int sortUnit(int[] ints, int s, int e){
int num = ints[s]; //标杆
int i = s;
int j = e;
while (i<j){
while (i<j){
if(ints[j] <= num){ //负责找小的
ints[i] = ints[j];
break;
}
j--;
}
while (i<j){
if(ints[i] >= num){ //负责找大的
ints[j] = ints[i];
break;
}
i++;
}
}
ints[i] = num;
return i;
}
八皇后: 来自国际象棋.
8*8的棋牌格， 没边16个棋子，前面一排称为 兵: 兵第一步可以走1~2格，从第二步开始一只能走一格，只能向前走，兵的吃法是吃左斜上角和右斜上角的兵。兵如果走到底的话，就可以变成任意一颗棋子。后面一排就是将了， 最边上的俩个就是中国象棋中的 “车” 走法都一样 ，接下来是“马” 马走日,但是是周围6格. 接下来就是“相”, 是斜着走，没有距离限制.分黑白，然后就是皇后, 走法:横,竖,斜无距离限制，最后皇帝: 横竖斜同时只能走一步. 车,后移位的规则比较复杂。
代码实现 如下：
public class Test04 {
private static int[][] map = new int[8][8]; //表示棋牌, 默认0表示没有皇后, 1表示放了皇后.
public static void main(String[] args) {
play(0);
}
static int count = 1;
//显示棋盘
private static void show(){
System.out.println("第"+count+"种摆法");
count++;
for (int i=0; i< 8; i++){
for (int j=0; j<8;j ++){
System.out.print(map[i][j]+" ");
}
System.out.println();
}
}
//验证是否可以放皇后
private static boolean check(int row, int col){
//上面
for (int i=row-1; i>=0;i--){
if (map[i][col] == 1) {
return false;
}
}
//左斜上
for (int i=row-1,j=col-1; i>=0 && j>=0;i--,j--){
if (map[i][j] == 1) {
return false;
}
}
//右斜上
for (int i=row-1,j=col+1; i>=0 && j<8;i--,j++){
if (map[i][j] == 1) {
return false;
}
}
return true;
}
//放皇后
private static void play(int row){
for (int i=0; i<8; i++){
if(check(row,i)){
//可以放
map[row][i] = 1;
if(row == 7){
//是否最后一行
show();
map[row][i] = 0;
}else {
play(row+1); //下一行
//当调用结束时去掉当前设置皇后
map[row][i] = 0;
}
}
}
}
}
