递归和回溯

递归

我能想到的最简单的、具有实际用途的递归函数是阶乘函数。
阶乘是小于等于该数的整数与自身的乘积。
例如：4的阶乘! = 4*3*2*1 = 24

def factorial(n):
  if(n>1):
    return factorial(n-1) * n
  return 1

这个 Python 示例通过递归调用自身来获取给定值的阶乘。

输入值“n”在每次递归调用中都会减去 1，导致“n”变为 0，从而达到递归的完整深度，输出阶乘值。

我并不是说这是解决这个问题的最佳方法。 这可以通过更少的代码轻松解决，而无需递归。

这是另一个使用 Nilakantha 级数计算 pi 的递归示例。

def CalcPiDecimals(opr,preciciendept):
  if preciciendept < 1:
    return 0
  preciciendept -= 1
  return 4/(opr * (opr + 1) * (opr + 2)) - 4/((opr + 2) * (opr + 3)* (opr + 4)) + 
            CalcPiDecimals(opr + 4,preciciendept)

print(3 + CalcPiDecimals(2,500))

在这里，递归函数只计算该值的小数部分。 需要将 3 加到结果中。
此函数，以此深度，输出 3.141592653340542。

回溯

您可以使用回溯来探索不同的解决方案和选项，使递归更强大。

这个例子受到了 YouTube 频道 Computerfile 的视频的启发。

这是一个典型的数独，让我们来解决它。

import numpy as np

#Converted to numpy array
sudoku = np.array([[0, 0, 2, 0, 1, 5, 0, 7, 8],
                   [1, 8, 0, 0, 6, 3, 4, 0, 0],
                   [0, 0, 4, 0, 2, 0, 5, 6, 1],
                   [0, 9, 6, 0, 0, 7, 0, 3, 0],
                   [0, 1, 0, 3, 0, 6, 0, 0, 5],
                   [0, 0, 3, 2, 0, 4, 0, 9, 6],
                   [0, 3, 0, 0, 0, 0, 0, 0, 0],
                   [6, 4, 9, 8, 3, 0, 2, 0, 7],
                   [0, 0, 7, 0, 0, 0, 0, 1, 0]
                   ])

# test if a value on a specific place is possible with current data
def possible(sudoku,rov, col, val):
    if sudoku[rov][col] != 0:
        return False #Already filled
    if val in sudoku[rov]:
        return False #Value already in row
    for a in range(9):
        if sudoku[a][col] == val:
            return False #value already in column
    sqrov = int(int(rov) / 3) * 3
    sqcol = int(int(col) / 3) * 3
    for r in range(sqrov, sqrov + 3):
        for c in range(sqcol, sqcol + 3):
            if sudoku[r][c] == val:
                return False #value already in square
    return True  # Value possible

#solve a sudoku if possible, Fill out list
def solve_Sudoku(sudoku):
    for rov in range(0, 9):
        for col in range(0, 9):
            if sudoku[rov][col] == 0:
                for val in range(1, 10):
                    if possible(sudoku,rov, col, val):
                        sudoku[rov][col] = val
                        if solve_Sudoku(sudoku):
                            return True
                        sudoku[rov][col] = 0 #Backtrack
                return False #Solution failed, backtrack for next value
    return True

solve_Sudoku(sudoku)
print(sudoku)

在这个例子中，真正发生的事情都在“Solve”函数中。

“possible”函数只是检查任何值是否符合数独的神圣规则。

你知道的

• 只能使用 1 到 9 之间的值
• 每行只能出现一次值
• 每列只能出现一次值
• 将数独板分成九个方格时，每个方格中只能出现一次值

“solve”函数迭代遍历 sudoku 数组中的每一行和每一列，查找未解决的字段（包含 0）。 找到后，它会迭代可能的数值。 使用“Possible”函数尝试每个值，直到“possible”返回 True。

如果“Possible”函数返回 true，则该值保留在 sudoku 数组中，并递归调用“Solve”函数以迭代到下一个具有未解决值的行/列。 这在下面的绿色箭头中进行了说明。

这可能不是世界上最好的插图，但制作它帮助我更好地理解了整个事情，这是这篇文章的主要目的。

如果“possible”函数返回 False，则 sudoku 数组字段再次被标记为未解决，并且循环查找在该字段中要尝试的下一个值。 如果字段没有值可以满足数独规则，回溯就开始了。

插图中的红色箭头显示，来自 possible 函数的 False 结果导致 sudoku 数组中的值被擦除（回溯），并且循环继续到下一个值。 这种回溯可以向后进行多个步骤，直到“possible”函数再次开始返回 True。 然后递归向前移动，用绿色箭头表示。

当行和列循环到达末尾时，如果可能，数独将被解决，并且“solve”函数将一直返回 true，直到它到达入口点。 蓝色箭头。

在此处查看整个插图.

打印已解决的数独。

[[9 6 2 4 1 5 3 7 8]
 [1 8 5 7 6 3 4 2 9]
 [3 7 4 9 2 8 5 6 1]
 [4 9 6 1 5 7 8 3 2]
 [2 1 8 3 9 6 7 4 5]
 [7 5 3 2 8 4 1 9 6]
 [5 3 1 6 7 2 9 8 4]
 [6 4 9 8 3 1 2 5 7]
 [8 2 7 5 4 9 6 1 3]]

我开始编写一个带有回溯的迷宫求解算法，但意识到 Computerfile 已经就此制作了一个视频，而且如果没有优化功能，我无法制作出比他们的更有效的算法。

所以，我只会链接到 Computerfile 的视频。 迷宫求解。

这是一个非常棒的频道，Mike Pound 和其他嘉宾确实了解他们的内容。

希望您玩得开心，并喜欢阅读我的文章。

---

历史

• 2020年3月18日：初始版本