一、递归函数的基本使用
递归函数是编程中常用的技术之一，它允许函数调用自身来解决问题。递归函数的使用通常涉及以下几个基本要素：
1. 基案（Base Case）
基案是递归终止的条件。没有基案的递归函数将无限调用自身，最终导致栈溢出错误。
2. 递归案（Recursive Case）
递归案是函数调用自身的情况，它应该逐渐向基案靠拢。
3. 调用自身
递归函数必须在某个点调用自身，并且每次调用都应该使问题更接近基案。
示例：计算阶乘
阶乘是递归的经典例子，因为它定义为n! = n * (n-1)!，其中0!定义为1。
def factorial(n):
# 基案：0的阶乘是1
if n == 0:
return 1
# 递归案：n的阶乘是n乘以(n-1)的阶乘
else:
return n * factorial(n - 1)
# 测试递归函数
print(factorial(5)) # 输出: 120
示例：斐波那契数列
斐波那契数列是另一个递归的例子，其中每个数字是前两个数字的和。
def fibonacci(n):
# 基案：第0个和第1个斐波那契数是1
if n == 0 or n == 1:
return 1
# 递归案：第n个斐波那契数是前两个斐波那契数的和
else:
return fibonacci(n - 1) + fibonacci(n - 2)
# 测试递归函数
print(fibonacci(6)) # 输出: 8
注意事项
- 确保递归有明确的基案，以避免无限递归。
- 考虑递归的深度，过深的递归可能导致栈溢出。
- 分析递归的效率，有些问题可能不适合用递归解决，或者递归解决方案可能不是最高效的。
- 尾递归优化：某些编程语言支持尾递归优化，Python的CPython解释器默认不支持，但可以通过手动转换为循环来避免栈溢出。
递归是一种强大的工具，但需要谨慎使用，以确保它不会引发性能问题或栈溢出。
二、递归函数遇到的问题：
- 将
page_data=[]定义在递归函数内，导致每次递归调用会把page_data的值重置为[]。 - 递归调用的结果被添加到
page_data列表中，而不是直接赋值给page_data。这导致即使在找不到下一页的情况下，函数也不会立即返回page_data，而是继续被递归调用，导致无限递归。 - 缺少基案：原代码只有存在下一页时的递归案：获取当前页的全部文章并追加到
page_data，但缺少基案：不存在下一页时，直接返回page_data。导致多次调试打印page_data的值始终为[]。增加基案后，page_data的值返回正确。 - 将递归函数改为循环，以避免潜在的递归深度问题。
- 性能问题：递归可能不如迭代高效，尤其是在每次递归调用都有较大开销的情况下。分析递归的性能，考虑是否有更优的迭代解决方案。
def parse_page_soup(current_url, headers, context, page_data=None):
# 错误用法：每次递归调用page_data的值都被重置为[]。
page_data = []
# 处理当前页的数据
soup = get_soup(current_url, headers, context)
if not soup:
return page_data
# 处理列表跳转至详情页的数据
tag_list = soup.select('div.AllListCon a')
for tag in tag_list:
article_url = tag.get('href')
article_soup = get_soup(article_url, headers, context)
if article_soup:
page_data.append(parse_article_soup(article_soup))
# 查找下一页
next_page = soup.find('a', class_='next')
if next_page:
next_page_url = next_page.get('href')
# 错误用法，递归调用+合并结果
page_data += parse_page_soup(next_page_url, headers, context, page_data)
方案一：修改递归函数的调用方法
def parse_page_data(current_url, headers, context, page_data=None):
# 正确用法：增加对page_data值的判断。
if page_data is None:
page_data = []
# 处理当前页的数据
soup = get_soup(current_url, headers, context)
if not soup:
return page_data
# 处理列表跳转至详情页的数据
tag_list = soup.select('div.AllListCon a')
for tag in tag_list:
article_url = tag.get('href')
article_soup = get_soup(article_url, headers, context)
if article_soup:
page_data.append(parse_article_soup(article_soup))
# 查找下一页
next_page = soup.find('a', class_='next')
if next_page:
current_url = next_page.get('href')
# 递归调用并立即返回结果
return parse_page_data(current_url, headers, context, page_data)
# 一定要加不满足条件时的返回值，否则递归不满足时由于没有返回值会返回空
else:
return page_data
方案二：使用迭代（while循环）替换递归函数
def parse_page_data(base_url, headers, context):
page_data = []
curr_page_url = base_url
while curr_page_url:
# 获取当前页的soup对象
soup = get_soup(curr_page_url, headers, context)
if not soup:
break # 如果soup为空，直接跳出循环
# 处理当前页的数据
tag_list = soup.select('div.AllListCon a')
for tag in tag_list:
article_url = tag.get('href')
if not article_url.startswith(('http:', 'https:')):
article_url = urljoin(next_page_url, article_url)
article_soup = get_soup(article_url, headers, context)
if article_soup:
page_data.append(parse_article_soup(article_soup))
# 查找下一页的链接
next_page = soup.find('a', class_='next')
if next_page:
next_page_url = next_page.get('href')
if not next_page_url.startswith(('http:', 'https:')):
next_page_url = urljoin(next_page_url, next_page_url)
curr_page_url = next_page_url
else:
break # 如果没有下一页，跳出循环
return page_data # 循环结束后返回data_list
三、使用递归函数经常遇到的问题详细解析
使用递归函数时，开发者可能会遇到几个常见问题。以下是这些问题的详细解析和解决方法：
1. 无限递归（Infinite Recursion）
如果递归函数没有正确的基案或递归条件设置不当，函数可能会无限调用自身，导致程序永远不会停止。
解决方法：
- 确保递归函数有明确的基案，且递归调用逐步逼近基案。
2. 栈溢出（Stack Overflow）
每次函数调用都会在内存的调用栈上添加一条记录。递归调用太深时，可能会超出调用栈的最大容量限制，导致栈溢出错误。
解决方法：
- 优化递归逻辑，减少递归深度。
- 使用尾递归优化（如果语言支持）。
- 考虑使用迭代（循环）代替递归。
3. 重复计算（Redundant Computations）
某些递归算法可能会多次计算相同的子问题，这在动态规划问题中尤为常见。
解决方法：
- 使用记忆化（Memoization）技术，存储已经计算过的结果，避免重复计算。
- 将递归转换为动态规划算法。
4. 性能问题（Performance Issues）
递归可能不如迭代高效，尤其是在每次递归调用都有较大开销的情况下。
解决方法：
- 分析递归的性能，考虑是否有更优的迭代解决方案。
- 使用尾递归优化减少开销。
5. 难以理解的逻辑（Complex Logic）
递归逻辑可能难以理解和维护，尤其是对于初学者。
解决方法：
- 使用清晰的基案和递归逻辑。
- 添加注释和文档，说明递归的工作原理。
6. 语言或环境限制（Language or Environment Limitations）
不同的编程语言对递归的支持程度不同，例如Python的默认递归深度限制较低。
解决方法：
- 了解并设置语言的递归限制（如Python中的
sys.setrecursionlimit()）。 - 使用迭代或增加栈空间。
7. 尾递归未优化（Tail Recursion Not Optimized）
尾递归是一种特殊的递归形式，其中递归调用是函数体中的最后一个操作。尽管尾递归理论上可以优化以减少栈使用，但并非所有语言或解释器/编译器都会自动进行这种优化。
解决方法：
- 手动转换尾递归为循环。
- 使用支持尾递归优化的语言或工具。
8. 资源消耗（Resource Consumption）
递归函数可能会消耗大量内存或其他资源，尤其是在递归树非常深的情况下。
解决方法：
- 优化算法以减少资源消耗。
- 使用生成器等技术减少内存占用。
9. 调试困难（Debugging Difficulty）
递归函数可能难以调试，因为调用栈可能非常深，且错误可能在递归的深层发生。
解决方法：
- 使用调试工具逐步跟踪递归调用。
- 添加打印语句以跟踪递归的进度和状态。
通过了解和解决这些问题，你可以更有效地使用递归函数，并避免常见的陷阱。在某些情况下，迭代可能是更好的选择，特别是当递归逻辑复杂或存在性能问题时。
