Python递归基础概念与应用

2023-04-15 00:00:00 概念递归基础

一、递归基础概念
递归是一种函数或算法调用自身的方式。简单来说，当一个函数或算法调用自身时，就称为递归。递归可以理解为是一种分治思想，即把大问题分解成一个个小问题，然后不断调用自身进行解决，最终将小问题解决完毕后回到最初的大问题，以此达到解决整个问题的目的。
递归的三要素：
（1）基本情况：递归终止的条件，也叫递归出口。
（2）递推公式：将复杂问题分解为简单问题的公式。
（3）递归调用：在函数里不停的调用其自身。
二、递归应用
递归应用非常广泛，主要包括以下几个方面：
（1）数学问题：如斐波那契数列、阶乘等。
示例代码：

# 斐波那契数列
def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)
# 阶乘
def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)

（2）图像问题：如树形结构、图形问题等。
示例代码：

# 树形结构遍历
class TreeNode:
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Tree:
    def __init__(self, root=None):
        self.root = root
    def preOrderTraversal(self, root):
        if root is None:
            return
        print(root.val)
        self.preOrderTraversal(root.left)
        self.preOrderTraversal(root.right)
# 图形问题
def dfs(x, y):
    if x < 0 or y < 0 or x >= n or y >= m or visited[x][y] or grid[x][y] == "0":
        return
    visited[x][y] = True
    dfs(x - 1, y)
    dfs(x + 1, y)
    dfs(x, y - 1)
    dfs(x, y + 1)

（3）游戏问题：如迷宫寻路、N皇后等。
示例代码：

# 迷宫寻路
def dfs(x, y):
    if x < 0 or y < 0 or x >= n or y >= m or visited[x][y] or maze[x][y] == "#":
        return False
    if maze[x][y] == "E":
        return True
    visited[x][y] = True
    for i in range(4):
        if dfs(x + dx[i], y + dy[i]):
            return True
    return False

（4）动态规划问题：如背包问题、最长公共子序列等。
示例代码：

# 01背包问题
def dfs(index, weight, value):
    global ans
    if index == n:
        ans = max(ans, value)
        return
    # 不选当前物品
    dfs(index + 1, weight, value)
    # 选当前物品
    if weight + w[index] <= s:
        dfs(index + 1, weight + w[index], value + v[index])

（5）其他问题：如字符串问题、排序问题等。
示例代码：

# 字符串问题
def isPalindrome(s):
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return isPalindrome(s[1:-1])
# 排序问题
def quicksort(nums):
    if len(nums) <= 1:
        return nums
    pivot = nums[int(len(nums) / 2)]
    left = [x for x in nums if x < pivot]
    middle = [x for x in nums if x == pivot]
    right = [x for x in nums if x > pivot]
    return quicksort(left) + middle + quicksort(right)

三、递归和循环
递归和循环是两种不同的思维方式，都可以用来解决问题。在一些情况下，两者的效率相当，但在一些情况下，循环的效率要更高一些。
对于递归和循环，需要根据具体情况来选择使用哪一种。在效率方面，循环通常是更好的选择，因为循环不涉及函数调用的开销，而且可以更好的利用缓存。但是，在处理一些具有递归性质的问题时，使用递归会更加直观和优美，而且代码也更加清晰。

相关文章