又是一次递归的总结

2024-06-25

11k 词

递归

递归意味着“根据自身来定义问题”。这在编写算法方面可能是一个非常强大的工具。递归直接来自数学，其中有许多用自身编写的表达式的例子。例如，斐波那契数列定义为：F（i） = F（i-1） + F（i-2）。

用递归打印数字三角形

我们需要打印以下的数字三角形：

1
22
333
4444
55555
......

定义函数f，唯一参数int n为行数，返回值为void。函数f的功能是打印一个数字三角形，其中第i行打印i个数字i。

public static void f(int n) {
    if (n == 0) return;
    f(n - 1);
    for (int i = 0; i < n; i++) {
        System.out.print(n);
    }
    System.out.println();
}

先想递归的终止条件，当n等于0时，不需要打印任何东西，直接返回。然后想如果我要打印n行的数字三角形，我可以先打印n-1行的数字三角形，然后再打印第n行。这样就可以用递归来解决这个问题。

用递归反转打印数组

public static void reverse(int[] a, int i) {
    if (i == a.length) {
        return;
    }
    reverse(a, i + 1);
    System.out.print(a[i] + "");
}

递归终止条件：当索引为数组长度时直接结束掉。

打个比方，我们要反转打印[1,2,3,4,5]，那么就先可以先反转打印[2,3,4,5]，也就是调用函数reverse(a,i+1)然后再打印1，于是问题就被解决了。

公交车乘客问题

现在有W个手持五毛钱的人和Y个手持1块钱的人，公交车上的票价是5毛钱，然后车上没有零钱，但是可以用收来的五毛钱来找零，问有多少种上车的方式。

第一种做法

我最先想的是，可以定义三个参数，分别是int W，int Y，int cnt，分别表示手持五毛钱的人数，手持1块钱的人数，已经上了车的五毛钱的人数。然后我们可以定义一个函数f，当W=0且Y=0时，那么说明都上了车了，是一种合法的方案，我们把ans++，当W>0时，说明还有手持五毛钱的人没有上车，那么我们可以让他上车，然后递归调用f(W-1,Y,cnt+1)，当Y>0且cnt>0时，说明还有手持1块钱的人没有上车且可以给他找零，那么我们可以让他上车，然后递归调用f(W,Y-1,cnt-1)。

public static int ans;
    
public static void g(int W, int Y, int cnt) {
    if (W == 0 && Y == 0) {
        ans++;
        return;
    }
    if (W > 0) {
        path.append("5");
        g(W - 1, Y, cnt + 1);
        path.deleteCharAt(path.length() - 1);
    }
    if (Y > 0 && cnt > 0) {
        path.append("1");
        g(W, Y - 1, cnt - 1);
        path.deleteCharAt(path.length() - 1);
    }
}

第二种做法

先上代码：

public static int g2(int W, int Y) {
    if (W < Y) return 0;
    if (Y == 0) return 1;
    return g2(W - 1, Y) + g2(W, Y - 1);
}

先看递归边界：

当W<Y时，说明手持五毛钱的人数小于手持1块钱的人数，那么无法找零，直接返回0。
当Y=0时，说明手持1块钱的人数为0，那么只有一种方案，就是所有拿五毛钱的都上车。

最后只需返回上一个五毛钱的人数和上一个1块钱的人数的方案数之和即可。

苹果和盘子

现在又有M个苹果，N个盘子，问你将这M个苹果放在这N个盘子里，有多少种方案（不考虑排列）。

例如：M=6,N=3，那么其方案如下：

观察一下不难发现，有的方案有空盘子，有的方案没有空盘子，那么我们可以定义两个函数一个h1,h2，h1表示有空盘子的方案数，h2表示没有空盘子的方案数，它们的输入参数都int M, int N，表示有M个苹果，N个盘子。

考虑函数`h1`

当N=1也就是盘子数为一个的时候，将M个盘子都放入这个盘子里，只有一种方案，那就是1。
当M=1也就是苹果数为一个的时候，只有一个苹果，那么只有一种方案，那就是1。
当M<N时，也就是苹果数小于盘子数的时候，一定会有空盘子，也就是实际只有M个盘子放入了苹果，原问题等价于h1(M,M)。
当M>=N时，也就是苹果数大于等于盘子数的时候，我们可以把这M个苹果放在i in 1..N个盘子里，那么转化为循环调用h2(M,i)累加求和，h2的定义是没有空盘子的方案数。

public static int h1(int M, int N) {
    if (N == 1) return 1;
    if (M == 1) return 1;
    if (M < N) return h1(M, M);
    int sum = 0;
    for (int i = 1; i <= N; i++) {
        sum += h2(M, i);
    }
    return sum;
}

考虑函数`h2`

当M<N时，也就是苹果数少于盘子数，那么一定会有空盘子，不满足定义，返回0
当M=N时，也就是苹果数等于盘子数，那么只有一种方案，那就是1
当N==1时，也就是只有一个盘子时，那么只有一种方案，那就是1，注意这里这个判断条件一定要在判断M<N之后，否则当M=0时，会返回1，这是不合法的。
当M>N时，也就是苹果数大于盘子数，那么此时的结果就等价于h1(M-N,N)，为什么呢，我们可以先将N个盘子平均放入N个苹果，那么剩下的M-N个苹果可以放在这N个盘子里，也就是h1(M-N,N)，因为是有空盘子的方案数。

public static int h2(int M, int N) {
    if (M < N) return 0;
    if (M == N) return 1;
    if (N == 1) return 1;
    return h1(M - N, N);
}

N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。

先定义函数nhh，传入参数int n，返回值为void，内部定义一个n*n的二维数组a，然后调用函数process，传入棋盘a，棋盘大小n，当前行数0。

public static void nhh(int n) {
    int[][] a = new int[n][n];
    process(a, n, 0);
}

直接放出暴力递归代码：

 public static void process(int[][] a, int n, int i) {
    if (i == n) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                System.out.print(a[j][k] == 1 ? "Q " : ". ");
            }
            System.out.println();
        }
        System.out.println();
        return;
    }
    for (int j = 0; j < n; j++) {
        if (check(a, i, j, n)) {
            a[i][j] = 1;
            process(a, n, i + 1);
            a[i][j] = 0;
        }
    }
}

其中check函数的功能是判断当前位置是否可以放置皇后，传入参数为int[][] a，int i，int j，int n，分别表示棋盘，行数，列数，棋盘大小。

public static boolean check(int[][] a, int i, int j, int n) {
    for (int k = 0; k < i; k++) {
        if (a[k][j] == 1
                || (j - i + k >= 0 && a[k][j - i + k] == 1)
                || (i + j - k < n && a[k][i + j - k] == 1)) return false;
    }
    return true;
}

检查三个半方向的是否有皇后，如果有就返回false，否则返回true。

检查同一列是否有皇后，也就是遍历行号，取列号为j的位置是否有皇后。
检查左斜线上方是否有皇后，也就是遍历行号，取列号为j-i+k（由j-i=x-k得到x=j-i+k，因为主对角线行列标差相等）的位置是否有皇后。
检查右斜线上方是否有皇后，也就是遍历行号，取列号为i+j-k（由i+j=x+k得到x=i+j-k，因为次对角线行列标和相等）的位置是否有皇后。

调用nhh(4)，输出如下：

. Q . . 
. . . Q 
Q . . . 
. . Q . 

. . Q . 
Q . . . 
. . . Q 
. Q . .

继续进一步思考，因为每行只能放一个皇后，所以我们可以用一个一维数组int[] a来表示皇后的位置，a[i]表示第i行的皇后位置，如此就可以省去二维数组的空间，降低了空间复杂度至O(n)。

一维数组写法：

public class N皇后1 {
    public static void main(String[] args) {
        nhh(4);
    }

    public static void nhh(int n) {
        int[] a = new int[n];
        process(a, n, 0);
    }

    public static void process(int[] a, int n, int i) {
        if (i == n) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    System.out.print(a[j] == k ? "Q " : ". ");
                }
                System.out.println();
            }
            System.out.println();
            return;
        }
        for (int j = 0; j < n; j++) {
            if (check(a, i, j, n)) {
                a[i] = j;
                process(a, n, i + 1);
                // a[i] = 0;
            }
        }
    }

    public static boolean check(int[] a, int i, int j, int n) {
        for (int k = 0; k < i; k++) {
            if (a[k] == j
                    || a[k] == (j - i + k)
                    || a[k] == (i + j - k)) return false;
        }
        return true;
    }
}

接着我们改成用栈的方式来实现，这样就不需要递归了，因为要将原先的递归信息放到栈里面，所以我们需要先定义一个类来表示递归信息，这里我们定义一个State类，有三个属性，分别是int[] a，int row，int col，分别表示皇后位置数组，当前行数，当前列数。

class State {
    int[] a;
    int row;
    int col;

    State(int[] a, int row, int col) {
        this.a = a;
        this.row = row;
        this.col = col;
    }
}

然后用栈来模拟递归：

package 实践学期.第二节课递归;

import java.util.Stack;

public class N皇后2 {
    public static void main(String[] args) {
        nhh(4);
    }

    public static void nhh(int n) {
        int[] a = new int[n];
        Stack<State> stack = new Stack<>();
        stack.push(new State(a, 0, 0));

        while (!stack.isEmpty()) {
            State cur = stack.pop();
            a = cur.a;
            int row = cur.row;
            int col = cur.col;

            if (row == n) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < n; k++) {
                        System.out.print(a[j] == k ? "Q " : ". ");
                    }
                    System.out.println();
                }
                System.out.println();
                continue;
            }

            if (col < n) {
                if (check(a, row, col, n)) {
                    a[row] = col;
                    stack.push(new State(a.clone(), row + 1, 0));
                }
                stack.push(new State(a.clone(), row, col + 1));
            }
        }
    }

    public static boolean check(int[] a, int i, int j, int n) {
        for (int k = 0; k < i; k++) {
            if (a[k] == j || a[k] == (j - i + k) || a[k] == (i + j - k)) {
                return false;
            }
        }
        return true;
    }
}

class State {
    int[] a;
    int row;
    int col;

    State(int[] a, int row, int col) {
        this.a = a;
        this.row = row;
        this.col = col;
    }
}

高IQ过河

这个问题是这样的：有八个人，需要让所有人过河，其中有一个警察、一个小偷、一个爸爸、两个儿子、一个妈妈、两个女儿，然后有一个小船最多只能坐两个人，只有大人才能开船（也就是只有警察、爸爸、妈妈可以开），但是要遵循以下规则：

当这些人在同一岸时：

小偷不能和除警察的六个人在一起
妈妈不能在没有爸爸的情况下和儿子在一起
爸爸不能在没有妈妈的情况下和女儿在一起

现在，请问如何过河？

我们先可以用数字定义这个八个人，这里我们直接使用二进制的每一位来表示，这样就保证了他们组合时的唯一性。

警察：128，小偷：64，父亲：32，母亲：16，两个女儿：8，4，两个儿子：2，1

判断`x`是否包含`y`的所有位

我们写一个方法f1用来判断x是否包含y的所有位，例如：18（10010）包含2（00010），这里18表示了母亲和大儿子的一种组合，将x与y做与运算，如果结果等于y，那么就说明x包含了y的所有位。

public static boolean f1(int x, int y) {
    return (x & y) == y;
}

判断`x`是否合理

然后我们再写一个函数f2判断当前的是否合理，如何实现呢？我们可以通过刚才写的f1函数进行判断：

如果当前x内不包含警察并且大于64也就是包含小偷，那么不合理，返回false
如果当前x内不包含父亲但是包含母亲和儿子，那么也不合理，返回false
如果当前x内不包含母亲但是包含父亲和女儿，那么也不合理，返回false
否则满足条件，，返回true

编写搜索代码

考虑函数定义，用一个参数x表示现在没有过河的人的总和，用一个一维数组res表示每一步操作的步骤，再用一个数字step来表示当前是第几步。

初始状态，所有的人都在一边没有过河，总和为255，并且当前是第0步。

考虑到一共有512种状态((0-255)*2)，为什么乘2，因为要船的位置在这边和那边分别是两种不同的状态，我们可以通过step%2的操作判断船在那一边，如果为0，说明不在对岸，如果为1说明在对岸，然后考虑上船的不同组合方式

警察和小偷
警察和父亲
警察和母亲
警察和大女儿
警察和二女儿
警察和大儿子
警察和二儿子
母亲和大女儿
母亲和二女儿
父亲和大儿子
父亲和二儿子
父亲和母亲
父亲
母亲
警察

共计15种，那么我们创建长度为15的数组

int[] arr = {警察 | 小偷, 警察 | 父亲, 警察 | 儿子1, 警察 | 儿子2, 警察 | 母亲, 警察 | 女儿1, 警察 | 女儿2,
                父亲 | 母亲, 父亲 | 儿子1, 父亲 | 儿子2, 母亲 | 女儿1, 母亲 | 女儿2, 警察, 父亲, 母亲};

然后在递归函数内遍历这15种情况一一尝试：

如果step%2为0，也就是船不在对岸的情况下，以下情况不合理：
- x不包含当前选择的arr[i]，也就是我要选的组合在这些人里没有
- f2(x-arr[i])返回false，不在河对岸位置的人减去走的人不合理
- f2(255-x+arr[i])返回false，河对岸位置的人加上来的人不合理
反之如果step%2为1，也就是船在对岸的情况下，以下情况不合理：
- 255-x包含了当前选择的arr[i]，同样也是我要选的组合在这些人里没有
- f2(255-x-arr[i])返回false，河对岸位置的人减去走的人不合理
- f2(x+arr[i])返回false，不在河对岸的人加上来的人不合理

如果条件合理，那么我们记录res[step] = arr[i]，并且继续向下递归。

public static void f(int x, int[] res, int step) {
    if (isFinished) return;
    if (step >= 20) return;
    if (x == 0) {
        for (int i = 0; i < step; i++) {
            System.out.print(res[i] + " ");
        }
        System.out.println();
        isFinished = true;
        return;
    }

    int[] arr = {警察 | 小偷, 警察 | 父亲, 警察 | 儿子1, 警察 | 儿子2, 警察 | 母亲, 警察 | 女儿1, 警察 | 女儿2,
            父亲 | 母亲, 父亲 | 儿子1, 父亲 | 儿子2, 母亲 | 女儿1, 母亲 | 女儿2, 警察, 父亲, 母亲};
    for (int i = 0; i < arr.length; i++) {
        if (step % 2 == 0) {
            if (!f1(x, arr[i])) continue;
            if (!f2(x - arr[i])) continue;
            if (!f2(255 - x + arr[i])) continue;
            if (flag[x - arr[i]]) continue;
            res[step] = arr[i];
            flag[x - arr[i]] = true;
            f(x - arr[i], res, step + 1);
        } else {
            if (!f1(255 - x, arr[i])) continue;
            if (!f2(x + arr[i])) continue;
            if (!f2(255 - x - arr[i])) continue;
            if (flag[x + arr[i] + 256]) continue;
            res[step] = arr[i];
            flag[x + arr[i] + 256] = true;
            f(x + arr[i], res, step + 1);
        }
    }
}

完整代码

public class 高IQ过河 {

    // 用int表示八个人
    // 警察：128，小偷：64，父亲：32，母亲：16，两个女儿：8，4，两个儿子：2，1
    public static int 警察 = 128, 小偷 = 64, 父亲 = 32, 母亲 = 16, 女儿1 = 8, 女儿2 = 4, 儿子1 = 2, 儿子2 = 1;

    public static boolean[] flag = new boolean[512];

    // 判断x是否包含y的所有位
    public static boolean f1(int x, int y) {
        return (x & y) == y;
    }

    // 判断x是否合理
    public static boolean f2(int x) {
        if (!f1(x, 警察) && x > 64) return false;
        if (!f1(x, 父亲) && f1(x, 母亲) && (f1(x, 儿子1) || f1(x, 儿子2))) return false;
        if (!f1(x, 母亲) && f1(x, 父亲) && (f1(x, 女儿1) || f1(x, 女儿2))) return false;
        return true;
    }

    public static void f(int x, int[] res, int step) {
        if (isFinished) return;
        if (step >= 20) return;
        if (x == 0) {
            for (int i = 0; i < step; i++) {
                System.out.print(res[i] + " ");
            }
            System.out.println();
            isFinished = true;
            return;
        }

        int[] arr = {警察 | 小偷, 警察 | 父亲, 警察 | 儿子1, 警察 | 儿子2, 警察 | 母亲, 警察 | 女儿1, 警察 | 女儿2,
                父亲 | 母亲, 父亲 | 儿子1, 父亲 | 儿子2, 母亲 | 女儿1, 母亲 | 女儿2, 警察, 父亲, 母亲};
        for (int i = 0; i < arr.length; i++) {
            if (step % 2 == 0) {
                if (!f1(x, arr[i])) continue;
                if (!f2(x - arr[i])) continue;
                if (!f2(255 - x + arr[i])) continue;
                if (flag[x - arr[i]]) continue;
                res[step] = arr[i];
                flag[x - arr[i]] = true;
                f(x - arr[i], res, step + 1);
            } else {
                if (!f1(255 - x, arr[i])) continue;
                if (!f2(x + arr[i])) continue;
                if (!f2(255 - x - arr[i])) continue;
                if (flag[x + arr[i] + 256]) continue;
                res[step] = arr[i];
                flag[x + arr[i] + 256] = true;
                f(x + arr[i], res, step + 1);
            }
        }
    }

    public static boolean isFinished = false;

    public static void main(String[] args) {
        int x = 255;
        int[] res = new int[20];
        f(x, res, 0);
    }
}

组合数

public static void c1(int m, int n, int k, int M, boolean[] str) {
    if (m < n) return;
    if (n == 0) {
        for (int j = 0; j < M; j++)
            System.out.print(str[j] ? 1 : 0);
        System.out.println();
        return;
    }
    for (int j = 0; j < m - n + 1; j++) {
        str[j + k] = true;
        c1(m - 1 - j, n - 1, k + 1 + j, M, str);
        str[j + k] = false;
    }
}

public static void c(int m, int n) {
    boolean[] str = new boolean[m];
    c1(m, n, 0, m, str);
}

调用c(5,3)，输出：

 public static void C1(int[] in, int[] out, int m, int n, int N) {
    if (m < n) return;
    if (n == 0) {
        for (int j = 0; j < N; ++j)
            System.out.print(out[j] + " ");
        System.out.println();
        return;
    }
    for (int j = 0; j < m - n + 1; j++) {
        out[N - n] = in[j];
        C1(Arrays.copyOfRange(in, j + 1, in.length), out, m - 1 - j, n - 1, N);
    }
}

调用C1(new int[]{1, 2, 3, 4, 5}, new int[3], 5, 3, 3);

输出：

方格分割

思路

6x6的方格，沿着格子的边线剪开成两部分。要求这两部分的形状完全相同。

试计算：包括这3种分法在内，一共有多少种不同的分割方法。注意：旋转对称的属于同一种分割法。

思路：我们从中间的点开始出发，可以上下左右四个方向进行移动，直到走到边界位置，将答案+1，但是“旋转对称的属于同一种分割法。”，所以我们最后把答案除4。

那么我们创建一个7x7的矩阵，初始化x坐标偏移量dx和y坐标偏移量dy。

public static int[][] matrix = new int[7][7];
    
public static int cnt = 0;

public static int[] dx = {0, 0, 1, -1};

public static int[] dy = {1, -1, 0, 0};

我们定义dfs搜索函数：参数为当前的行数i和列数j，来表示当前的位置，递归边界，就是当前的位置已经处于矩阵边界位置。

if (i == 0 || j == 0 || i == 6 || j == 6) {
    cnt++;
    return;
}

然后遍历dx和dy，进行下一步的移动，如果计算出下一步的坐标(x,y)，如果下一步没有走过，那么就走，并且标记当前位置走过和该位置对称于中间位置的位置走过，递归调用dfs(x,y)，在回溯时撤回，取消标记当前位置和该位置对称于中间位置的位置。

最后得到输出：

完整代码

public class 方格分割 {


    public static void main(String[] args) {
        matrix[3][3] = 1;
        dfs(3, 3);
        System.out.println(cnt / 4);
    }
    public static int[][] matrix = new int[7][7];

    public static int cnt = 0;

    public static int[] dx = {0, 0, 1, -1};

    public static int[] dy = {1, -1, 0, 0};

    public static void dfs(int i, int j) {
        if (i == 0 || j == 0 || i == 6 || j == 6) {
            cnt++;
            return;
        }

        for (int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if (matrix[x][y] != 1) {
                matrix[x][y] = 1;
                matrix[6-x][6-y] = 1;
                dfs(x, y);
                matrix[x][y] = 0;
                matrix[6-x][6-y] = 0;
            }
        }
    }
}

至此，递归的总结就结束了。

分类

标签

归档

最新文章

又是一次递归的总结

递归

用递归打印数字三角形

用递归反转打印数组

公交车乘客问题

第一种做法

第二种做法

苹果和盘子

考虑函数`h1`

考虑函数`h2`

N皇后

高IQ过河

判断`x`是否包含`y`的所有位

判断`x`是否合理

编写搜索代码

完整代码

组合数

方格分割

思路

完整代码

分类

标签

归档

最新文章

递归

用递归打印数字三角形

用递归反转打印数组

公交车乘客问题

第一种做法

第二种做法

苹果和盘子

考虑函数h1

考虑函数h2

N皇后

高IQ过河

判断x是否包含y的所有位

判断x是否合理

编写搜索代码

完整代码

组合数

方格分割

思路

完整代码

考虑函数`h1`

考虑函数`h2`

判断`x`是否包含`y`的所有位

判断`x`是否合理