recursive

[giscus[bot]]

recursive

递归是一种常见的算法，指函数直接或间接地调用自身。递归可以解决的问题通常可以被分解为相似的子问题。这些子问题的结构与原始问题相似，但规模较小。

https://py.qizhen.xyz/recursive

[ruanqizhen]

数组求和

def array_sum(arr):
   if len(arr) == 0:
       return 0
   return arr[0] + array_sum(arr[1:])
   
print(array_sum([1,2,3,4,5]))

[ruanqizhen]

列表反转

def reverse_list(lst):
    # 基础情况：如果列表为空或只有一个元素，则直接返回
    if len(lst) <= 1:
        return lst
    # 递归：将最后一个元素放在列表前面，并对剩下的列表继续递归
    return [lst[-1]] + reverse_list(lst[:-1])

# 示例
my_list = [1, 2, 3, 4, 5]
reversed_list = reverse_list(my_list)

[ruanqizhen]

幂计算

1. 当 n = 0 时， x^n = 1。
2. 当 n 是正数时，如果 n 是偶数，可以将问题分解为 x^(n/2) * x^(n/2)；如果 n 是奇数，可以分解为 x * x^(n-1)。
3. 当 n 是负数时，x^n = 1/(x^(-n)。

def power(x, n):
    # 基本情况
    if n == 0:
        return 1
    elif n < 0:
        return 1 / power(x, -n)
    elif n % 2 == 0:
        half = power(x, n // 2)
        return half * half
    else:
        return x * power(x, n - 1)

# 测试代码
print(power(2, 10))  # 1024
print(power(2, -3))  # 0.125
print(power(5, 0))   # 1

[ruanqizhen]

排列组合

def permute(nums):
    # 基本情况：如果列表为空，返回一个空列表
    if len(nums) == 0:
        return [[]]
    
    # 结果存放所有的排列组合
    result = []
    
    # 遍历每个元素，将其固定为第一个位置
    for i in range(len(nums)):
        # 取出当前元素
        current = nums[i]
        # 剩下的其他元素
        remaining = nums[:i] + nums[i+1:]
        
        # 递归计算剩下元素的排列
        for perm in permute(remaining):
            result.append([current] + perm)
    
    return result

# 测试代码
data = [1, 2, 3]
permutations = permute(data)
print(permutations)

[ruanqizhen]

汉诺塔

递归终止条件：只有一个盘子时，直接移动到目标柱。
递归公式：将 n-1 个盘子从源柱移动到辅助柱，将第 n 个盘子移动到目标柱，再将 n-1 个盘子从辅助柱移动到目标柱。

def hanoi(n, source, helper, target):
   if n == 1:
	   print(f"Move disk 1 from {source} to {target}")
	   return
   hanoi(n-1, source, target, helper)
   print(f"Move disk {n} from {source} to {target}")
   hanoi(n-1, helper, source, target)

[ruanqizhen]

这是一个预设的迷宫，用来测试迷宫程序：

maze = [
    "■■■■■■■■■■■■■■■■■■■■■■■■■■■",
    "S      ■       ■          ■",
    "■ ■■■  ■ ■■■■■ ■ ■■■■■■■■ ■",
    "■   ■  ■     ■ ■        ■ ■",
    "■■■ ■  ■■■■■ ■ ■■■■■■■  ■ ■",
    "■          ■ ■          ■ ■",
    "■ ■■■■■■■■ ■ ■■■■■■■■■  ■ ■",
    "■        ■ ■       ■ ■  ■ ■",
    "■■■■■■ ■ ■ ■■■■■ ■■■ ■■■■ ■",
    "■      ■ ■       ■        ■",
    "■ ■■■■■■ ■■■■■■■ ■■ ■■■■■■■",
    "■        ■       ■        ■",
    "■■■■■■ ■■■ ■■■■■■■ ■■■■■■■■",
    "■            ■            ■",
    "■■■■■■■■■■■■ ■■■■■■■ ■■■■ ■",
    "■        ■   ■     ■ ■    ■",
    "■ ■■■■■■■■ ■■■ ■■■ ■■■ ■■■■",
    "■        ■ ■     ■        ■",
    "■■■■■■■■ ■ ■ ■■■■■■■■■■■■■■",
    "■          ■              E",
    "■■■■■■■■■■■■■■■■■■■■■■■■■■■"
]

[ruanqizhen]

八皇后问题

# 打印棋盘
def print_board(board):
    for row in board:
        print(" ".join("Q" if col else "." for col in row))
    print("\n")

# 检查是否可以在 (row, col) 放置皇后
def is_valid_posititon(board, row, col):
    # 检查同一列是否有皇后
    for i in range(row):
        if board[i][col]:
            return False

    # 检查左上对角线是否有皇后
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j]:
            return False

    # 检查右上对角线是否有皇后
    for i, j in zip(range(row, -1, -1), range(col, 8)):
        if board[i][j]:
            return False

    return True

def solve_8_queens(board, row):
    if row == 8:
        # 所有皇后已经放置，打印解决方案
        print_solution(board)

    for col in range(8):
        if is_valid_posititon(board, row, col):
            # 放置皇后
            board[row][col] = 1
            # 递归放置下一行的皇后
            solve_8_queens(board, row + 1)
            # 回溯：移除皇后
            board[row][col] = 0

board = [[0] * 8 for _ in range(8)]  # 空棋盘
solve_8_queens(board, 0)             # 从第 0 行开始查看