第39集：递归函数基础

学习目标

• 理解递归函数的概念
• 掌握递归函数的两个核心要素
• 学会使用递归解决问题
• 理解递归的执行过程
• 掌握递归函数的注意事项

一、什么是递归函数？

递归函数是指函数调用自身的函数。

基本概念

递归函数就像俄罗斯套娃：

• 大套娃里有小套娃
• 小套娃里有更小的套娃
• 直到最小的那个，不再嵌套

递归的两个核心要素

生活类比：数楼梯

# 递归方式数楼梯
def count_stairs(n):
    """数n级楼梯"""
    if n == 0:
        return 0  # 基准情况：数完了
    else:
        return 1 + count_stairs(n - 1)  # 递归情况：数完这一级，继续数下一级

count_stairs(5)  # 输出：5

二、递归函数的基本结构

递归模板

def recursive_function(parameters):
    # 1. 基准情况（终止条件）
    if 基准条件:
        return 结果
    
    # 2. 递归情况（调用自身）
    else:
        # 处理当前问题
        # 调用自身，参数更接近基准情况
        return recursive_function(新参数)

示例1：计算阶乘

def factorial(n):
    """计算n的阶乘"""
    # 基准情况
    if n == 0 or n == 1:
        return 1
    # 递归情况
    else:
        return n * factorial(n - 1)

print(factorial(5))  # 输出：120
# 解释：5! = 5 × 4 × 3 × 2 × 1 = 120

执行过程图解

factorial(5)
  = 5 × factorial(4)
    = 5 × (4 × factorial(3))
      = 5 × (4 × (3 × factorial(2)))
        = 5 × (4 × (3 × (2 × factorial(1))))
          = 5 × (4 × (3 × (2 × 1)))  ← 达到基准情况
          = 5 × 4 × 3 × 2 × 1
          = 120

示例2：累加求和

def sum_to_n(n):
    """计算1到n的和"""
    # 基准情况
    if n == 0:
        return 0
    # 递归情况
    else:
        return n + sum_to_n(n - 1)

print(sum_to_n(5))  # 输出：15
# 解释：1 + 2 + 3 + 4 + 5 = 15

三、常见的递归函数示例

示例3：斐波那契数列

def fibonacci(n):
    """计算斐波那契数列的第n项"""
    # 基准情况
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # 递归情况
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# 输出前10项
for i in range(10):
    print(f"fibonacci({i}) = {fibonacci(i)}")
# 输出：
# fibonacci(0) = 0
# fibonacci(1) = 1
# fibonacci(2) = 1
# fibonacci(3) = 2
# fibonacci(4) = 3
# fibonacci(5) = 5
# fibonacci(6) = 8
# fibonacci(7) = 13
# fibonacci(8) = 21
# fibonacci(9) = 34

示例4：计算幂次

def power(base, exponent):
    """计算base的exponent次方"""
    # 基准情况
    if exponent == 0:
        return 1
    # 递归情况
    else:
        return base * power(base, exponent - 1)

print(power(2, 3))   # 输出：8  (2³ = 8)
print(power(3, 4))   # 输出：81 (3⁴ = 81)
print(power(5, 0))   # 输出：1  (任何数的0次方都是1)

示例5：判断回文

def is_palindrome(s):
    """判断字符串是否是回文"""
    # 基准情况
    if len(s) <= 1:
        return True
    # 递归情况
    elif s[0] != s[-1]:
        return False
    else:
        return is_palindrome(s[1:-1])

print(is_palindrome("aba"))    # 输出：True
print(is_palindrome("abba"))   # 输出：True
print(is_palindrome("hello"))  # 输出：False
print(is_palindrome("racecar")) # 输出：True

示例6：计算最大公约数

def gcd(a, b):
    """计算最大公约数（欧几里得算法）"""
    # 基准情况
    if b == 0:
        return a
    # 递归情况
    else:
        return gcd(b, a % b)

print(gcd(48, 18))  # 输出：6
print(gcd(100, 25)) # 输出：25
print(gcd(17, 5))   # 输出：1

四、递归与迭代的对比

示例对比：阶乘

# 递归方式
def factorial_recursive(n):
    """递归计算阶乘"""
    if n == 0 or n == 1:
        return 1
    return n * factorial_recursive(n - 1)

# 迭代方式
def factorial_iterative(n):
    """迭代计算阶乘"""
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

print(factorial_recursive(5))  # 输出：120
print(factorial_iterative(5))  # 输出：120

对比表格

何时使用递归？

适合使用递归的场景：

• 问题可以分解为相似的子问题
• 数据结构具有递归特性（如树、图）
• 代码可读性更重要

适合使用迭代的场景：

• 需要更高的执行效率
• 内存有限
• 问题规模很大

五、递归的执行过程

示例：factorial(4)的执行过程

def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

# 调用 factorial(4)

调用过程（入栈）：

factorial(4) 入栈
  factorial(3) 入栈
    factorial(2) 入栈
      factorial(1) 入栈  ← 达到基准情况

返回过程（出栈）：

factorial(1) 返回 1
factorial(2) 返回 2 × 1 = 2
factorial(3) 返回 3 × 2 = 6
factorial(4) 返回 4 × 6 = 24

完整过程：

factorial(4)
= 4 × factorial(3)
= 4 × (3 × factorial(2))
= 4 × (3 × (2 × factorial(1)))
= 4 × (3 × (2 × 1))
= 4 × (3 × 2)
= 4 × 6
= 24

使用调试查看递归

def factorial_debug(n, depth=0):
    """带调试信息的阶乘函数"""
    indent = "  " * depth
    print(f"{indent}调用 factorial({n})")
    
    if n == 0 or n == 1:
        print(f"{indent}返回 1（基准情况）")
        return 1
    else:
        result = n * factorial_debug(n - 1, depth + 1)
        print(f"{indent}返回 {result}")
        return result

factorial_debug(4)

输出：

调用 factorial(4)
  调用 factorial(3)
    调用 factorial(2)
      调用 factorial(1)
      返回 1（基准情况）
    返回 2
  返回 6
返回 24

六、递归函数的注意事项

注意1：必须有基准情况

# ❌ 错误：缺少基准情况
def bad_recursive(n):
    return n + bad_recursive(n - 1)

# bad_recursive(5)  # 会导致栈溢出

# ✅ 正确：有基准情况
def good_recursive(n):
    if n == 0:
        return 0
    return n + good_recursive(n - 1)

注意2：必须向基准情况逼近

# ❌ 错误：不向基准情况逼近
def bad_recursive(n):
    if n == 0:
        return 0
    return n + bad_recursive(n)  # 参数不变

# ✅ 正确：向基准情况逼近
def good_recursive(n):
    if n == 0:
        return 0
    return n + good_recursive(n - 1)  # 参数递减

注意3：防止栈溢出

# ❌ 危险：递归深度过大
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

# factorial(10000)  # 可能导致栈溢出

# ✅ 更好的方式：限制递归深度或使用迭代
def factorial_safe(n):
    """安全的阶乘计算"""
    if n < 0:
        return None
    if n == 0:
        return 1
    if n > 1000:  # 限制递归深度
        print("警告：递归深度过大，改用迭代")
        result = 1
        for i in range(1, n + 1):
            result *= i
        return result
    return n * factorial_safe(n - 1)

注意4：考虑效率问题

# ❌ 低效：重复计算
def fibonacci_slow(n):
    """低效的斐波那契计算"""
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fibonacci_slow(n - 1) + fibonacci_slow(n - 2)

# fibonacci_slow(40)  # 非常慢

# ✅ 优化：使用记忆化
def fibonacci_fast(n, memo={}):
    """优化的斐波那契计算"""
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    elif n == 1:
        return 1
    memo[n] = fibonacci_fast(n - 1, memo) + fibonacci_fast(n - 2, memo)
    return memo[n]

# fibonacci_fast(40)  # 很快

七、实际应用案例

案例1：二分查找

def binary_search(arr, target, left=0, right=None):
    """二分查找（递归）"""
    if right is None:
        right = len(arr) - 1
    
    # 基准情况：未找到
    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)

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

案例2：汉诺塔问题

def hanoi(n, source, target, auxiliary):
    """汉诺塔问题"""
    # 基准情况：只有一个盘子
    if n == 1:
        print(f"将盘子1从{source}移动到{target}")
        return
    
    # 递归情况：
    # 1. 将n-1个盘子从源柱移到辅助柱
    hanoi(n - 1, source, auxiliary, target)
    
    # 2. 将最大的盘子从源柱移到目标柱
    print(f"将盘子{n}从{source}移动到{target}")
    
    # 3. 将n-1个盘子从辅助柱移到目标柱
    hanoi(n - 1, auxiliary, target, source)

# 使用示例：3个盘子
hanoi(3, "A", "C", "B")

输出：

将盘子1从A移动到C
将盘子2从A移动到B
将盘子1从C移动到B
将盘子3从A移动到C
将盘子1从B移动到A
将盘子2从B移动到C
将盘子1从A移动到C

案例3：列出目录结构

def list_directory(path, depth=0):
    """递归列出目录结构"""
    import os
    
    indent = "  " * depth
    
    # 列出当前目录内容
    for item in os.listdir(path):
        full_path = os.path.join(path, item)
        
        if os.path.isdir(full_path):
            # 如果是目录，递归处理
            print(f"{indent}📁 {item}/")
            list_directory(full_path, depth + 1)
        else:
            # 如果是文件，直接打印
            print(f"{indent}📄 {item}")

# 使用示例（注释掉，避免实际执行）
# list_directory("./my_folder")

案例4：生成所有排列

def permutations(elements):
    """生成所有排列"""
    # 基准情况
    if len(elements) <= 1:
        return [elements]
    
    # 递归情况
    result = []
    for i in range(len(elements)):
        # 取出当前元素
        current = elements[i]
        # 剩余元素
        remaining = elements[:i] + elements[i+1:]
        # 递归生成剩余元素的排列
        for perm in permutations(remaining):
            result.append([current] + perm)
    
    return result

# 使用示例
print(permutations([1, 2, 3]))
# 输出：[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

八、递归函数的优化技巧

技巧1：尾递归优化

# 普通递归
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

# 尾递归（Python不自动优化，但可以提高可读性）
def factorial_tail(n, accumulator=1):
    """尾递归阶乘"""
    if n == 0:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)

技巧2：记忆化（Memoization）

def fibonacci_memo(n, memo={}):
    """带记忆化的斐波那契"""
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    elif n == 1:
        return 1
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

# 使用装饰器实现记忆化
from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_lru(n):
    """使用LRU缓存的斐波那契"""
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fibonacci_lru(n - 1) + fibonacci_lru(n - 2)

技巧3：限制递归深度

import sys

# 设置递归深度限制
sys.setrecursionlimit(10000)

def safe_recursive(n):
    """限制递归深度的函数"""
    if n > 1000:
        print("警告：递归深度过大")
        return None
    if n == 0:
        return 0
    return n + safe_recursive(n - 1)

九、常见错误与调试

错误1：忘记基准情况

# ❌ 错误
def countdown(n):
    print(n)
    countdown(n - 1)

# countdown(10)  # 无限递归，直到栈溢出

# ✅ 正确
def countdown(n):
    print(n)
    if n > 0:
        countdown(n - 1)

错误2：递归参数不变

# ❌ 错误
def countdown(n):
    print(n)
    countdown(n)  # 参数不变，无限递归

# ✅ 正确
def countdown(n):
    print(n)
    if n > 0:
        countdown(n - 1)  # 参数递减

调试技巧：打印递归信息

def recursive_debug(n, depth=0):
    """带调试信息的递归函数"""
    indent = "  " * depth
    print(f"{indent}→ 调用：n={n}")
    
    if n == 0:
        print(f"{indent}← 返回：0（基准情况）")
        return 0
    else:
        result = n + recursive_debug(n - 1, depth + 1)
        print(f"{indent}← 返回：{result}")
        return result

recursive_debug(3)

十、小结

十一、课后练习

练习1

定义递归函数sum_recursive(n)，计算1到n的和。

练习2

定义递归函数power_recursive(base, exponent)，计算幂次。

练习3

定义递归函数reverse_string(s)，反转字符串。

练习4

定义递归函数count_down(n)，从n倒数到1。

练习5

定义递归函数find_max(arr)，找出列表中的最大值。