递归回溯算法一文读懂详解图文_Java

一、递归算法的定义

程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

递归，就是在运行的过程中调用自己。
构成递归需具备的条件：

子问题须与原始问题为同样的事，且更为简单；
不能无限制地调用本身，须有个出口，化简为非递归状况处理。

递归的套路：

确定递归函数的参数和返回值
确定终止条件
确定单层函数的逻辑

二叉树的遍历就是一个典型的递归算法：

代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        if(root==null) return 0;
        int left = countNodes(root.left);
        int right = countNodes(root.right);
        return left+right+1;
    }
}

程序自身调用自身是递归的首要特征，递归的本质是穷举法，会遍历所有可能发生的情况，然后选择符合的输出，所以递归的时间效率不理想，所以对于时间要求较严格的情况下，递归可能会超时。

二、回溯算法

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

回溯是递归的副产品，只要有递归就会有回溯。

回溯算法和递归是类似的，只是在递归最后多了一步回退操作，经典的回溯问题：

八皇后问题：

n后问题要求在一个n*n格的棋盘上放置n个皇后，使得它们彼此不受攻击。按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一条斜线上的其他任何棋子。

分析：利用回溯算法，进行穷举每一种情况，不符合摆放规则的进行回溯。

代码：

public class Main{
	static int max = 8;
	static int count = 0;
	static int[] res = new int[max];
	
	public static void main(String[] args) {
		Main queen = new Main();
		queen.set(0);
		System.out.println(count);
	}
	
	//判断当前行是否符合
	public boolean judge(int n){
		for(int i=0;i<n;i++)
			//判断当前行的行(i<n说明行不可能会一样)、列(res[i]==res[n]判断列)、上斜/下斜(Math.abs(i-n)==Math.abs(res[i]-res[n])判断上下斜)是否符合
			if(res[i]==res[n] || Math.abs(i-n)==Math.abs(res[i]-res[n]))
				return false;
		//循环遍历一遍行、列、上下斜都符合，则返回true
		return true;
	}
	
	//设置当前的行
	public void set(int n){
		if(n==max)//如果符合n==8了，证明前面的0-7个位置判断是一定正确的，所以可以输出当前结果
		{
			out();
			return;
		}
		for(int i=0;i<max;i++)
		{
			res[n] = i;//逐个试每个位置能否放置
			if(judge(n)){//如果当前位置可以放置，则set（n+1）放置下一行，如果不可以继续试当前行的下一个位置，当相当于回溯到当前位置，没有进行下一步递归
				set(n+1);
			}
		}
	}
	//输出
	public void out(){
		count++;//每输出一次就增加一次
		System.out.println(Arrays.toString(res));
	}
}