递归与回溯 – 在Python中优雅地解决复杂问题

[QPY课程团队]

🚀 引言

递归和回溯是两种核心技术，它们解锁了强大的问题解决模式——尤其是在处理树、排列、组合、谜题和路径寻找时。

在这篇文章中，我们将探讨：

✅ 递归是什么以及它是如何工作的

✅ 可视化调用栈

✅ 用模板解释回溯

✅ 现实世界中的问题，如排列、组合和数独求解器

✅ 避免常见陷阱的技巧，如无限递归和栈溢出

 

 1️⃣ 什么是递归？

递归是指一个函数调用自身以解决一个更小的子问题。

🔹 经典示例：阶乘

def factorial(n):
    if n == 0:
        return 1

return n * factorial(n - 1)

🧠 思考分为三个部分：

1. 基本情况 – 何时停止

2. 递归情况 – 问题如何缩小

3. 栈 – Python 使用调用栈来跟踪函数调用

 

🧠 可视化调用栈

factorial(3)
=> 3 * factorial(2)
       => 2 * factorial(1)
              => 1 * factorial(0)
                     => 1

每次递归调用都会暂停，直到下一个调用返回。这种后进先出（LIFO）的行为类似于栈。

 

 2️⃣ 什么是回溯法？

回溯法是一种通过探索所有可能性并在需要时撤销决策来解决问题的策略。

它在以下情况下使用：

1. 生成排列或组合时

2. 解决约束问题（如数独）

3. 在网格或树中探索路径

 

 3️⃣ 回溯模板

def backtrack(path, choices):
    if goal_reached(path):
        results.append(path)
        return

    for choice in choices:
        if is_valid(choice):

make_choice(choice)
backtrack(path + [choice], updated_choices)
undo_choice(choice)

这是所有回溯解决方案的核心思想。

 4️⃣ 示例：生成所有排列

def permute(nums):
    results = []

    def backtrack(path, remaining):
        if not remaining:
            results.append(path)
            return

        for i in range(len(remaining)):

backtrack(path + [remaining[i]], remaining[:i] + remaining[i+1:])

backtrack([], nums)
return results

print(permute([1, 2, 3]))

 

5️⃣ 示例：N-皇后问题

 

在一个 N×N 的棋盘上放置 N 个皇后，使得任意两个皇后都不互相威胁。

 

def solve_n_queens(n):
    solutions = []

    def backtrack(row, cols, diag1, diag2, board):
        if row == n:

solutions.append(["".join(r) for r in board])
            return

        for col in range(n):
            if col in cols or (row + col) in diag1 or (row - col) in diag2:
                continue

board[row][col] = 'Q'
backtrack(row + 1, cols | {col}, diag1 | {row + col}, diag2 | {row - col}, board)
board[row][col] = '.'

board = [["."] * n for _ in range(n)]
    backtrack(0, set(), set(), set(), board)
    return solutions

6️⃣ 示例：组合

def combine(n, k):
    results = []

    def backtrack(start, path):
        if len(path) == k:
            results.append(path[:])
            return
        for i in range(start, n + 1):

path.append(i)
backtrack(i + 1, path)
path.pop()

backtrack(1, [])
return results

✅ 回溯通常涉及修改状态、递归，然后撤销该更改。

 

 7️⃣ 示例：解决数独棋盘

def solve_sudoku(board):
    def is_valid(r, c, val):
        for i in range(9):

if board[r][i] == val or board[i][c] == val or board[r//3*3 + i//3][c//3*3 + i%3] == val:
                return False
        return True

    def backtrack():

for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    for num in map(str, range(1, 10)):
                        if is_valid(r, c, num):

在这段代码中，我们使用了嵌套的循环来遍历一个 9×9 的棋盘。外层循环遍历行（`r`），内层循环遍历列（`c`）。当棋盘上某个位置的值为 `.` 时，我们会尝试在该位置放置数字 1 到 9。通过调用 `is_valid` 函数，我们可以检查在该位置放置特定数字是否有效。

board[r][c] = num
                            if backtrack():
                                return True
                            board[r][c] = "."
                    return False
        return True

    backtrack()

📌 一个带有约束剪枝的递归状态搜索的优秀示例。

 

8️⃣ 提示与最佳实践

✅ 始终定义一个基本情况

✅ 使用集合或访问数组来避免循环

✅ 在传递列表时使用 path[:] 或 path.copy()

✅ 尝试编写递归 + 回溯模板一次并重用

⚠️ 注意 Python 的递归限制 (sys.setrecursionlimit())

 

🧪 经典练习问题

问题	类型
斐波那契数列	递归 + 记忆化
排列问题	回溯
N 皇后问题	回溯 + 剪枝
数独求解器	回溯
网格中的单词搜索	深度优先搜索 + 回溯
电话号码的字母组合	回溯
子集/组合问题	回溯

 

✅ 摘要

✔️ 递归是指在函数内部调用自身，以将问题分解为子问题
✔️ 回溯法是探索、承诺和撤销选择的过程
✔️ 对于涉及所有可能组合/排列的问题，使用回溯法
✔️ Python 使递归变得直观，语法简单——只需注意栈深度
✔️ 从状态、选择和约束的角度进行思考

💬 有一个让你困扰的递归问题吗？或者有一个想分享的回溯技巧？在评论中告诉我们，让我们一起解决它吧！🧠🐍

[作者]

帖子