前言：如何思考遞歸問題

當你看到遞歸時，如果腦子里想著循環，一層層向下調用，一層層回溯，總想著計算機的每一步是怎么做的，這樣就會陷入學習遞歸的思維誤區；

正確的做法是什么呢？（屏蔽遞歸細節）
假設A問題，可以細分為BCD這三個小問題，那么我們就應該考慮BCD這三者怎么解決，然后能解決之后再考慮BCD和A的關系；

例：如果要解決我坐在電影院第幾排，那么就可以分成規模更小的問題，然后問題就成為了很多個前一排在哪一排的問題；求解自己在哪一排的思路和前面一排的人求解的思路一樣

---

一、對于遞歸問題代碼怎么編寫

1.寫出遞推公式(找到如何將大問題分解為小問題的規律，基于此寫出遞推公式)
2.找到終止條件
（注：如果沒有終止條件，遞歸就成為了死龜了😁）

二、迷宮問題

思路：
1.使用一個二維數組代表迷宮，數字1代表墻，2代碼通路，3代表死路 ，0代表還未走過
2.走的策略：下-右-上-左
3.如果走到某個點不通，就將該點標記為3；然后返回false，棧頂就會彈出一個方法，所以會回退到上一步

代碼

package com.company;/*** @author:抱著魚睡覺的喵喵* @date:2021/2/21* @description:*/ public class Maze {public static void main(String[] args) {int[][] maze = new int[9][8];for (int i = 0; i < 8; i++) { //數組上下邊界設為墻maze[0][i] = 1;maze[8][i] = 1;}for (int j = 0; j < 9; j++) { //數組左右邊界設為墻maze[j][0] = 1;maze[j][7] = 1;}maze[2][2] = 1; //額外為迷宮加入兩個墻作為障礙maze[2][1] = 1;for (int i = 0; i < 9; i++) {for (int j = 0; j<8; j++) {System.out.printf("%d\t",maze[i][j]);}System.out.println();}getPath(maze,1,1);System.out.println("路徑如下：");for (int i = 0; i < 9; i++) {for (int j = 0; j<8; j++) {System.out.printf("%d\t",maze[i][j]);}System.out.println();}}/*** 迷宮的行走策略：下-右-上-左* @param map* @param x* @param y* @return*/public static boolean getPath(int[][] map, int x, int y) {if (map[7][6] == 2) {return true;} else {if (map[x][y] == 0) {map[x][y] = 2;if (getPath(map, x+1, y)) {return true;} else if (getPath(map, x, y+1)) {return true;} else if (getPath(map, x-1, y)) {return true;} else if (getPath(map, x, y-1)) {return true;} else {map[x][y] = 3;return false;}} else {return false;}}} }

愿你孤獨的努力都有回報，愿你前行的路上有人陪伴~

一起加油哈😉

總結

以上是生活随笔為你收集整理的迷宫问题让你深度理解递归(回溯）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。