什么是Python中的递归和回溯？

阅读更多：Python 教程

介绍

递归和回溯都是在编写算法时用到的常见技术。在Python语言中，它们有着很重要的作用。

递归指的是函数调用自身的过程，它可以帮助我们简化复杂的问题，将一个大问题分解成若干个小问题，从而降低程序的复杂度。

回溯指的是通过穷举的方式找出所有可能的解，并且在搜索过程中记录下来，最终返回其中最优的解。

在本篇文章中，我们将学习如何使用递归和回溯算法来解决常见的问题。

递归

下面我们将以计算斐波那契数列为例来介绍递归的应用。

斐波那契数列的定义如下：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

我们可以使用递归的方式来计算斐波那契数列：

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

print(fib(6))

这段代码的输出结果为 8，是斐波那契数列的第6个数。

使用递归来计算斐波那契数列的优点是代码实现简单，但是它也有一些缺点。最明显的缺点是递归算法的性能问题，这是由于递归算法在求解大规模问题时需要反复调用函数，从而导致函数重复执行多次。假设我们需要计算 F(50)，那么这个递归函数将会被调用超过 10^17 次，这将导致程序耗时严重。

为了解决这个问题，我们可以使用循环或者记忆化搜索来优化递归算法。

回溯

下面我们以一个经典的回溯问题 N 皇后问题为例，介绍回溯算法的应用。

N 皇后问题指的是在一个 N × N 的棋盘上摆放 N 个皇后，使得每个皇后都不在同一行、同一列或同一条对角线上。例如，当 N=4 时，一种可能的方案如下所示：

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

我们可以使用回溯算法来解决 N 皇后问题。首先，我们需要写一个函数来检查当前位置是否可以放置皇后，然后在棋盘上枚举每一行的位置，在符合要求的情况下尝试放置皇后，如果失败，则回溯到上一步，继续尝试其他位置。

下面是使用回溯算法解决 N 皇后问题的Python代码：

def solveNQueens(n):
    def dfs(queens, xy_dif, xy_sum):
        row = len(queens)
        if row == n:
            result.append(queens)
            return
        for col in range(n):
            # 检查当前位置是否可以放置皇后
            if col not in queens and row-col not in xy_dif and row+col not in xy_sum:
                dfs(queens+[col], xy_dif+[row-col], xy_sum+[row+col])

    result = []
    dfs([], [], [])
    return [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]

print(solveNQueens(4))

这段代码会返回所有符合要求的解，其中每个解保存的是一种方案，输出格式为二维列表。

虽然回溯算法的思想非常简单，但是它在求解NP难问题上具有非常重要的地位，如图论、排列组合等问题都可以使用回溯算法来解决。