递归回溯法叫称为试探法，按选优条件向前搜索，当搜索到某一步，发现原先选择并不优或达不到目标时，就退回一步重新选择。这里有一个非常经典的例子叫“骑士巡逻问题”，这个例子应该更容易帮助你理解什么是递归回溯法。
所谓“骑士巡逻问题”是指按照国际象棋中骑士（Knight，走法类似于中国象棋中的“马”）的走法，一个骑士从棋盘的某一个格子出发，走遍整个棋盘的每一个方格，而且每个格子只能够经过一次，找出可能的线路和走法。如果骑士从某个格子出发，走完所有格子后最终能回到这个出发的格子，称这种巡逻方式为“封闭式巡逻”，否则称为“开放式巡逻”。国际象棋的棋盘是 \small{8 \times 8} 的方格，一共有26,534,728,821,064种封闭式巡逻，有19,591,828,170,979,904种开放式巡逻。对于下面的缩小为 \small{5 \times 5} 的棋盘，下面的动图给出了骑士的一种巡逻方案。
这里顺便吐槽一下，知乎回答问题时插入图片居然不支持gif，这里只能给一个gif图片的链接，图片来自于维基百科，可能需要科学一下才能看到。
下面用 Python 给出了“骑士巡逻问题”的代码，用其他语言书写本质上也没有什么差别。
SIZE = 5
def show_board(board, totals=[0]):
"""显示棋盘和第几种走法"""
totals[0] += 1
print(f'第{totals[0]}种走法: ')
for row in board:
for col in row:
print(str(col).center(4), end='')
print()
def patrol(board, row=0, col=0, step=1):
"""用递归回溯的方式搜索所有的巡逻方式
:param board: 棋盘（用嵌套列表表示）
:param row: 骑士准备巡逻的位置对应的行
:param col: 骑士准备巡逻的位置对应的列
:param step: 序号（按巡逻的顺序依次标记）
"""
if row >= 0 and row < SIZE and col >= 0 and col < SIZE and board[row][col] == 0:
# 如果row和col都在棋盘范围以内且对应的格子没有巡逻过就标记它
board[row][col] = step
if step == SIZE * SIZE:
# 所有的格子都被标记（一次巡逻完成）就输出棋盘
show_board(board)
# 向下一个格子继续巡逻（国际象棋的骑士可以往八个方向进行）
# 巡逻方向不同row和col的变化就不同，但step都是统一加1
patrol(board, row - 2, col - 1, step + 1)
patrol(board, row - 1, col - 2, step + 1)
patrol(board, row + 1, col - 2, step + 1)
patrol(board, row + 2, col - 1, step + 1)
patrol(board, row + 2, col + 1, step + 1)
patrol(board, row + 1, col + 2, step + 1)
patrol(board, row - 1, col + 2, step + 1)
patrol(board, row - 2, col + 1, step + 1)
# 八个方向都行不通或者所有格子已经巡逻完毕就回到上一步（回溯）
# 回溯时要记得清除之前标记的step，标记为0相当于格子未被巡逻
board[row][col] = 0
def main():
# 初始化棋盘（每个格子都标为0表示没有巡逻过）
board = [[0] * SIZE for _ in range(SIZE)]
patrol(board)
if __name__ == '__main__':
main()看看上面的代码是否能够帮助你更好的理解递归回溯算法。有一个小建议，给你的代码增加一些断点，然后用调试模式运行代码，通过单步执行并观察你的函数调用栈以及相关变量的值，就能更好的理解整个代码是如何运转起来的。
最后，还是给你一个C++版本的代码，我不确定你写的C还是C++，我也很久没有写过C++的代码了，下面的代码倒是可以运转起来的，但是不知道写得是否精准，你自己甄别吧。
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
const int SIZE = 5;
void show_board(const vector<vector<int> >& board) {
static int total = 0;
cout << "第" << ++total << "种走法: " << endl;
for (const auto& row : board) {
for (const auto& col : row) {
cout << setw(4) << col;
}
cout << endl;
}
}
void patrol(vector<vector<int> >& board, int row = 0, int col = 0, int step = 1) {
if (row >= 0 && row < SIZE && col >= 0 && col < SIZE && board[row][col] == 0) {
board[row][col] = step;
if (step == SIZE * SIZE) {
show_board(board);
}
patrol(board, row - 2, col - 1, step + 1);
patrol(board, row - 1, col - 2, step + 1);
patrol(board, row + 1, col - 2, step + 1);
patrol(board, row + 2, col - 1, step + 1);
patrol(board, row + 2, col + 1, step + 1);
patrol(board, row + 1, col + 2, step + 1);
patrol(board, row - 1, col + 2, step + 1);
patrol(board, row - 2, col + 1, step + 1);
board[row][col] = 0;
}
}
int main() {
vector<vector<int> > board(SIZE, vector<int>(SIZE, 0));
patrol(board);
return 0;
}
写到这里就顺便吐槽一下C++，用嵌套容器时两个大于号放一起会跟 >> 运算符冲突，原来的解决方案是在两个大于号中间添加一个空格，但这样会让整个代码看起来丑陋无比，就像我上面代码中写的那样，真心不喜欢！我记得从什么时候开始，C++是不是编译的时候加个参数 -std 就可以解决这个问题，具体是怎么操作的我也没啥印象了，如果有大佬知道这个问题的解决方案和背后的道理，也请大家不吝赐，感谢！
编辑于 2024-03-24 11:07・IP 属地四川