第6章 函数及其应用
6.4 递归函数
📚 本节学习目标
1.理解函数的运行机制：掌握函数调用、执行、返回的完整流程
2.掌握递归的核心思想：理解”问题分解”与”回推处理”的本质
3.学会编写递归函数：能够正确设置递归条件和边界条件
4.培养计算思维：通过递归思想解决复杂问题
🔗 知识回顾与串联
在开始学习递归函数之前，让我们先回顾一下前面章节学过的相关知识，这些知识将帮助我们更好地理解函数的运行机制：
📌 第1章回顾：Python程序结构 - 我们学习了Python程序由模块、函数、语句组成 - 函数是组织好的、可重复使用的代码块 - 使用def关键字定义函数
📌 第2章回顾：变量与数据类型 - 变量是存储数据的容器 - 数值型数据（int, float）在函数间传递 - 字符串的索引和切片操作
📌 第3章回顾：分支结构 - if-else条件判断语句 - 条件表达式用于控制程序流程 - 逻辑运算（and, or, not）
📌 第4章回顾：循环结构 - for循环和while循环 - break和continue控制循环 - 循环的嵌套使用
📌 第5章回顾：组合数据类型 - 列表、元组、字典、集合的基本操作 - 这些数据类型可以作为函数的参数和返回值
📌 第6章前面内容回顾 - 函数的定义与调用（6.1节） - 参数传递方式（6.2节）：值传递、引用传递、按参数名传递、默认值传递 - 变量的作用域（6.3节）：局部变量和全局变量
💡 本节核心问题：当我们调用一个函数时，Python内部到底发生了什么？函数调用结束后，程序是如何知道返回到哪里继续执行的？
6.4.1 函数的运行机制
一、函数调用的完整流程
在深入学习递归之前，我们必须先彻底理解函数的运行机制。只有理解了函数是如何被调用、执行和返回的，才能真正掌握递归的本质。
1.1 函数调用的三个阶段
当一个程序包含多个函数时，函数的执行遵循以下规律：
┌─────────────────────────────────────────────────────────┐│ 函数调用流程图 │├─────────────────────────────────────────────────────────┤│ ││ 主调函数 被调函数 ││ │ │ ││ │ ① 遇到函数调用 │ ││ │ ② 保存当前执行位置 │ ││ │ ③ 跳转执行 │ ││ ├──────────────────────────>│ ││ │ │ ④ 执行函数体 ││ │ │ ⑤ 遇到return/结束 ││ │ ⑦ 继续执行 │ ││ │<──────────────────────────┤ ⑥ 返回调用位置 ││ │ │ ││ ▼ ▼ ││ │└─────────────────────────────────────────────────────────┘
1.2 详细执行步骤
步骤1：函数调用的开始
对于包含多个函数的程序，执行总是从主程序（或主函数）开始。当执行流程遇到函数调用时：
·当前函数的执行被暂停（挂起）
·系统保存当前执行位置（即函数调用语句的地址，以便返回时继续执行）
·程序控制权转移给被调用函数
步骤2：参数传递
如果函数调用时存在参数传递：
·实参的数据传递给形参（根据第6.2节学习的参数传递规则）
·对于不可变类型（int, float, str, tuple）：值传递，形参是实参的副本
·对于可变类型（list, dict, set）：引用传递，形参和实参指向同一对象
步骤3：执行被调用函数
·执行被调用函数的函数体
·逐行执行函数体内的语句
·可以包含任意合法的Python语句（赋值、分支、循环等）
步骤4：函数返回
当遇到以下情况之一时，被调用函数结束执行：
·遇到return语句：将返回值带回给调用者
·函数体执行完毕：自动返回（返回值为None）
步骤5：返回到调用函数
·程序控制权返回到调用函数
·从函数调用的位置继续执行
·如果被调用函数有返回值，用返回值替换原来的函数调用表达式
二、代码演示：函数运行机制
让我们通过一个具体的例子来观察函数的运行机制：
示例1：基本函数调用流程
# 定义一个简单的函数：计算CK大学学生某门课程的总成绩def calculate_total_score(midterm, final, daily): """ 计算学生总成绩 midterm: 期中考试成绩（占30%） final: 期末考试成绩（占50%） daily: 平时成绩（占20%） """ print(f" [被调函数] 开始计算总成绩...") print(f" [被调函数] 期中成绩: {midterm}, 期末成绩: {final}, 平时成绩: {daily}") total = midterm * 0.3 + final * 0.5 + daily * 0.2 print(f" [被调函数] 计算完成，总成绩: {total}") print(f" [被调函数] 准备返回结果...") return total# 主程序print("=" * 50)print("【主程序】开始执行")print("=" * 50)print("\n【主程序】准备调用calculate_total_score函数")print("【主程序】参数: 期中=85, 期末=90, 平时=88")# 函数调用点result = calculate_total_score(85, 90, 88)print("\n【主程序】函数调用返回，继续执行")print(f"【主程序】获得返回值: {result}")print("【主程序】程序结束")
运行结果分析：
==================================================【主程序】开始执行==================================================【主程序】准备调用calculate_total_score函数【主程序】参数: 期中=85, 期末=90, 平时=88[被调函数] 开始计算总成绩...[被调函数] 期中成绩: 85, 期末成绩: 90, 平时成绩: 88[被调函数] 计算完成，总成绩: 87.5[被调函数] 准备返回结果...【主程序】函数调用返回，继续执行【主程序】获得返回值: 87.5【主程序】程序结束
📌 关键观察：注意主程序和被调函数的执行顺序，主程序在调用点暂停，被调函数执行完毕后，主程序从调用点继续执行。
示例2：多层函数调用
让我们看一个更复杂的例子，展示函数调用的嵌套：
# 定义函数：计算CK大学学生的绩点def calculate_gpa(score): """根据成绩计算绩点""" print(f" [calculate_gpa] 接收到成绩: {score}") if score >= 90: gpa = 4.0 elif score >= 85: gpa = 3.7 elif score >= 82: gpa = 3.3 elif score >= 78: gpa = 3.0 elif score >= 75: gpa = 2.7 elif score >= 72: gpa = 2.3 elif score >= 68: gpa = 2.0 elif score >= 64: gpa = 1.5 elif score >= 60: gpa = 1.0 else: gpa = 0.0 print(f" [calculate_gpa] 计算得绩点: {gpa}") return gpa# 定义函数：计算加权平均绩点def calculate_weighted_gpa(scores, credits): """ 计算加权平均绩点 scores: 成绩列表 credits: 学分列表 """ print(f" [calculate_weighted_gpa] 开始计算加权平均绩点") print(f" [calculate_weighted_gpa] 成绩列表: {scores}") print(f" [calculate_weighted_gpa] 学分列表: {credits}") total_weighted_gpa = 0 total_credits = 0 # 遍历每门课程（使用第4章学习的for循环） for i in range(len(scores)): print(f"\n [calculate_weighted_gpa] 处理第{i+1}门课程...") # 调用calculate_gpa函数（嵌套调用） gpa = calculate_gpa(scores[i]) weighted_gpa = gpa * credits[i] total_weighted_gpa += weighted_gpa total_credits += credits[i] print(f" [calculate_weighted_gpa] 该课程加权绩点: {weighted_gpa}") result = total_weighted_gpa / total_credits print(f"\n [calculate_weighted_gpa] 加权平均绩点: {result:.2f}") return result# 主程序print("=" * 60)print("【主程序】CK大学学生绩点计算系统")print("=" * 60)# 某学生的成绩和学分（使用第5章学习的列表）student_scores = [92, 88, 85, 90, 78] # 5门课的成绩student_credits = [3, 4, 2, 3, 2] # 对应的学分print(f"\n【主程序】学生成绩: {student_scores}")print(f"【主程序】课程学分: {student_credits}")print("\n【主程序】调用calculate_weighted_gpa函数...")final_gpa = calculate_weighted_gpa(student_scores, student_credits)print(f"\n【主程序】该学生的加权平均绩点为: {final_gpa:.2f}")print("【主程序】程序结束")
执行流程分析：
【主程序】开始│├── 调用 calculate_weighted_gpa(scores, credits)│││├── 第1次循环: i=0│││││├── 调用 calculate_gpa(92)│││└── 返回 4.0│││││└── 继续执行...│││├── 第2次循环: i=1│││││├── 调用 calculate_gpa(88)│││└── 返回 3.7│││││└── 继续执行...│││└── ...（继续循环）│└── 返回主程序，继续执行
三、函数调用栈（Call Stack）的概念
为了更深入地理解函数运行机制，我们需要了解调用栈（Call Stack）的概念。
3.1 什么是调用栈？
调用栈是计算机内存中的一块特殊区域，用于跟踪函数调用的顺序和状态。它遵循后进先出（LIFO, Last In First Out）的原则。
┌─────────────────────────────────────┐│ 调用栈示意图 │├─────────────────────────────────────┤│ ││ 栈顶 ──> ┌─────────────────┐ ││ │ 当前执行的函数 │ ││ ├─────────────────┤ ││ │ 调用者的信息 │ ││ ├─────────────────┤ ││ │ 更早的调用者 │ ││ ├─────────────────┤ ││ │ ... │ ││ └─────────────────┘ ││ 栈底 ││ │└─────────────────────────────────────┘
3.2 调用栈的工作过程
函数调用时（入栈）： 1. 保存当前函数的执行状态（局部变量、执行位置等） 2. 将这些信息压入调用栈 3. 跳转到被调用函数执行
函数返回时（出栈）： 1. 从调用栈顶弹出保存的信息 2. 恢复调用者的执行状态 3. 从调用位置继续执行
3.3 代码演示：观察调用栈
import tracebackdef function_c(): """最内层函数""" print("\n进入 function_c") print("当前调用栈：") traceback.print_stack() print("离开 function_c\n") return "C的结果"def function_b(): """中间层函数""" print("进入 function_b") result = function_c() print(f"function_c 返回: {result}") print("离开 function_b") return "B的结果"def function_a(): """最外层函数""" print("进入 function_a") result = function_b() print(f"function_b 返回: {result}") print("离开 function_a") return "A的结果"# 主程序print("=" * 50)print("演示调用栈的工作过程")print("=" * 50)print("\n【主程序】开始执行")final_result = function_a()print(f"\n【主程序】最终获得: {final_result}")print("【主程序】结束")
输出分析：
从调用栈的输出中，我们可以看到函数调用的层次结构： - 最底层是主程序 - 然后是 function_a - 接着是 function_b - 最顶层是 function_c（当前正在执行的函数）
当 function_c 返回时，它会从栈顶移除，控制权回到 function_b，依此类推。
四、参数传递的深入理解
回顾第6.2节学习的参数传递知识，让我们通过代码再次确认：
4.1 不可变类型的传递（值传递）
def modify_immutable(x): """尝试修改不可变类型""" print(f" [函数内] 修改前 x = {x}, id = {id(x)}") x = x + 10 # 创建新对象 print(f" [函数内] 修改后 x = {x}, id = {id(x)}")# 主程序num = 100print(f"【主程序】调用前 num = {num}, id = {id(num)}")modify_immutable(num)print(f"【主程序】调用后 num = {num}, id = {id(num)}")
结论：不可变类型在函数内的修改不会影响外部变量。
4.2 可变类型的传递（引用传递）
def modify_mutable(lst): """修改可变类型""" print(f" [函数内] 修改前 lst = {lst}, id = {id(lst)}") lst.append(100) # 修改原对象 print(f" [函数内] 修改后 lst = {lst}, id = {id(lst)}")# 主程序my_list = [1, 2, 3]print(f"【主程序】调用前 my_list = {my_list}, id = {id(my_list)}")modify_mutable(my_list)print(f"【主程序】调用后 my_list = {my_list}, id = {id(my_list)}")
结论：可变类型在函数内的修改会影响外部变量。
💡 为什么这很重要？ 理解参数传递机制对于编写递归函数至关重要，因为递归函数需要正确地处理参数，避免产生意外的副作用。
五、return语句的多种形式
回顾第6.1节的内容，return语句有多种使用方式：
5.1 返回单个值
def get_square(n): """返回n的平方""" return n ** 2result = get_square(5)print(result) # 输出: 25
5.2 返回多个值（实际是返回元组）
def get_min_max(numbers): """返回列表中的最小值和最大值""" return min(numbers), max(numbers)# 使用第5章学习的列表scores = [78, 92, 85, 67, 90]min_score, max_score = get_min_max(scores)print(f"最低分: {min_score}, 最高分: {max_score}")
5.3 没有return语句（返回None）
def print_info(name): """只打印信息，不返回值""" print(f"学生姓名: {name}")result = print_info("张三")print(f"返回值: {result}") # 输出: 返回值: None
5.4 提前返回（多分支返回）
def get_grade(score): """根据分数返回等级""" if score >= 90: return "优秀" elif score >= 80: return "良好" elif score >= 70: return "中等" elif score >= 60: return "及格" else: return "不及格"# 测试（使用第3章学习的分支结构）print(get_grade(95)) # 优秀print(get_grade(82)) # 良好print(get_grade(55)) # 不及格
六、综合案例：CK大学学生成绩管理系统
让我们综合运用前面章节的知识，创建一个完整的案例：
# CK大学学生成绩管理系统def input_scores(): """输入学生成绩（使用第4章的循环和第5章的列表）""" scores = [] print("请输入5门课程的成绩（输入-1结束）：") while len(scores) < 5: try: score = float(input(f"第{len(scores)+1}门课程成绩: ")) if score == -1: break if 0 <= score <= 100: scores.append(score) else: print("成绩必须在0-100之间！") except ValueError: print("请输入有效的数字！") return scoresdef calculate_statistics(scores): """计算统计信息""" if not scores: return None, None, None total = sum(scores) # 使用第5章列表的内置函数 average = total / len(scores) max_score = max(scores) min_score = min(scores) return average, max_score, min_scoredef determine_pass_status(scores): """判断是否全部及格（使用第3章的分支和第4章的循环）""" for score in scores: if score < 60: return False, score return True, Nonedef generate_report(name, scores): """生成学生成绩报告""" print("\n" + "=" * 50) print(f" CK大学学生成绩报告单") print("=" * 50) print(f"学生姓名: {name}") print(f"课程数量: {len(scores)}门") print("-" * 50) for i, score in enumerate(scores, 1): status = "及格" if score >= 60 else "不及格" print(f"课程{i}: {score:6.2f}分 ({status})") print("-" * 50) avg, max_s, min_s = calculate_statistics(scores) print(f"平均分: {avg:6.2f}分") print(f"最高分: {max_s:6.2f}分") print(f"最低分: {min_s:6.2f}分") all_pass, fail_score = determine_pass_status(scores) if all_pass: print("\n✓ 所有课程均已通过！") else: print(f"\n✗ 存在不及格课程（最低分: {fail_score}分）") print("=" * 50)# 主程序print("欢迎使用CK大学学生成绩管理系统！")student_name = input("请输入学生姓名: ")# 获取成绩student_scores = input_scores()# 生成报告if student_scores: generate_report(student_name, student_scores)else: print("没有输入有效成绩！")print("\n程序结束，感谢使用！")
七、本节小结
7.1 核心知识点
1.函数调用的三个阶段：
o调用阶段：保存现场，跳转执行
o执行阶段：执行函数体
o返回阶段：恢复现场，继续执行
2.参数传递机制：
o不可变类型：值传递（创建副本）
o可变类型：引用传递（共享对象）
3.调用栈的作用：
o跟踪函数调用顺序
o保存和恢复执行状态
o实现函数的嵌套调用和返回
7.2 与前面章节的联系
章节 | 本节应用 |
第2章 | 变量、数据类型作为函数参数 |
第3章 | 分支结构在函数内的使用 |
第4章 | 循环结构在函数内的使用 |
第5章 | 列表等组合类型作为函数参数和返回值 |
第6.1-6.3节 | 函数定义、参数传递、作用域 |
7.3 思考问题
1.如果函数A调用函数B，函数B又调用函数C，调用栈中会有几层？
2.为什么理解函数运行机制对编写递归函数很重要？
3.在递归函数中，调用栈会发生什么变化？
6.4.2 递归函数
一、什么是递归？
1.1 递归的直观理解
递归（Recursion） 是一种重要的算法思想，它指的是：函数在执行过程中调用自身。
让我们用一个生活中的例子来理解递归：
🎯 例子：重庆火锅的调料搭配
假设你要调配一碗完美的重庆火锅油碟，规则是： - 基础是香油 - 每次可以添加一种调料（蒜泥、香菜、葱花、蚝油等） - 直到你觉得味道合适了，就停止添加
这个过程就是递归的：每次都在已有的基础上添加新的东西，直到满足某个条件停止。
1.2 递归的数学起源
递归的思想来源于数学中的递推关系：
·斐波那契数列：F(n) = F(n-1) + F(n-2)
·阶乘：n! = n × (n-1)!
·等差数列：aₙ = aₙ₋₁ + d
这些都是用自身定义自身的例子，这就是递归的本质。
二、递归的核心思想：两步走策略
递归的实现过程可以分为两个明确的步骤：
2.1 第一步：问题分解（递推）
把一个大问题分解为若干个性质相同的较小问题。
│ 问题分解示意图 │├─────────────────────────────────────────────────────────┤│ ││ 大问题: 计算5! ││ │ ││ ├──> 分解为: 5 × 4! ││ │ │ ││ │ ├──> 分解为: 4 × 3! ││ │ │ │ ││ │ │ ├──> 分解为: 3 × 2! ││ │ │ │ │ ││ │ │ │ ├──> 2 × 1! ││ │ │ │ │ │ ││ │ │ │ │ └──> 1 ││ │ │ │ │ ││ ▼ ▼ ▼ ▼ ││ 边界条件: 当问题小到可以直接求解时停止分解 ││ │└─────────────────────────────────────────────────────────┘
问题分解的关键： - 每次分解都要使问题规模变小 - 分解后的子问题与原问题性质相同 - 分解过程要有明确的终止条件（边界条件）
2.2 第二步：回推处理（回归）
从最小的问题入手，依次求解较大问题，最终得出原问题的解。
┌─────────────────────────────────────────────────────────┐│ 回推处理示意图 │├─────────────────────────────────────────────────────────┤│ ││ 已知: 1! = 1 ││ │ ││ ├──> 回推: 2! = 2 × 1! = 2 × 1 = 2 ││ │ │ ││ │ ├──> 回推: 3! = 3 × 2! = 3 × 2 = 6 ││ │ │ │ ││ │ │ ├──> 回推: 4! = 4 × 3! ││ │ │ │ = 4 × 6 ││ │ │ │ = 24 ││ │ │ │ ││ │ │ └──> 回推: 5! = 5 × 4! ││ │ │ = 5 × 24 ││ │ │ = 120 ✓ ││ ▼ ▼ ▼ ││ 最终结果: 5! = 120 ││ │└─────────────────────────────────────────────────────────┘
回推处理的关键： - 从边界条件开始 - 利用已解决的子问题的解 - 逐步构建更大问题的解
三、递归的两个必要条件
编写正确的递归函数，必须满足以下两个条件：
3.1 条件一：递归关系（Recurrence Relation）
定义：描述大问题与子问题之间的关系，即如何用子问题的解来构造原问题的解。
形式：
f(n) = 某种操作(f(n-1), f(n-2), ...)
例子： - 阶乘：n! = n × (n-1)! - 斐波那契：F(n) = F(n-1) + F(n-2) - 累加：sum(n) = n + sum(n-1)
3.2 条件二：边界条件（Base Case）
定义：递归终止的条件，当问题规模小到可以直接求解时，不再继续分解。
作用： - 防止无限递归（死循环） - 提供回推的起点 - 确保递归能够结束
形式：
if n == 边界值:return 直接可计算的结果
例子： - 阶乘：0! = 1, 1! = 1 - 斐波那契：F(0) = 0, F(1) = 1 - 累加：sum(1) = 1
3.3 两个条件的关系
┌─────────────────────────────────────────────────────────┐│ 递归函数的结构框架 │├─────────────────────────────────────────────────────────┤│ ││ def recursive_function(n): ││ # 1. 边界条件（终止条件） ││ if n == base_case: ││ return base_value ││ ││ # 2. 递归关系（继续分解） ││ else: ││ return some_operation(n, recursive_function(n-1))││ │└─────────────────────────────────────────────────────────┘
⚠️ 重要警告：如果缺少边界条件，递归将无限进行，最终导致栈溢出（Stack Overflow）错误！
四、经典案例：求n的阶乘（n!）
让我们通过最经典的递归案例——阶乘计算，来深入理解递归的工作原理。
4.1 数学定义
n! = n × (n-1) × (n-2) × ... × 2 × 1特别地：0! = 1（边界条件）1! = 1（边界条件）
递推公式：
n! = n × (n-1)!（当 n > 1 时）
4.2 递归实现
def factorial(n): """ 计算n的阶乘（递归实现） 参数: n: 非负整数 返回: n的阶乘值 """ # ========== 边界条件 ========== # 当n为0或1时，直接返回1 # 这是递归的终止条件，防止无限递归 if n == 0 or n == 1: print(f" 到达边界条件: {n}! = 1") return 1 # ========== 递归关系 ========== # n! = n × (n-1)! # 这里调用函数自身，但参数变小了（n-1） else: print(f" 分解: {n}! = {n} × {n-1}!") result = n * factorial(n - 1) print(f" 回推: {n}! = {n} × {(n-1)}! = {result}") return result# 测试代码print("=" * 50)print("计算5的阶乘")print("=" * 50)n = 5result = factorial(n)print(f"\n最终结果: {n}! = {result}")
4.3 执行过程详解
让我们详细跟踪factorial(5)的执行过程：
【调用 factorial(5)】│├── n = 5, 不满足边界条件├── 打印: "分解: 5! = 5 × 4!"├── 需要计算: 5 * factorial(4)││【调用 factorial(4)】│││├── n = 4, 不满足边界条件│├── 打印: "分解: 4! = 4 × 3!"│├── 需要计算: 4 * factorial(3)││││【调用 factorial(3)】│││││├── n = 3, 不满足边界条件││├── 打印: "分解: 3! = 3 × 2!"││├── 需要计算: 3 * factorial(2)││││││【调用 factorial(2)】│││││││├── n = 2, 不满足边界条件│││├── 打印: "分解: 2! = 2 × 1!"│││├── 需要计算: 2 * factorial(1)││││││││【调用 factorial(1)】│││││││││├── n = 1, 满足边界条件！││││├── 打印: "到达边界条件: 1! = 1"││││└── 返回: 1│││││││├── 得到 factorial(1) = 1│││├── 计算: 2 * 1 = 2│││├── 打印: "回推: 2! = 2 × 1! = 2"│││└── 返回: 2│││││├── 得到 factorial(2) = 2││├── 计算: 3 * 2 = 6││├── 打印: "回推: 3! = 3 × 2! = 6"││└── 返回: 6│││├── 得到 factorial(3) = 6│├── 计算: 4 * 6 = 24│├── 打印: "回推: 4! = 4 × 3! = 24"│└── 返回: 24│├── 得到 factorial(4) = 24├── 计算: 5 * 24 = 120├── 打印: "回推: 5! = 5 × 4! = 120"└── 返回: 120最终结果: 5! = 120
4.4 调用栈的变化
阶段1：递推过程（函数入栈） 栈顶 ──> ┌──────────────┐ │ factorial(1) │ ← 当前执行 ├──────────────┤ │ factorial(2) │ ← 等待factorial(1)的结果 ├──────────────┤ │ factorial(3) │ ← 等待factorial(2)的结果 ├──────────────┤ │ factorial(4) │ ← 等待factorial(3)的结果 ├──────────────┤ │ factorial(5) │ ← 等待factorial(4)的结果 ├──────────────┤ │ 主程序 │ ← 等待factorial(5)的结果 └──────────────┘ 栈底阶段2：到达边界条件 factorial(1) 返回 1阶段3：回推过程（函数出栈） 栈顶 ──> ┌──────────────┐ │ factorial(2) │ ← 得到1，计算2×1=2，返回2 ├──────────────┤ │ factorial(3) │ ← 得到2，计算3×2=6，返回6 ├──────────────┤ │ factorial(4) │ ← 得到6，计算4×6=24，返回24 ├──────────────┤ │ factorial(5) │ ← 得到24，计算5×24=120，返回120 ├──────────────┤ │ 主程序 │ ← 得到120 └──────────────┘
五、更多递归案例
5.1 案例1：计算1+2+3+…+n
数学分析：
sum(n) = 1 + 2 + 3 + ... + (n-1) + n= sum(n-1) + n边界条件：sum(1) = 1
代码实现：
def recursive_sum(n): """ 计算1+2+3+...+n的递归实现 知识点串联： - 使用了第6章的函数定义 - 使用了第3章的分支结构 - 使用了第2章的数值运算 """ # 边界条件 if n == 1: print(f" 边界: sum(1) = 1") return 1 # 递归关系: sum(n) = sum(n-1) + n print(f" 分解: sum({n}) = sum({n-1}) + {n}") partial_sum = recursive_sum(n - 1) result = partial_sum + n print(f" 回推: sum({n}) = {partial_sum} + {n} = {result}") return result# 测试print("=" * 50)print("计算1+2+3+...+10")print("=" * 50)n = 10total = recursive_sum(n)print(f"\n1+2+3+...+{n} = {total}")# 验证（使用第4章的循环）verification = sum(range(1, n + 1))print(f"验证结果: {verification}")
5.2 案例2：斐波那契数列
问题描述：斐波那契数列是这样一个数列：0, 1, 1, 2, 3, 5, 8, 13, 21, … 从第三项开始，每一项都等于前两项之和。
数学定义：
F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2)（当 n >= 2 时）
代码实现：
def fibonacci(n): """ 计算斐波那契数列的第n项 注意：这个实现虽然直观，但效率较低（存在大量重复计算） """ # 边界条件 if n == 0: return 0 elif n == 1: return 1 # 递归关系: F(n) = F(n-1) + F(n-2) else: result = fibonacci(n - 1) + fibonacci(n - 2) return result# 测试：输出前10项print("=" * 50)print("斐波那契数列前10项")print("=" * 50)for i in range(10): print(f"F({i}) = {fibonacci(i)}")# 使用列表存储结果（第5章知识）print("\n使用列表存储结果:")fib_list = [fibonacci(i) for i in range(10)]print(fib_list)
递归树分析：
fib(5)/\fib(4)fib(3)/\/\fib(3)fib(2) fib(2)fib(1)/\......1fib(2)fib(1)...1
💡 思考题：观察上面的递归树，你能发现什么问题吗？（提示：注意fib(2)和fib(3)被计算了几次？）
5.3 案例3：字符串反转
问题描述：将一个字符串反转。例如，“CK大学” → “学大KC”
递归思路：
reverse("abcde") = "e" + reverse("abcd")= "e" + "d" + reverse("abc")= "e" + "d" + "c" + reverse("ab")= "e" + "d" + "c" + "b" + reverse("a")= "e" + "d" + "c" + "b" + "a"= "edcba"边界条件：当字符串长度为0或1时，直接返回该字符串
代码实现：
def reverse_string(s): """ 递归实现字符串反转 知识点串联： - 第2章：字符串类型和索引 - 第5章：字符串切片 s[1:] 和 s[0] """ # 边界条件：空字符串或单字符 if len(s) <= 1: return s # 递归关系：最后一个字符 + 剩余字符串的反转 # s[-1] 获取最后一个字符（第2章字符串索引） # s[:-1] 获取除最后一个字符外的所有字符（第2章字符串切片） print(f" 分解: reverse('{s}') = '{s[-1]}' + reverse('{s[:-1]}')") result = s[-1] + reverse_string(s[:-1]) print(f" 回推: reverse('{s}') = '{result}'") return result# 测试print("=" * 50)print("字符串反转")print("=" * 50)test_strings = ["CK", "重庆", "Python", "递归"]for s in test_strings: print(f"\n原字符串: '{s}'") reversed_s = reverse_string(s) print(f"反转后: '{reversed_s}'")
5.4 案例4：判断回文字符串
问题描述：回文字符串是指正读和反读都相同的字符串，如”level”、“radar”、“重庆庆重”。
递归思路：
1. 如果字符串长度为0或1，是回文2. 如果首尾字符不同，不是回文3. 如果首尾字符相同，继续判断去掉首尾后的子串
代码实现：
def is_palindrome(s): """ 递归判断字符串是否为回文 知识点串联： - 第2章：字符串索引 s[0], s[-1] - 第2章：字符串切片 s[1:-1] - 第3章：逻辑判断 """ # 边界条件1：空字符串或单字符，是回文 if len(s) <= 1: return True # 边界条件2：首尾字符不同，不是回文 if s[0] != s[-1]: print(f"'{s}': 首尾字符 '{s[0]}' != '{s[-1]}'，不是回文") return False # 递归关系：首尾相同，判断子串 print(f"'{s}': 首尾字符相同 '{s[0]}'，继续判断 '{s[1:-1]}'") return is_palindrome(s[1:-1])# 测试print("=" * 50)print("判断回文字符串")print("=" * 50)test_cases = ["level", "hello", "radar", "重庆庆重", "CKKC", "Python"]for s in test_cases: result = is_palindrome(s) status = "是回文" if result else "不是回文" print(f"\n'{s}' {status}")
5.5 案例5：计算列表元素之和
问题描述：使用递归计算列表中所有元素的和。
递归思路：
sum([a, b, c, d, e]) = a + sum([b, c, d, e])= a + b + sum([c, d, e])= a + b + c + sum([d, e])= a + b + c + d + sum([e])= a + b + c + d + e + sum([])= a + b + c + d + e + 0边界条件：空列表的和为0
代码实现：
def list_sum(lst): """ 递归计算列表元素之和 知识点串联： - 第5章：列表的索引和切片 - lst[0] 获取第一个元素 - lst[1:] 获取除第一个元素外的子列表 """ # 边界条件：空列表 if not lst: # 等价于 len(lst) == 0 print(f" 边界: 空列表，返回0") return 0 # 递归关系：第一个元素 + 剩余元素的和 first = lst[0] rest = lst[1:] print(f" 分解: sum({lst}) = {first} + sum({rest})") partial = list_sum(rest) result = first + partial print(f" 回推: sum({lst}) = {first} + {partial} = {result}") return result# 测试print("=" * 50)print("计算列表元素之和")print("=" * 50)# 使用第5章的列表知识test_lists = [ [1, 2, 3, 4, 5], [10, 20, 30], [100], []]for lst in test_lists: print(f"\n列表: {lst}") if lst: # 非空列表才进行详细跟踪 total = list_sum(lst) else: total = 0 print(f" 空列表，和为0") print(f"最终结果: {total}") # 验证（使用第5章的sum函数） print(f"验证: {sum(lst)}")
5.6 案例6：求列表中的最大值
问题描述：使用递归找出列表中的最大值。
递归思路：
max([a, b, c, d]) = max(a, max([b, c, d]))= max(a, max(b, max([c, d])))= max(a, max(b, max(c, max([d]))))= max(a, max(b, max(c, d)))边界条件：单元素列表的最大值就是该元素
代码实现：
def list_max(lst): """ 递归找出列表中的最大值 知识点串联： - 第5章：列表操作 - 第3章：条件比较 """ # 边界条件：单元素列表 if len(lst) == 1: print(f" 边界: 单元素列表 [{lst[0]}]，最大值是 {lst[0]}") return lst[0] # 递归关系：比较第一个元素和剩余列表的最大值 first = lst[0] max_of_rest = list_max(lst[1:]) # 使用第3章的条件表达式 result = first if first > max_of_rest else max_of_rest print(f" 比较: max({first}, {max_of_rest}) = {result}") return result# 测试print("=" * 50)print("找出列表中的最大值")print("=" * 50)# CK大学某班级5门课程的成绩scores = [78, 92, 85, 67, 90]print(f"成绩列表: {scores}")print()maximum = list_max(scores)print(f"\n最高分: {maximum}")# 验证print(f"验证: max(scores) = {max(scores)}")
六、递归与循环的比较
6.1 相同点
·都可以用来解决重复性问题
·都需要设置终止条件（循环的条件判断 / 递归的边界条件）
·都可以实现相同的算法逻辑
6.2 不同点
特性 | 循环（Iteration） | 递归（Recursion） |
实现方式 | 使用for/while语句 | 函数调用自身 |
终止条件 | 循环条件为False | 到达边界条件 |
内存使用 | 固定，使用较少 | 较多，需要调用栈 |
代码简洁性 | 相对冗长 | 通常更简洁优雅 |
可读性 | 直观 | 需要理解递归思想 |
适用场景 | 简单的重复操作 | 问题可分解为子问题 |
风险 | 死循环 | 栈溢出 |
6.3 代码对比：阶乘计算
循环实现：
def factorial_iterative(n): """使用循环计算阶乘""" result = 1 # 使用第4章的for循环 for i in range(1, n + 1): result *= i return result
递归实现：
def factorial_recursive(n): """使用递归计算阶乘""" if n <= 1: return 1 return n * factorial_recursive(n - 1)
对比分析：
循环实现的特点：- 使用变量result保存中间结果- 显式控制循环变量i- 代码相对较长- 内存使用固定递归实现的特点：- 利用调用栈保存中间状态- 隐式控制通过参数n- 代码简洁优雅- 内存使用随n增大
七、递归的注意事项
7.1 必须有边界条件
# ❌ 错误示例：缺少边界条件def bad_recursion(n): return n + bad_recursion(n - 1) # 无限递归！# 这将导致：RecursionError: maximum recursion depth exceeded
7.2 递归参数必须向边界条件收敛
# ❌ 错误示例：参数不向边界收敛def bad_recursion2(n): if n == 0: return 0 return n + bad_recursion2(n + 1) # n越来越大，永远不会到达0！
7.3 注意递归深度限制
Python有默认的递归深度限制（通常是1000），可以通过以下方式查看和修改：
import sys# 查看当前递归深度限制print(f"当前递归深度限制: {sys.getrecursionlimit()}")# 修改递归深度限制（谨慎使用）sys.setrecursionlimit(2000)print(f"修改后递归深度限制: {sys.getrecursionlimit()}")
7.4 避免重复计算
斐波那契数列的朴素递归实现存在大量重复计算，可以使用记忆化技术优化：
# 使用字典缓存已计算的结果（第5章知识）fib_cache = {}def fibonacci_optimized(n): """优化的斐波那契数列计算（记忆化）""" # 检查缓存 if n in fib_cache: return fib_cache[n] # 边界条件 if n <= 1: return n # 计算并缓存结果 result = fibonacci_optimized(n - 1) + fibonacci_optimized(n - 2) fib_cache[n] = result return result# 对比测试print("=" * 50)print("优化前后的斐波那契计算对比")print("=" * 50)import time# 测试优化前start = time.time()result1 = fibonacci(30)time1 = time.time() - startprint(f"优化前: fib(30) = {result1}, 耗时: {time1:.4f}秒")# 测试优化后start = time.time()result2 = fibonacci_optimized(30)time2 = time.time() - startprint(f"优化后: fib(30) = {result2}, 耗时: {time2:.4f}秒")print(f"\n速度提升: {time1/time2:.0f}倍")
八、综合案例：CK大学图书馆书籍编号系统
让我们设计一个综合案例，运用本章和前面章节的知识：
"""CK大学图书馆书籍编号系统编号规则：- 书籍编号由分类码和序列号组成- 分类码使用递归生成（如A, AA, AAA, ...）- 序列号使用递归计算知识点串联：- 第2章：字符串操作- 第3章：条件判断- 第4章：循环（主程序中使用）- 第5章：列表和字典- 第6章：函数定义、参数传递、递归"""def generate_category_code(level, base="A"): """ 递归生成分类码 level=1 -> "A" level=2 -> "AA" level=3 -> "AAA" ... """ # 边界条件 if level == 1: return base # 递归关系：当前级别 = 基础字符 + 上一级别的编码 return base + generate_category_code(level - 1, base)def calculate_book_id(category_num, sequence): """ 计算书籍完整编号 格式：分类码-序列号（带前导零） """ category = generate_category_code(category_num) # 使用递归生成序列号（带前导零，至少4位） def format_sequence(n, width=4): """递归格式化序列号""" s = str(n) if len(s) >= width: return s # 递归添加前导零 return format_sequence(n, width - 1) + "0" if len(s) < width - 1 else "0" + s seq_str = format_sequence(sequence) return f"{category}-{seq_str}"def count_books_by_category(book_list, category): """ 递归统计某分类下的书籍数量 参数: book_list: 书籍列表，每个元素是字典（第5章知识） category: 要统计的分类码 """ # 边界条件：空列表 if not book_list: return 0 # 检查第一本书的分类（使用第5章字典访问） first_book = book_list[0] count = 1 if first_book["category"] == category else 0 # 递归统计剩余书籍 return count + count_books_by_category(book_list[1:], category)def list_all_categories(max_level): """列出所有分类码""" categories = [] for i in range(1, max_level + 1): categories.append(generate_category_code(i)) return categories# ============== 主程序 ==============print("=" * 60)print(" CK大学图书馆书籍编号系统")print("=" * 60)# 1. 演示生成分类码print("\n【1】生成分类码")print("-" * 40)for level in range(1, 6): code = generate_category_code(level) print(f"级别 {level}: {code}")# 2. 生成书籍编号print("\n【2】生成书籍编号")print("-" * 40)books = []for i in range(1, 6): book_id = calculate_book_id(2, i) books.append({ "id": book_id, "name": f"Python编程基础（第{i}版）", "category": "AA" }) print(f"书籍编号: {book_id}")# 添加一些其他分类的书籍books.append({"id": calculate_book_id(1, 1), "name": "计算机导论", "category": "A"})books.append({"id": calculate_book_id(3, 1), "name": "数据结构与算法", "category": "AAA"})print(f"\n图书馆共有 {len(books)} 本书")# 3. 统计分类print("\n【3】分类统计")print("-" * 40)for cat in ["A", "AA", "AAA"]: count = count_books_by_category(books, cat) print(f"分类 {cat}: {count} 本")# 4. 列出所有分类print("\n【4】所有分类码")print("-" * 40)all_cats = list_all_categories(5)print(f"分类列表: {all_cats}")print("\n" + "=" * 60)print("系统运行结束")print("=" * 60)
九、本节小结
9.1 递归的核心要点
┌─────────────────────────────────────────────────────────┐│ 递归函数编写指南 │├─────────────────────────────────────────────────────────┤│ ││ 1. 明确递归关系：如何用子问题定义原问题 ││ 例：n! = n × (n-1)! ││ ││ 2. 确定边界条件：何时停止递归 ││ 例：1! = 1 ││ ││ 3. 确保收敛：每次递归都向边界条件靠近 ││ 例：factorial(n) 调用 factorial(n-1)，n越来越小 ││ ││ 4. 验证正确性：用小的测试用例验证 ││ 例：验证 factorial(5) = 120 ││ │└─────────────────────────────────────────────────────────┘
9.2 递归的适用场景
✅ 适合使用递归： - 问题的定义本身就是递归的（如阶乘、斐波那契） - 数据结构是递归的（如树、链表） - 问题可以分解为相似的子问题（如分治算法）
❌ 不适合使用递归： - 问题本身没有递归结构 - 对性能要求很高（递归有函数调用开销） - 递归深度可能很大（容易栈溢出）
9.3 知识串联总结
章节 | 本节应用 |
第2章 | 数值运算、字符串操作作为递归的基础操作 |
第3章 | 分支结构实现边界条件判断 |
第4章 | 理解递归与循环的等价性 |
第5章 | 列表、字典作为递归函数的参数和数据结构 |
第6.1-6.3节 | 函数定义、参数传递、作用域 |
第6.4.1节 | 函数运行机制（调用栈）是递归的实现基础 |
🤖 AI辅助学习：用AI加深对递归的理解
一、为什么要用AI辅助学习编程？
在掌握了递归函数的基础知识后，我们可以利用AI工具来：
1.获得即时反馈：随时提问，立即得到解答
2.个性化学习：根据自己的理解程度调整问题难度
3.拓展思维：看到不同的解题思路和实现方式
4.实践练习：通过AI生成练习题和代码挑战
5.可视化理解：让AI帮助生成递归过程的图形化展示
二、如何与AI对话学习递归
2.1 基础提问模板
模板1：概念理解
请用通俗易懂的语言解释什么是[递归/边界条件/调用栈]，并举一个生活中的例子帮助我理解。
模板2：代码分析
请分析下面这段递归代码的执行过程：[粘贴你的代码]请逐行解释，并画出调用栈的变化过程。
模板3：错误排查
我的递归函数出现了[错误信息]，请帮我找出问题：[粘贴你的代码和错误信息]
模板4：优化建议
请帮我优化这段递归代码，使其[更高效/更易读/避免栈溢出]：[粘贴你的代码]
三、AI练习任务集
任务1：递归可视化——绘制递归树
学习目标：理解递归的调用过程
AI提示词：
请帮我写一个Python程序，使用turtle库（第6.5.2节学习的知识）绘制一棵递归分形树。要求：1. 树的深度可以通过参数控制2. 每层的树枝长度和角度有规律地变化3. 在代码中添加详细的注释，解释递归的过程4. 使用不同的颜色区分不同层级的树枝请给出完整的代码，并解释递归是如何在绘图过程中发挥作用的。
预期学习成果： - 理解递归如何生成复杂的图形 - 掌握turtle库的高级用法 - 直观感受递归的”分解-回推”过程
任务2：递归艺术——绘制科赫雪花
学习目标：用递归创造美丽的分形图案
AI提示词：
请帮我写一个Python程序，使用turtle库绘制科赫雪花（Koch Snowflake）。科赫雪花的绘制规则：1. 从一个等边三角形开始2. 将每条边分成三等份3. 在中间一段上向外画一个等边三角形4. 对新生成的每条边重复上述过程要求：1. 递归深度可以通过参数控制2. 使用循环绘制雪花的三个边3. 添加注释解释递归过程4. 让雪花填充颜色请给出完整的代码，并解释科赫曲线的递归原理。
预期学习成果： - 理解分形图形的递归生成原理 - 掌握递归与几何图形的结合 - 体验编程的艺术之美
任务3：递归动画——汉诺塔问题可视化
学习目标：理解经典递归问题的求解过程
AI提示词：
请帮我写一个Python程序，使用turtle库可视化汉诺塔问题的解决过程。汉诺塔规则：1. 有三根柱子A、B、C2. 有n个大小不同的盘子，初始都在A柱上，大盘在下，小盘在上3. 每次只能移动一个盘子4. 大盘不能压在小盘上5. 目标是把所有盘子从A柱移到C柱要求：1. 使用递归算法解决汉诺塔问题2. 用turtle动画展示每一步的移动过程3. 盘子数量可以通过参数设置（建议3-5个）4. 添加文字说明每一步的操作5. 在代码中详细注释递归的思路请给出完整的代码，并解释汉诺塔问题的递归解法。
预期学习成果： - 理解汉诺塔问题的递归解法 - 掌握递归与动画的结合 - 深入理解”分解问题”的思想
任务4：递归与爱心——绘制爱心图案
学习目标：用递归创造有趣的图案
AI提示词：
请帮我写一个Python程序，使用turtle库递归绘制爱心图案。要求：1. 使用数学公式绘制基本爱心形状2. 在爱心内部递归绘制更小的爱心3. 递归深度可以控制4. 使用粉色或红色系的颜色5. 在爱心旁边添加文字"CK大学"请给出完整的代码，并解释如何用递归创造这种嵌套效果。
预期学习成果： - 理解递归与数学公式的结合 - 掌握嵌套图形的绘制方法 - 增加编程的趣味性
任务5：递归实用工具——文件目录遍历
学习目标：理解递归在实际编程中的应用
AI提示词：
请帮我写一个Python程序，使用递归遍历指定目录下的所有文件和子目录。要求：1. 使用os模块的递归函数2. 按层级缩进显示目录结构3. 统计文件数量和目录数量4. 计算所有文件的总大小5. 可以指定要查找的文件类型（如只找.py文件）请给出完整的代码，并解释为什么这个问题适合用递归解决。
预期学习成果： - 理解递归在实际问题中的应用 - 掌握os模块的使用 - 理解树形结构的遍历
任务6：递归游戏——猜数字游戏的AI对手
学习目标：用递归实现二分查找算法
AI提示词：
请帮我写一个Python程序，实现一个猜数字游戏，其中电脑使用递归二分查找算法来猜测玩家想好的数字。游戏规则：1. 玩家在心里想一个1到100之间的数字2. 电脑使用二分查找递归猜测3. 玩家告诉电脑"大了"、"小了"或"猜对了"4. 电脑根据反馈调整猜测范围5. 记录猜测次数要求：1. 使用递归实现二分查找2. 显示每次猜测的范围和猜测值3. 限制最多猜测7次（因为2^7=128>100）4. 添加详细的注释解释二分查找的递归原理请给出完整的代码，并解释二分查找为什么可以用递归实现。
预期学习成果： - 理解二分查找算法的递归实现 - 掌握递归与算法的结合 - 理解递归的效率优势
任务7：递归与数学——计算组合数C(n,k)
学习目标：用递归解决数学问题
AI提示词：
请帮我写一个Python程序，使用递归计算组合数C(n,k)（从n个元素中选k个的组合数）。数学知识：C(n,k) = C(n-1,k-1) + C(n-1,k)（帕斯卡公式）边界条件：C(n,0) = C(n,n) = 1要求：1. 使用递归实现组合数计算2. 使用记忆化技术优化性能3. 打印出C(10,k) for k in range(11)的结果4. 与数学公式n!/(k!(n-k)!)的结果进行对比验证5. 添加详细注释解释递归关系和边界条件请给出完整的代码，并解释帕斯卡公式的递归原理。
预期学习成果： - 理解数学公式的递归表达 - 掌握记忆化技术的应用 - 加深对组合数学的理解
任务8：递归与字符串——生成所有排列
学习目标：用递归生成排列组合
AI提示词：
请帮我写一个Python程序，使用递归生成一个字符串的所有排列。例如："ABC"的所有排列是："ABC", "ACB", "BAC", "BCA", "CAB", "CBA"递归思路：1. 固定第一个字符，递归生成剩余字符的排列2. 对每个位置，依次交换字符到首位3. 边界条件：当字符串长度为1时，返回该字符串要求：1. 使用递归实现排列生成2. 使用列表存储所有排列结果3. 去除重复的排列（如果有重复字符）4. 统计排列总数5. 添加详细注释解释递归过程请给出完整的代码，并解释如何用递归生成所有排列。
预期学习成果： - 理解排列生成的递归算法 - 掌握递归与列表操作的结合 - 理解回溯算法的雏形
10个月宝宝每天需要喝多少奶粉？
