递归的基本概念

• 递归函数: 一个函数在其定义中调用自身
• 递归条件:
  • 基线条件(Base Case): 递归终止的条件, 防止无限递归
  • 递归条件(Recursive Case): 将问题分解为更小的子问题, 并调用自身解决

递归的基本结构

def recursive_func(参数):
  if 基线条件:
    return 基线结果
  else:
    更新参数
    return recursive_func(更新后的参数)

递归的经典示例

1. 计算阶乘 阶乘的定义是: n! = n * (n - 1), 其中 0! = 1

def factorial(n):
  if n == 0:  # 基线条件
    return 1
  else:
    return factorial(n * (n-1))

2. 计算斐波那契数列 斐波那契数列的定义是: F(n) = F(n-1) + F(n-2), 其中 F(0) = 0, F(1) = 1

def fibonacci():
  if n == 0:
    return 0
  elif n == 1:
    return 1
  else:
    return fabonacci(n-1) + fabonacci(n-2)

3. 遍历目录下的所有文件

• 基线条件: 如果是文件, 打印路径
• 递归条件: 如果是目录, 递归调用

import os

def list_file(path):
  for item in os.listdir(path):
    full_path = os.path.join(path, item)
    if os.path.isdir(full_path):  # 如果是目录, 递归调用
      list_files(full_path)
    else: # 如果是文件, 打印路径
      print(full_path)

递归的优缺点

优点 :

• 代码简洁: 递归可以用较少的代码解决复杂问题
• 直观: 对于树形结构, 递归的实现更符合问题的自然描述

缺点 :

• 性能问题: 递归可能产生大量的函数调用, 导致栈溢出或效率低下
• 调试困难: 递归的调用链较长时, 调试和跟踪问题可能比较困难

递归的优化

1. 尾递归优化
   尾递归是指递归调用是函数的最后一步操作。某些编程语言支持尾递归优化, 但Python不支持
2. 记忆化
   通过缓存已计算的结果, 避免重复计算

def fibonacci(n, memo = {}):
  if n in memo:   # 如果结果已缓存, 直接返回结果
    return memo[n]
  if n == 0:    # 基线条件
    return 0
  elif n == 1:  # 基线条件
    return 1
  else:   #递归条件
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

3. 转换为迭代
   将递归问题转换为循环问题, 避免栈溢出

def factorial(n):
"""
计算n的阶乘
params:
  n(int): 待计算的数
return:
  result(int): n的阶乘
"""
  result = 1
  for i in range(1, n + 1):
    result *= i
  return result

注意事项

• 栈溢出: Python默认的递归深度是1000, 可以通过sys.setrecursionlimit()修改, 但不建议滥用
• 基线条件: 必须确保递归有终止条件, 否则会无限递归