Java - 13 方法的递归

递归必须向退出递归的条件逼近

斐波那契数列

1. 当n=1，1
2. 当n=2，1
3. 当n >= 3，是前两个数的和

public class Recursion{
	public static void main(String[] args) {
		Fbnq f = new Fbnq();
		int n = 7;
		int res = f.num(n);
		if(res!=-1)
			System.out.println(res);
	}
}

class Fbnq {
	public int num(int n){
		if(n<1){
			System.out.println("text the number >= 1");
			return -1;			
		}else{
			if(n > 2)
				return num(n-1)+num(n-2);
			else
				return 1;
		}
	}
}

• 考虑无效输入的情况，返回-1，用-1控制输出

猴子吃桃

1. 第10天，1个桃子
2. 第9天，(1+1)*2个桃子

public class Recursion{
	public static void main(String[] args) {
		Monkey m = new Monkey();
		int res = m.peach(9);
		if (res!=-1)
			System.out.println(res);
	}
}

class Monkey {
	public int peach(int n){
		if(n == 10){
			return 1;
		}else if(n>=1&&n<=9){
			return (peach(n+1)+1)*2;
		}else{
			System.out.println("1-10");
			return -1;
		}
	}
}

迷宫

public class Migong{
	public static void main(String[] args) {
		// draw map
		int[][] map = new int[8][7];
		for(int i = 0; i<map[i].length; i++){
			map[0][i] = 1;
			map[7][i] = 1;
		}
		for(int i = 0; i<map.length; i++){
			map[i][0] = 1;
			map[i][6] = 1;
		}
		map[3][1] = 1;
		map[3][2] = 1;
		map[2][2] = 1;
		for(int i = 0; i<map.length; i++){
			for(int j = 0; j<map[i].length; j++){
				System.out.print(map[i][j]+" ");
			}
			System.out.println("");
		}

		// find way
		Migong m = new Migong();
		m.findWay(map, 1, 1);

		System.out.println("============");

		// check the map
		for(int i = 0; i<map.length; i++){
			for(int j = 0; j<map[i].length; j++){
				System.out.print(map[i][j]+" ");
			}
			System.out.println("");
		}
	}
}

class Migong {
	/* 1: barrier 2: can pass 3: cant pass */
	public boolean findWay(int[][] map, int i, int j){
		if(map[6][5] == 2)
			return true;
		else if(map[i][j] == 0){
			map[i][j] = 2; // assume it can go through
			// go down
			if(findWay(map, i+1, j))
				return true;
			// go right
			else if(findWay(map, i, j+1))
				return true;
			// go up
			else if(findWay(map, i-1, j))
				return true;
			// go left
			else if(findWay(map, i, j-1))
				return true;
			else{
				map[i][j] = 3;
				return false;
			}
		}else{
			return false;
		}
	}
}

Hanoi

public class Hanoi{
	public static void main(String[] args) {
		Hanoi tower = new Hanoi();
		tower.move(5,'A','C','B');
	}
}

class Hanoi {
	public void move(int num, char from, char to, char help){
		if(num == 1)
			System.out.println(from + "->" + to);
		else{
			move(num-1, from, help, to);
			System.out.println(from + "->" + to);
			move(num-1, help, to, from);
		}
	}
}

八皇后

import java.util.ArrayList;
import java.util.List;
public class Try{
    public static void main(String[] args) {
        int n = 8;
        Solution s = new Solution();
        s.solveNQueens(n);
    }
}
class Solution {
    public void solveNQueens(int n) {
        int count = 0;
        int[] solve = new int[n];
        for(int i = 0; i<n; i++){
            solve[i] = -1;
        }
        List<int[]> solves = new ArrayList<>();
        findQ(n, 0, solve, solves);
            // 遍历 List
            for (int[] array : solves) {
                count++;
                System.out.print("solution: ");
                for (int num : array) {
                    System.out.print(num + " ");
                }
                System.out.println();
            }
        System.out.println(count); // 一共解法

    }

    public void findQ(int n, int row, int[] solve, List<int[]> solves){ // n:一共的行数(8); row:当前的行数(0-7); solve
        for(int i = 0; i<n; i++){
            if(row == n){ // 最后一行已经下好Q了
                solves.add(solve.clone()); // *
                return ;
            }else{
                solve[row] = i; // 假设下在第row+1行的i+1个位置
                if(isValid(solve, row))
                    findQ(n, row+1, solve, solves); // 继续找下一行
                solve[row] = -1; // 回溯
            }    
        }

    }

    public boolean isValid(int[] sol, int row){
        boolean flag1;
        boolean flag2;
        boolean flag3;

        for(int n = 0; n<row ; n++){
            for(int m = n+1; m<=row; m++){
                flag1 = sol[n] == sol[m]; // 在同一列
                flag2 = (n - sol[n]) == (m - sol[m]); // 在左上\右下
                flag3 = (n + sol[n]) == (m + sol[m]); // 在左下\右上
                if(flag1 || flag2 || flag3)
                    return false;
            }
        }
        return true;
    }    

}