Python递归完整学习指南¶

1. 什么是递归？想象一下...¶

想象你正在看一个神奇的俄罗斯套娃！每打开一个娃娃，里面还有一个一模一样但更小的娃娃。这就像递归：一个函数不断调用自己，每次处理更小的问题，直到达到最基本的情况。

2. 递归的基本概念¶

2.1. 递归的两个要素¶

基本情况（Base Case）：停止递归的条件
递归步骤（Recursive Step）：将问题分解为更小的子问题

2.2. 递归的工作原理¶

def factorial(n):
    # 基本情况
    if n == 0 or n == 1:
        return 1
    # 递归步骤
    return n * factorial(n - 1)

# 调用示例
print(factorial(5))  # 输出：120

3. 常见递归示例¶

3.1. 斐波那契数列¶

def fibonacci(n):
    # 基本情况
    if n <= 1:
        return n
    # 递归步骤
    return fibonacci(n-1) + fibonacci(n-2)

# 打印斐波那契数列的前10个数
for i in range(10):
    print(fibonacci(i), end=" ")  # 输出：0 1 1 2 3 5 8 13 21 34

3.2. 阶乘计算¶

def factorial(n):
    # 基本情况
    if n == 0:
        return 1
    # 递归步骤
    return n * factorial(n-1)

# 计算5的阶乘
print(factorial(5))  # 输出：120

3.3. 二分查找¶

def binary_search(arr, target, left, right):
    # 基本情况
    if left > right:
        return -1

    # 找到中间位置
    mid = (left + right) // 2

    # 如果找到目标
    if arr[mid] == target:
        return mid
    # 递归步骤
    elif arr[mid] > target:
        return binary_search(arr, target, left, mid-1)
    else:
        return binary_search(arr, target, mid+1, right)

# 使用示例
arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(arr, 7, 0, len(arr)-1))  # 输出：3

4. 高级递归应用¶

4.1. 树的遍历¶

class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

def inorder_traversal(root):
    if root:
        # 递归遍历左子树
        inorder_traversal(root.left)
        # 访问根节点
        print(root.val, end=" ")
        # 递归遍历右子树
        inorder_traversal(root.right)

# 创建一个简单的二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# 中序遍历
inorder_traversal(root)  # 输出：4 2 5 1 3

4.2. 汉诺塔问题¶

def hanoi(n, source, auxiliary, target):
    if n == 1:
        print(f"将盘子1从{source}移动到{target}")
        return

    # 将n-1个盘子从source移动到auxiliary
    hanoi(n-1, source, target, auxiliary)
    # 将第n个盘子从source移动到target
    print(f"将盘子{n}从{source}移动到{target}")
    # 将n-1个盘子从auxiliary移动到target
    hanoi(n-1, auxiliary, source, target)

# 解决3个盘子的汉诺塔问题
hanoi(3, 'A', 'B', 'C')

5. 递归的优化¶

5.1. 尾递归¶

def factorial_tail(n, accumulator=1):
    if n == 0:
        return accumulator
    return factorial_tail(n-1, n * accumulator)

# 使用尾递归计算阶乘
print(factorial_tail(5))  # 输出：120

5.2. 记忆化递归¶

def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    return memo[n]

# 使用记忆化递归计算斐波那契数
print(fibonacci_memo(10))  # 输出：55

6. 注意事项¶

6.1. 递归的优点¶

代码简洁清晰
问题解决思路自然
适合处理树形结构

6.2. 递归的缺点¶

可能导致栈溢出
空间复杂度较高
重复计算问题

6.3. 使用建议¶

确保有明确的终止条件
考虑使用尾递归优化
大数据时考虑使用迭代

7. 进一步学习¶

def count_down(n):
    if n == 0:
        print("出发！")
    else:
        print(n)
        count_down(n-1)

count_down(5)