Java数据结构与算法实现递归与回溯

Java数据结构与算法实现递归与回溯攻略

什么是递归与回溯

递归是指函数调用自己的过程。在递归过程中，一般需要包含两个部分：递归调用过程和递归出口。递归应用广泛，例如在计算机科学中，递归可应用于算法设计中的分治思想和动态规划。

回溯是指在解决问题时，尝试每一种可能的分步方法，当尝试后发现该方法不行时，取消当前尝试的分步方法，回到上一步，再使用其他可能的分步方法继续尝试寻找问题的解决方法。回溯算法通常用于解决组合问题、排列问题、选择问题等。

使用递归实现阶乘

下面是使用递归实现阶乘的Java示例代码：

public int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial(n-1);
}

该代码中，首先判断传入的参数是否为0，如果为0，则返回1，否则继续递归调用factorial函数，并将n-1作为参数传入，最后将当前的n和调用factorial(n-1)得到的值相乘并返回。

使用回溯算法实现八皇后问题

八皇后问题是一个经典的问题，即在一个8x8的棋盘上放置8个皇后，使得每个皇后不在同一行、同一列和同一对角线上。下面是使用回溯算法实现八皇后问题的Java示例代码：

public List<List<Integer>> solveNQueens(int n) {
    List<List<Integer>> res = new ArrayList<>();
    boolean[] col = new boolean[n];
    boolean[] diag1 = new boolean[2*n - 1];
    boolean[] diag2 = new boolean[2*n - 1];
    helper(res, new ArrayList<>(), col, diag1, diag2, n, 0);
    return res;
}

private void helper(List<List<Integer>> res, List<Integer> cur, boolean[] col, boolean[] diag1, boolean[] diag2, int n, int row) {
    if (row == n) {
        res.add(new ArrayList<>(cur));
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!col[i] && !diag1[row+i] && !diag2[n-1+row-i]) {
            col[i] = true;
            diag1[row+i] = true;
            diag2[n-1+row-i] = true;
            cur.add(i);
            helper(res, cur, col, diag1, diag2, n, row+1);
            col[i] = false;
            diag1[row+i] = false;
            diag2[n-1+row-i] = false;
            cur.remove(cur.size()-1);
        }
    }
}

在该代码中，我们使用三个数组分别记录了每一行、每一列和每一条对角线上是否已经存在皇后。在每一行中，我们枚举每一个位置，如果该位置在当前列、对角线上都没有其他皇后，则将该位置标记为已占用，并继续递归遍历下一行。如果当前所有行都已经遍历完成，则将结果保存到输出列表中，并返回。

以上就是Java数据结构与算法实现递归与回溯的攻略，递归和回溯都是算法的重要思想，掌握它们有助于我们在算法设计中更加灵活地处理问题。