py编程基础及导论 9

第6章函数函数定义·参数传递·递归·统计计算面向师范生的Python编程导论本章概述2第6章函数本章将学习Python中函数的定义、调用与递归6.1函数入门内置函数、def定义、参数与返回值、函数调用、统计计算6.2函数进阶递归概念、阶乘递归、最大公约数、斐波那契数列本章学习目标4第6章函数知识目标理解函数的概念与作用掌握def关键字定义函数理解形参与实参的区别掌握return语句的使用理解函数调用过程理解递归的基本原理掌握基本情况与递归步骤能力目标能够定义和调用自定义函数能够设计多参数函数能够计算平均数、中位数、众数能够用递归实现阶乘能够用递归求最大公约数能够优化递归效率能够对比递归与循环本章课时安排（4课时）6第6章函数课时教学内容重点/难点活动设计第1课时函数定义、def关键字、return语句函数签名与函数体概念讲解+Shell练习第2课时参数传递、函数调用过程、统计函数形参与实参、可变类型编程实践+任务驱动第3课时递归概念、阶乘递归、最大公约数基本情况与递归步骤递归推演+编程实践第4课时斐波那契数列、递归优化、综合应用递归效率与记忆化综合练习+测试提示建议每课时预留15分钟进行编程实践，让学生在动手编写代码中掌握函数的定义与调用。6.1函数入门理解函数概念，掌握def定义函数、参数传递与返回值，能够设计统计计算函数6.1.1内置函数9第6章函数·6.1函数入门什么是函数？函数是具有特定功能的代码片段，其允许程序在不同代码片段之间切换，也为代码复用提供了有效的机制。函数是对功能的一种抽象，我们无须关心其具体实现，只需要了解输入参数和返回结果即可。内置函数print()—输出数据input()—读取输入range()—生成数列int()/float()/str()—类型转换type()—查看类型len()—计算长度函数的特点具有特定功能的代码片段可以实现代码复用是对功能的抽象通过参数接收输入通过返回值输出结果简化程序结构Python常用内置函数11第6章函数·6.1函数入门函数名功能示例返回值print()输出数据print('Hello')Noneinput()读取用户输入n=input()字符串range()生成整数数列range(1,10,2)range对象int()转换为整数int('100')intfloat()转换为浮点数float('3.14')floatstr()转换为字符串str(100)strtype()查看类型type(n)type对象len()计算长度len([1,2,3])intsorted()排序并返回新列表sorted([3,1,2])listmax()/min()求最大/最小值max([1,5,3])元素值提示Python3提供了丰富的内置函数，无需导入即可使用。访问Python官方文档可以查看所有内置函数。内置函数使用示例13第6章函数·6.1函数入门built_in.py#print()函数—根据参数不同，输出效果不同print("HelloWorld")print(3.14)print(1+2)#input()函数—读取键盘输入，返回字符串name=input("请输入姓名：")#range()函数—三个参数：start,stop,stepforiin

range(1,10,2):

print(i)#type()和len()函数nums=[1,2,3,4,5]print(type(nums))#<class'list'>print(len(nums))#5函数是对功能的抽象15第6章函数·6.1函数入门函数的抽象性虽然函数的本质是一段完成具体功能的代码，但是我们无须关心其具体实现，只需要了解输入参数和返回结果即可。这就是函数对功能的抽象。输入参数→函数处理(无需关心)→返回结果range()的例子输入：start,stop,step我们不知道内部如何实现但知道返回一个整数数列这就是函数的抽象自定义函数的意义将重复代码封装为函数提高代码复用性使程序结构更清晰便于维护和调试6.1.2函数定义17第6章函数·6.1函数入门为什么需要自定义函数？除使用内置函数外，编程时通常需要使用自定义函数来实现某些功能。例如，输入一个整数n，求出1到n的和。我们可以设计一个函数来完成这个任务。函数命名规则使用英文字母、数字、下画线不能以数字开头不能使用Python关键字命名应表达函数的功能例如：series_sum表示数列求和def关键字def是define（定义）的缩写在程序中设计函数叫作定义函数def后跟函数名和参数以英文冒号结尾缩进的代码是函数体代码6.1：数列求和函数19第6章函数·6.1函数入门代码6.1#定义求和函数defseries_sum(n):s=0

foriin

range(1,n+1):s=s+i

returns#输入数据print("请输入一个正整数n:")n=int(input())#调用函数Sn=series_sum(n)#输出结果print(f"1加到{n}的和={Sn}")运行结果请输入一个正整数n:1001加到100的和=5050函数定义的结构21第6章函数·6.1函数入门函数定义分为两个部分：函数签名和函数体def关键字函数名(名称)参数(括号内)←——————————————————→函数签名函数体(缩进的代码)·实现函数功能的代码·使用局部变量·可以包含return语句返回值提示defseries_sum(n):这一行是函数签名，下面的缩进代码是函数体。函数签名（Signature）23第6章函数·6.1函数入门函数签名函数签名以def关键字开头，包括函数名称（functionname）和函数的形式参数（parameters）。通过函数签名即可实现函数调用。函数签名结构defseries_sum(n):|||──形式参数(parameter)───────────函数名称(functionname)def────────define关键字#通过函数签名即可调用result=series_sum(100)例如range()函数，我们可以通过其名称及形式参数实现调用，无须关注函数体内部如何实现。函数体与局部变量25第6章函数·6.1函数入门函数体(FunctionBody)包含实现函数功能的代码代码中通常会用到局部变量局部变量仅在函数体中有效不会影响函数体外的代码函数体代码需要缩进可以调用其他函数局部变量(LocalVariables)在函数体中定义的变量仅在函数体范围内有效函数外部无法访问不影响函数外的同名变量函数结束后被销毁不同函数可使用同名局部变量return语句27第6章函数·6.1函数入门return语句的作用return语句的作用是返回值。函数可以理解为一个复杂的表达式，因为最终它会变成一个值，即返回值。调用函数后，可以通过赋值语句将返回值赋给变量。return_example.py#return语句的基本用法defseries_sum(n):s=0

foriin

range(1,n+1):s=s+i

returns#返回s的值#调用函数，返回值赋给变量Sn=series_sum(100)#Sn=5050print(Sn)#输出5050注意函数可以没有返回值。如果没有return语句，函数执行完毕后返回None。6.1.3函数调用过程29第6章函数·6.1函数入门形式参数与实际参数定义函数时设定的是形式参数（parameters），其变量名在函数体代码中发挥效果。调用函数时输入的是实际参数（arguments），实际参数的值会传递给形式参数，然后运行函数体的代码，最后获得返回值。形式参数(Parameters)定义函数时设定的参数变量名在函数体中使用只是一个占位符调用时才获得实际值例如：deff(a1,d,n)实际参数(Arguments)调用函数时传入的参数变量名可以是任意的与形式参数名称无关值会传递给形式参数例如：series_sum(a,b,c)参数传递示意图31第6章函数·6.1函数入门参数传递#定义函数—形式参数为a1,d,ndefseries_sum(a1,d,n):an=a1+(n-1)*dSn=1/2*n*(a1+an)

returnSn#调用函数—实际参数为a,b,ca=2b=3c=3s=series_sum(a,b,c)#a的值传给a1,b的值传给d,c的值传给n实际参数a=2,b=3,c=3→值传递a→a1,b→d,c→n→形式参数a1=2,d=3,n=3任务6.1：等差数列求和函数33第6章函数·6.1函数入门任务6.1请根据等差数列求和公式，设计一个数列求和函数，函数的参数有首项值、公差、项数n，返回值为前n项的和。Sn=(n/2)*(a1+an)an=a1+(n-1)*d解题思路首先设计函数series_sum(a1,d,n)，根据求和公式计算前n项的和Sn。先计算第n项的值an=a1+(n-1)*d，再根据公式Sn=(1/2)*n*(a1+an)计算求和结果。提示函数参数增加至三个：首项a1、公差d、项数n。调用时实际参数变量名可以与形式参数不同。代码6.2：等差数列求和35第6章函数·6.1函数入门代码6.2#定义求和函数defseries_sum(a1,d,n):#计算anan=a1+(n-1)*d#前n项和Sn=1/2*n*(a1+an)#返回求和结果

returnSn#输入数据print("请输入等差数列的首项值:")a=int(input())print("请输入等差数列的公差:")b=int(input())print("请输入要求和的项数:")c=int(input())#调用函数s=series_sum(a,b,c)#输出结果print(f"该数列前{c}项的和={s}")运行结果请输入等差数列的首项值:2请输入等差数列的公差:3请输入要求和的项数:3该数列前3项的和=15.0函数调用过程37第6章函数·6.1函数入门函数调用的执行流程当调用函数时，代码回到函数定义部分。函数代码执行完成后，执行过程返回调用处，将返回值赋给变量。1.主程序执行到函数调用→2.跳转到函数定义→3.实参值传递给形参→4.执行函数体代码→5.return返回值关键理解调用函数时，代码执行会进行跳转，跳到函数定义处执行函数执行完毕后，代码会回到先前调用函数的位置继续执行实际参数的值传递给形式参数，变量名可以不同函数可以理解为一个复杂的表达式，最终变成返回值函数之间的调用39第6章函数·6.1函数入门函数间可以相互调用代码中可以包含多个函数，函数之间也可以相互调用。例如，将计算数列第n项的值设计为一个函数，在求和函数中调用它。series_sum()调用calc_an()→calc_an()计算第n项→返回an值给series_sum→series_sum()计算并返回Sn代码6.3：函数间调用41第6章函数·6.1函数入门代码6.3#定义求和函数defseries_sum(a1,d,n):Sn=1/2*n*(a1+calc_an(a1,d,n))

returnSn#计算第n项的函数defcalc_an(a1,d,n):an=a1+(n-1)*d

returnan#输入数据并调用a=int(input())b=int(input())c=int(input())s=series_sum(a,b,c)print(f"该数列前{c}项的和={s}")运行结果输入2,3,3，输出：该数列前3项的和=15.0（与代码6.2结果相同）形参与实参对比43第6章函数·6.1函数入门对比项形式参数(Parameters)实际参数(Arguments)出现位置函数定义中函数调用中变量名在函数体中使用可以是任意变量名关系接收实际参数的值将值传递给形式参数示例deff(a1,d,n)f(a,b,c)是否需要同名不需要不需要命名要求应表达参数含义调用时自行决定注意调用函数时，实际参数的变量名可以是任意的，与函数定义中的形式参数名称无关！代码6.2中用a,b,c调用series_sum(a1,d,n)不会报错。6.1.4计算统计数据45第6章函数·6.1函数入门用函数解决统计问题在分析数据时，经常需要计算一些统计数据，最常见的是中心趋势度量，包括平均数、中位数和众数。此外还有离散度度量，如标准差。我们将设计函数来计算这些统计指标。1平均数(mean)所有数据的和除以数据个数2中位数(median)排序后中间位置的数3众数(mode)出现次数最多的数4标准差(standarddeviation)衡量数据的离散程度学生成绩数据47第6章函数·6.1函数入门测试数据给定一个列表，包含15个整数表示学生的成绩。我们将设计函数来计算这些成绩的平均数、中位数、众数和标准差。数据#学生成绩列表scores=[60,66,88,81,90,95,70,71,75,75,81,69,75,90,78]print(f"成绩列表：{scores}，共{len(scores)}人")统计目标任务6.2：设计函数计算平均数mean()任务6.3：设计函数计算中位数median()任务6.4：设计函数计算众数mode()任务6.5：设计函数计算标准差standard_dev()任务6.2：计算平均数49第6章函数·6.1函数入门任务6.2设计一个函数，计算列表中成绩的平均数。平均数的计算方法平均数=所有数据的和/数据个数。对列表中的数据求和，再除以数据个数，即可求得平均数。思路#计算公式#avg=total/count#total:所有成绩的和#count:成绩的个数(len(nums))提示英文单词mean表示平均数、均值，因此函数命名为mean()。代码6.4：mean()函数51第6章函数·6.1函数入门代码6.4#定义求平均数函数defmean(nums):total=0

forninnums:total+=n#等价于total=total+navg=total/len(nums)

returnavg#成绩列表scores=[60,66,88,81,90,95,70,71,75,75,81,69,75,90,78]print(f"成绩列表：{scores}，共{len(scores)}人")#求平均数avg=mean(scores)print(f"平均分为：{avg}")运行结果成绩列表：[60,66,88,81,90,95,70,71,75,75,81,69,75,90,78]，共15人平均分为：77.6+=赋值运算符53第6章函数·6.1函数入门复合赋值运算符代码6.4中的total+=n是赋值语句total=total+n的简写形式，+=是一种复合赋值运算符。运算符等价形式示例说明+=a=a+btotal+=n加法赋值-=a=a-bcount-=1减法赋值*=a=a*bp*=i乘法赋值/=a=a/bs/=2除法赋值//=a=a//bn//=10取整除赋值%=a=a%br%=2取余赋值提示复合赋值运算符使代码更简洁。total+=n等价于total=total+n。任务6.3：计算中位数55第6章函数·6.1函数入门任务6.3设计一个函数，计算列表中成绩的中位数。中位数的定义排序后数列中间位置的数如果数据个数是奇数：中位数=中间位置的数如果数据个数是偶数：中位数=中间两个数的均值计算步骤1.对列表进行排序2.判断列表长度的奇偶性3.奇数：取中间位置mid=length//24.偶数：取中间两数的均值(nums[mid-1]+nums[mid])/2代码6.5：median()函数57第6章函数·6.1函数入门代码6.5#定义求中位数函数defmedian(nums):nums.sort()#排序length=len(nums)

iflength%2==1:#奇数长度mid=length//2median=nums[mid]

else:#偶数长度right_mid=length//2left_mid=right_mid-1median=(nums[left_mid]+nums[right_mid])/2

returnmedianscores=[60,66,88,81,90,95,70,71,75,75,81,69,75,90,78]mid=median(scores)print(f"中位数为：{mid}")运行结果中位数为：75列表传值问题59第6章函数·6.1函数入门注意运行代码6.5后发现：原始成绩列表scores也被排序了！nums.sort()影响了函数外的scores。原因分析列表是可变类型，作为参数传入函数时，形式参数会指向同一个列表。函数对列表排序后，外部的scores也会同时发生变化。而数字、字符串等不可变类型的参数一旦被修改，就会指向新的内存空间，函数外的原始值不会改变。数据类型可变性作为参数传入函数时int,float,str不可变类型修改后不影响原始值list,dict可变类型修改后会影响原始值代码6.6：复制列表61第6章函数·6.1函数入门解决方案为了避免原始列表被改变，只需要在函数中复制列表，然后对其进行操作。代码6.6#复制列表的两种方法a=[1,2,3]#方法1：使用copy()方法b=a.copy()#方法2：使用切片运算符，截取所有元素c=a[:]#修改b和c不会影响ab.append(4)c.append(5)print(a)#[1,2,3]print(b)#[1,2,3,4]print(c)#[1,2,3,5]提示在函数中复制列表后再操作，就不会影响原始数据。这是处理可变类型参数的重要技巧。代码6.7：优化median()函数63第6章函数·6.1函数入门代码6.7#定义求中位数函数（优化版）defmedian(nums):nums=nums.copy()#复制列表nums.sort()#排序

print(f"排序成绩：{nums}")length=len(nums)

iflength%2==1:mid=length//2median=nums[mid]

else:right_mid=length//2left_mid=right_mid-1median=(nums[left_mid]+nums[right_mid])/2

returnmedianscores=[60,66,88,81,90,95,70,71,75,75,81,69,75,90,78]mid=median(scores)print(f"原始成绩：{scores}")print(f"中位数为：{mid}")运行结果排序成绩：[60,66,69,70,71,75,75,75,78,81,81,88,90,90,95]原始成绩：[60,66,88,81,90,95,70,71,75,75,81,69,75,90,78]中位数为：75sorted()函数优化65第6章函数·6.1函数入门sorted()函数Python内置的sorted()函数返回一个新的已完成排序的列表。使用该函数可以进一步简化代码，合并执行复制与排序操作。对比#nums.sort()vssorted(nums)#sort()—原地排序，修改原列表#sorted()—返回新的排序列表，不影响原列表nums=[3,1,2]a=sorted(nums)#a=[1,2,3],nums不变nums.sort()#nums变为[1,2,3]sorted()的优势sorted(nums)等价于先复制列表再排序，一行代码完成两个操作，代码更简洁。代码6.8：使用sorted()优化67第6章函数·6.1函数入门代码6.8#定义求中位数函数（使用sorted优化）defmedian(nums):nums=sorted(nums)#排序并复制length=len(nums)

iflength%2==1:mid=length//2median=nums[mid]

else:right_mid=length//2left_mid=right_mid-1median=(nums[left_mid]+nums[right_mid])/2

returnmedian#奇数个数据scores=[60,66,88,81,90,95,70,71,75,75,81,69,75,90,78]mid=median(scores)print(f"中位数为：{mid}")#偶数个数据scores=[60,66,88,81,90,95,70,71]mid=median(scores)print(f"中位数为：{mid}")任务6.4：计算众数69第6章函数·6.1函数入门任务6.4设计一个函数，计算列表中成绩的众数。众数的定义众数（mode）是指数据集中出现次数最多的数，数据集中可能有多个众数。计算思路1.使用dict字典类型记录每个分数出现的次数2.分数作为key，出现次数作为value3.遍历字典，找出出现次数最多的分数4.注意：可能有多个众数，需要返回列表代码6.9：mode()函数（基础版）71第6章函数·6.1函数入门代码6.9#定义求众数函数defmode(nums):counts={}#创建记录出现次数的字典

foriteminnums:

ifitemincounts:counts[item]+=1

else:counts[item]=1#找出出现次数最多的数据max_count=0result=0

forkeyincounts:

ifcounts[key]>max_count:max_count=counts[key]result=key

returnresultscores=[60,66,88,81,90,95,70,71,75,75,81,69,75,90,78]m=mode(scores)print(f"众数为：{m}")注意此函数只能返回一个众数。当有多个众数时，需要优化。代码6.10：mode()函数（优化版）73第6章函数·6.1函数入门代码6.10#定义求众数函数（优化版，返回众数列表）defmode(nums):counts={}

foriteminnums:

ifitemincounts:counts[item]+=1

else:counts[item]=1#找出最高频率feq=counts.values()max_count=max(feq)#找出所有众数mode_list=[]

forkeyincounts:

ifcounts[key]==max_count:mode_list.append(key)

returnmode_list#测试scores1=[60,66,88,81,90,95,70,71,75,75,81,69,75,90,78]scores2=[81,90,95,70,71,75,75,81,69,75,90,78,81,90]print(f"众数：{mode(scores1)}")#[75]print(f"众数：{mode(scores2)}")#[81,90,75]任务6.5：计算标准差75第6章函数·6.1函数入门任务6.5设计一个函数，计算列表中成绩的标准差。标准差的计算公式标准差（standarddeviation）衡量数据的离散程度。计算步骤：先求平均数，再计算每个数据与平均数的差的平方，求和后除以(n-1)，最后开平方根。公式#标准差公式#sd=sqrt(sum((xi-avg)^2)/(n-1))##其中：#xi—每个数据#avg—平均数#n—数据个数代码6.11：standard_dev()函数77第6章函数·6.1函数入门代码6.11#定义求标准差函数defstandard_dev(nums):avg=mean(nums)total=0

forninnums:diff=n-avgdiff_squared=diff**2total+=diff_squaredsd=(total/(len(nums)-1))**0.5

returnsd#定义求平均数函数defmean(nums):total=0

forninnums:total+=navg=total/len(nums)

returnavg#测试scores=[60,66,88,81,90,95,70,71,75,75,81,69,75,90,78]avg=mean(scores)sd=standard_dev(scores)print(f"成绩均分为：{avg}，标准差：{sd:.3f}")运行结果成绩均分为：77.6，标准差：9.934统计函数总结79第6章函数·6.1函数入门函数名功能参数返回值对应Excel函数mean()计算平均数列表floatAVERAGE()median()计算中位数列表float/intMEDIAN()mode()计算众数列表列表MODE()standard_dev()计算标准差列表floatSTDEV()提示这些函数在Excel中也有对应函数。请对比我们设计的函数与Excel中相关函数的计算结果是否一致。设计统计函数的要点函数参数为列表类型，包含一组数据平均数：求和后除以个数中位数：需先排序，注意奇偶长度众数：用字典统计频率，注意多个众数的情况标准差：需调用mean()函数，注意函数间调用可变类型与不可变类型81第6章函数·6.1函数入门类型可变性作为函数参数修改后是否影响原始值示例int不可变值传递不影响n=100float不可变值传递不影响pi=3.14str不可变值传递不影响s='Hello'list可变引用传递影响!nums=[1,2,3]dict可变引用传递影响!d={'a':1}注意列表和字典是可变类型！作为函数参数时，函数内的修改会影响原始数据。解决方法：在函数中用copy()或sorted()复制后再操作。记忆口诀不可变类型（数字、字符串）传入函数→修改不影响原值可变类型（列表、字典）传入函数→修改会影响原值！需要复制！6.1小结：函数入门函数是具有特定功能的代码片段，实现了功能的抽象和代码复用def关键字用于定义函数，包括函数签名和函数体函数签名包括函数名和形式参数，通过签名即可调用函数return语句返回函数的值，函数可以理解为复杂的表达式局部变量仅在函数体中有效，不影响外部代码形式参数是定义时的参数，实际参数是调用时的参数实际参数的值传递给形式参数，变量名可以不同函数之间可以相互调用可变类型（列表、字典）作为参数时需注意复制设计了mean()、median()、mode()、standard_dev()统计函数6.2函数进阶理解递归的概念，掌握基本情况与递归步骤，能够用递归实现阶乘、最大公约数和斐波那契数列6.2.1递归85第6章函数·6.2函数进阶什么是递归？在使用函数的过程中，我们可以在一个函数中调用另外一个函数，还可以在函数中调用自身，函数调用自身的情况称为递归（recursion）。递归的优势程序通常更容易理解代码相对简洁自然表达递归问题如阶乘、斐波那契等递归的挑战需要对问题有深入理解可能出现重复计算效率可能低于循环需要注意终止条件递归的引入：阶乘问题87第6章函数·6.2函数进阶思考：如何设计一个计算阶乘的函数？n!表示n的阶乘，计算公式为：n!=n×(n-1)×(n-2)×...×2×1方法1：循环实现使用for循环实现累乘p=1foriinrange(1,n+1):p*=i不需要递归直接迭代计算方法2：递归实现n!=n×(n-1)!当n>1时递归调用当n=1时返回1函数调用自身代码更简洁符合数学定义任务6.6：计算阶乘89第6章函数·6.2函数进阶任务6.6n!表示n的阶乘，请设计一个函数计算n的阶乘。阶乘公式：n!=n×(n-1)×(n-2)×...×2×1阶乘的数学定义1!=1n!=n×(n-1)!(当n>1时)递归思路当n>1时，n的阶乘可以看作(n-1)的阶乘再乘以n。以此类推，(n-1)的阶乘又可以看作(n-2)!乘以(n-1)，直到n为1。代码6.12：循环实现阶乘91第6章函数·6.2函数进阶使用循环实现该程序使用for循环实现累乘，从而计算n的阶乘，这里并没有使用递归算法。代码6.12#定义阶乘函数（循环版）deffactorial(n):p=1

foriin

range(1,n+1):p*=i

returnp#调用函数n=6p=factorial(n)print(f"{n}!={p}")运行结果6!=720递归思路详解93第6章函数·6.2函数进阶递归的数学基础根据阶乘的计算公式，当n>1时，n!=n×(n-1)!6!=6×5!→5!=5×4!→4!=4×3!→...直到1!递归的两个关键部分1.基本情况（basecase）：递归的终止条件，如n=1时直接返回12.递归步骤（reductionstep）：函数调用自身的部分，如returnn*factorial(n-1)递归步骤中的参数值必须最终收敛到基本情况代码6.13：递归实现阶乘95第6章函数·6.2函数进阶代码6.13#定义递归阶乘函数deffactorial(n):

ifn==1:#基本情况

return

1

else:#递归步骤

returnn*factorial(n-1)#调用函数n=6p=factorial(n)print(f"{n}!={p}")运行结果6!=720提示递归方式不使用循环语句，只用少量程序描述多次重复计算，代码更简洁。6.2.2最大公约数97第6章函数·6.2函数进阶欧几里得算法关于最大公约数（greatestcommondivisor,GCD），有一个著名的古老算法叫作欧几里得算法，也叫作辗转相除法。其核心思想非常符合递归思路。算法描述当p>q时，p和q的最大公约数等于q和p%q的最大公约数即GCD(p,q)=GCD(q,p%q)当q为0时，p即为最大公约数递归特征基本情况：q==0时返回p递归步骤：GCD(q,p%q)参数逐渐收敛到基本情况p%q必然小于q最终q会变为0欧几里得算法的历史99第6章函数·6.2函数进阶古老的智慧欧几里得算法是最古老的算法之一，最早记载于古希腊数学家欧几里得的《几何原本》（约公元前300年）。至今仍被广泛使用，是数论中的经典算法。欧几里得《几何原本》→辗转相除求GCD→现代计算机依然使用算法的核心思想GCD(p,q)=GCD(q,p%q)—将大问题转化为小问题当q=0时，p就是答案—这就是基本情况任务6.7：求最大公约数101第6章函数·6.2函数进阶任务6.7设计一个函数，根据欧几里得算法求两个数的最大公约数。根据欧几里得算法，当p>q时，p和q的最大公约数等于q和p%q的最大公约数。算法分析从欧几里得算法的描述来看，其非常符合递归思路。基本情况是q为0时返回p，递归步骤是GCD(q,p%q)。基本情况q==0时返回p此时p就是最大公约数递归步骤q!=0时返回GCD(q,p%q)参数逐渐收敛辗转相除法示例：GCD(18,27)103第6章函数·6.2函数进阶以m=18,n=27为例，展示辗转相除法的执行过程步骤pqp%q操作1182718GCD(18,27)→GCD(27,18)227189GCD(27,18)→GCD(18,9)31890GCD(18,9)→GCD(9,0)490-q=0，返回p=9提示注意：第一步中18<27，但18%27=18，相当于自动交换了p和q的位置。最终结果：18和27的最大公约数为9代码6.14：递归求最大公约数105第6章函数·6.2函数进阶代码6.14#定义求最大公约数函数defGCD(p,q):

ifq==0:#基本情况

returnp

else:#递归步骤

returnGCD(q,p%q)#调用函数m=18n=27g=GCD(m,n)print(f"{m}和{n}的最大公约数为{g}")运行结果18和27的最大公约数为9提示代码非常简洁！递归函数的基本情况是q为0，即上一次递归步骤中p%q为0，此时q（即基本情况中的p）就是最大公约数。GCD递归执行过程分析107第6章函数·6.2函数进阶递归调用链以GCD(18,27)为例，追踪递归的完整执行过程：GCD(18,27)q!=0返回GCD(27,18%27)→GCD(27,18)q!=0返回GCD(18,27%18)→GCD(18,9)q!=0返回GCD(9,18%9)→GCD(9,0)q==0返回9关键观察第一步：18%27=18（因为18<27），相当于p和q自动交换了位置后续步骤：每次p%q都在减小，必然最终收敛到q=0基本情况触发时，p的值就是最大公约数p<q时的自动交换机制109第6章函数·6.2函数进阶为什么不需要判断p和q的大小？在代码6.14中，我们并没有判断p与q的大小。在案例中m小于n，程序仍然能够正常运行。原因是在p小于q时，p%q等于p，因此在执行递归步骤时，相当于p与q自动交换了位置。自动交换#当p<q时：#p%q=p(因为p除以q的商为0，余数为p)#GCD(p,q)=GCD(q,p%q)=GCD(q,p)#相当于自动交换了p和q#示例：GCD(18,27)#18%27=18#GCD(18,27)=GCD(27,18)#自动交换！提示这是取余运算的一个巧妙特性：当被除数小于除数时，余数等于被除数本身。最大公约数的应用：约分111第6章函数·6.2函数进阶GCD的实际应用最大公约数的一个重要应用是分数的约分。将分子和分母同时除以它们的最大公约数，就可以得到最简分数。约分应用#利用GCD进行约分defGCD(p,q):

ifq==0:

returnp

else:

returnGCD(q,p%q)#约分函数defreduce_fraction(num,den):g=GCD(num,den)

returnnum//g,den//g#测试：将18/27约分n,d=reduce_fraction(18,27)print(f"18/27约分后为{n}/{d}")运行结果18/27约分后为2/3代码6.15：循环实现最大公约数113第6章函数·6.2函数进阶不使用递归的实现我们可以根据欧几里得算法的步骤，利用while循环来实现算法。使用while循环的原因是：我们无法预测循环的次数，需要根据条件来终止循环。代码6.15#定义求最大公约数的函数defGCD(p,q):

whilep%q!=0:t=p%q#中间变量保存余数p=q#p变为qq=t#q变为余数

returnq#调用函数m=18n=27g=GCD(m,n)print(f"{m}和{n}的最大公约数为{g}")运行结果18和27的最大公约数为9while循环实现详解115第6章函数·6.2函数进阶交换变量的技巧因为要交换p和q的值，我们需要引入中间变量t，实现这种交换。这是编程中常见的变量交换模式。循环过程#变量交换过程（以p=18,q=27为例）#第1次循环：p=18,q=27#t=18%27=18#p=27,q=18#第2次循环：p=27,q=18#t=27%18=9#p=18,q=9#第3次循环：p=18,q=9#18%9=0，退出循环#返回q=9提示中间变量t是交换两个变量值的经典方法：t=a;a=b;b=t。Python中还支持a,b=b,a的写法。任务6.8：for循环求最大公约数117第6章函数·6.2函数进阶任务6.8设计一个函数，使用for循环求两个数的最大公约数。思路提示从较小数开始倒序遍历检查是否能同时整除p和q第一个满足条件的数即为GCDforiinrange(min(p,q),0,-1):ifp%i==0andq%i==0:returni方法对比递归：代码简洁，思路清晰while循环：无需预测循环次数for循环：思路最直接三种方法结果相同效率各有优劣GCD三种实现方法对比119第6章函数·6.2函数进阶方法代码量可读性效率特点递归（代码6.14）最短高中等符合数学定义，代码简洁while循环（代码6.15）中等中较高需要中间变量交换for循环（任务6.8）中等高较低思路直接，但遍历次数多选择建议递归方法最简洁，适合教学和理解算法思想while循环效率较高，适合实际应用for循环思路最直接，但效率最低三种方法都基于欧几里得算法的核心思想注意本节主要利用递归与循环迭代的方法求解最大公约数，请思考是否还有其他方法。6.2.2小结：最大公约数121第6章函数·6.2函数进阶欧几里得算法（辗转相除法）是求最大公约数的经典算法核心公式：GCD(p,q)=GCD(q,p%q)基本情况：当q=0时，p即为最大公约数递归步骤：GCD(q,p%q)，参数逐渐收敛当p<q时，p%q=p，自动交换p和q可用while循环替代递归，避免递归深度问题GCD的应用：约分、求最小公倍数等提示递归和循环是解决同一问题的两种不同思路，各有优劣。在实际编程中应根据具体情况选择。6.2.3斐波那契数列123第6章函数·6.2函数进阶斐波那契数列斐波那契数列是由意大利人斐波那契（Fibonacci）最先开始研究的一个数列，最初用来描述兔子的繁殖数量。这个数列在数学、自然科学和计算机科学中都有广泛应用。数列特点前两项为F(0)=0,F(1)=1后续每项等于前两项之和F(n)=F(n-1)+F(n-2)非常符合递归思路有两种基本情况应用领域兔子繁殖模型植物叶序排列黄金分割比例算法效率分析金融技术分析斐波那契与兔子繁殖问题125第6章函数·6.2函数进阶兔子繁殖模型假设一对刚出生的兔子，一个月后成熟，再一个月后开始每月生一对小兔。新生的小兔也遵循同样的规律。如果不考虑死亡，每个月兔子的总对数就是斐波那契数列。月份成熟兔子对数新生兔子对数总对数00111101211232134325553868513提示每个月的总对数就是斐波那契数列：1,1,2,3,5,8,13,21,34,55...斐波那契数列的数学定义127第6章函数·6.2函数进阶数学定义F(0)=0F(1)=1F(n)=F(n-1)+F(n-2)（当n>=2时）两种基本情况F(0)=0—第一种基本情况F(1)=1—第二种基本情况两种基本情况确保递归能终止缺少任一种都会导致错误递归步骤F(n)=F(n-1)+F(n-2)参数n逐次减小必然收敛到基本情况符合递归程序的设计要求斐波那契数列前10项129第6章函数·6.2函数进阶斐波那契数列前10项的值为：1,1,2,3,5,8,13,21,34,55...项数nF(n)计算过程00基本情况11基本情况21F(1)+F(0)=1+0=132F(2)+F(1)=1+1=243F(3)+F(2)=2+1=355F(4)+F(3)=3+2=568F(5)+F(4)=5+3=8713F(6)+F(5)=8+5=13821F(7)+F(6)=13+8=21934F(8)+F(7)=21+13=34斐波那契数列在自然界中131第6章函数·6.2函数进阶自然界中的斐波那契斐波那契数列不仅是一个数学游戏，它在自然界中广泛存在，体现了数学与自然的深刻联系。植物中的斐波那契向日葵种子的螺旋排列松果的鳞片排列菠萝表面的纹理花瓣数目常为斐波那契数树叶在茎上的排列角度黄金分割与斐波那契相邻两项的比值趋近于0.618F(n)/F(n+1)→1/φ≈0.618黄金分割比φ≈1.618自然界中的最优生长策略建筑和艺术中的比例美学任务6.9：计算斐波那契数列133第6章函数·6.2函数进阶任务6.9设计一个函数，参数为n，计算并返回斐波那契数列第n项的值。F(0)=0F(1)=1F(n)=F(n-1)+F(n-2)递归分析从定义来看，斐波那契数列非常符合递归思路：它有两种基本情况（F(0)=0和F(1)=1），可以递归求得第n项的值。注意事项当测试较小的数值时，程序可以快速给出答案。但是，如果测试一个稍大的数（例如36），程序需要执行几秒钟才能输出结果。斐波那契递归思路135第6章函数·6.2函数进阶递归设计根据斐波那契数列的数学定义，我们可以直接将其翻译为递归函数。Fib(6)=Fib(5)+Fib(4)→Fib(5)=Fib(4)+Fib(3)→Fib(4)=Fib(3)+Fib(2)→...直到Fib(0)或Fib(1)递归结构基本情况1：n==0时返回0基本情况2：n==1时返回1递归步骤：returnFib(n-1)+Fib(n-2)两种基本情况确保递归在n=0或n=1时终止代码6.16：递归求斐波那契数列137第6章函数·6.2函数进阶代码6.16#定义函数defFib(n):

ifn==0:#基本情况1

return

0

elifn==1:#基本情况2

return

1

else:#递归步骤

returnFib(n-1)+Fib(n-2)#调用函数n=6fn=Fib(n)print(f"斐波那契数列的第{n}项为{fn}")运行结果斐波那契数列的第6项为8提示代码非常简洁，直接对应数学定义。但当n较大时（如36），程序执行很慢。斐波那契递归调用树139第6章函数·6.2函数进阶以Fib(5)为例的调用树递归调用过程中，存在大量的重复计算。下图展示了Fib(5)的调用过程：调用树Fib(5)/\Fib(4)Fib(3)<-Fib(3)被计算了2次!/\/\Fib(3)Fib(2)Fib(2)Fib(1)<-Fib(2)被计算了3次!/\Fib(2)Fib(1)<-又一次计算Fib(2)/\Fib(1)Fib(0)注意Fib(3)被计算了2次，Fib(2)被计算了3次！n越大，重复计算越多，效率越低。代码6.17：斐波那契计时测试141第6章函数·6.2函数进阶代码6.17importtime#定义函数defFib(n):

ifn==0:

return

0

elifn==1:

return

1

else:

returnFib(n-1)+Fib(n-2)#调用函数n=36start=time.time()#记录开始时间fn=Fib(n)t=time.time()-start#计算运行时间print(f"斐波那契数列的第{n}项为{fn}")print(f"计算用时为{t:.3f}秒")运行结果斐波那契数列的第36项为14930352计算用时为3.576秒递归效率问题分析143第6章函数·6.2函数进阶注意计算Fib(36)用了约3.5秒，效率非常低！原因是递归过程中重复计算了大量相同的项。重复计算问题例如要计算第36项，就需要计算第35项和第34项；在计算第35项时，还会计算一次第34项。以此类推，程序会进行大量的重复计算，所以导致计算效率下降。n的值Fib(n)的值递归调用次数近似用时1055约177次<0.001秒206765约21891次<0.01秒30832040约2692537次约0.3秒3614930352约39088169次约3.5秒40102334155约331160281次约30秒重复计算的代价145第6章函数·6.2函数进阶问题可视化下图展示了斐波那契递归中各子问题的计算次数。颜色越深表示重复计算次数越多：子问题在Fib(6)中被计算的次数在Fib(10)中被计算的次数Fib(5)1次1次Fib(4)2次5次Fib(3)3次21次Fib(2)5次89次Fib(1)8次377次Fib(0)5次233次注意Fib(1)在计算Fib(10)时被重复计算了377次！这就是递归效率低下的根本原因。记忆化（Memoization）147第6章函数·6.2函数进阶优化思路为了提高程序的运行效率，我们可以尝试将程序运行过程中的计算结果进行保存。如果已经计算过某项的值，就不需要再重复计算。这种技术叫作记忆化（Memoization）。使用字典存储结果考虑使用字典类型保存计算结果键(key)：项数n值(value)：Fib(n)的结果初始化时存入基本情况Fib(0)=0,Fib(1)=1优化效果每个子问题最多计算一次时间复杂度从O(2^n)降为O(n)Fib(36)从3.5秒降为0.000秒Fib(100)也能立即输出结果效率提升非常可观代码6.18：记忆化优化的斐波那契149第6章函数·6.2函数进阶代码6.18importtime#定义函数（带记忆化）defFib(n,data):

if

notnindata:data[n]=Fib(n-1,data)+Fib(n-2,data)

returndata[n]#调用函数n=36data={0:0,1:1}#初始化基本情况start=time.time()fn=Fib(n,data)t=time.time()-startprint(f"斐波那契数列的第{n}项为{fn}")print(f"计算用时为{t:.3f}秒")运行结果斐波那契数列的第36项为14930352计算用时为0.000秒记忆化原理详解151第6章函数·6.2函数进阶代码6.18的工作原理我们在初始化data时，把第0项和第1项的基本情况保存其中，然后递归执行。只要某项的值不包含在字典中，就将其保存。当再次需要某项值时，则无须重复计算。执行过程#data={0:0,1:1}初始状态##调用Fib(5,data):#Fib(5):5不在data中->计算Fib(4)+Fib(3)#Fib(4):4不在data中->计算Fib(3)+Fib(2)#Fib(3):3不在data中->计算Fib(2)+Fib(1)#Fib(2):2不在data中->计算Fib(1)+Fib(0)#Fib(1):1在data中->返回1#Fib(0):0在data中->返回0#data[2]=1,存入字典#data[3]=2,存入字典#data[4]=3,存入字典#data[5]=5,存入字典#最终data={0:0,1:1,2:1,3:2,4:3,5:5}性能对比：优化前后153第6章函数·6.2函数进阶n的值未优化用时优化后用时提升倍数10约0.001秒约0.000秒-20约0.01秒约0.000秒-30约0.3秒约0.000秒-363.576秒0.000秒约3500倍50约77秒约0.000秒数万倍100数小时约0.000秒天文数字3.576s未优化Fib(36)0.000s优化后Fib(36)3500x效率提升记忆化优化总结155第6章函数·6.2函数进阶核心思想记忆化是一种用空间换时间的优化策略。通过额外的数据结构（字典）保存已计算的结果，避免重复计算，从而大幅提升效率。适用场景递归过程中存在重复子问题子问题的解可以缓存递归调用次数远大于子问题数量斐波那契数列是典型案例其他如背包问题、最长公共子序列等优缺点优点：大幅提升时间效率缺点：需要额外空间存储结果时间复杂度：O(n)空间复杂度：O(n)典型的空间换时间策略递归函数设计要点157第6章函数·6.2函数进阶设计递归函数的三个关键设计递归函数时，必须确保以下三个要素，否则程序可能出错或无法终止。1.基本情况至少有一种基本情况基本情况不调用自身直接返回确定的值是递归的终止条件2.递归步骤函数调用自身的部分将问题分解为子问题子问题与原问题结构相同但规模更小3.收敛性递归步骤的参数必须最终收敛到基本情况如factorial(n-1)中n每次减1，最终为1否则会无限递归！常见递归错误159第6章函数·6.2函数进阶缺少基本情况错误示例1#错误：缺少基本情况，无限递归！deffactorial(n):

returnn*factorial(n-1)#永远不会终止，最终报错：#RecursionError:maximumrecursiondepthexceeded参数不收敛错误示例2#错误：参数没有收敛到基本情况defbad_recursion(n):

ifn==1:

return

1

else:

returnbad_recursion(n+1)#n在增大，不会收敛！递归与迭代的对比161第6章函数·6.2函数进阶对比项递归迭代（循环）代码简洁性通常更简洁可能较冗长可读性符合数学定义时高逻辑直接执行效率可能有重复计算通常更高内存消耗调用栈消耗大通常更少适用场景树形/分治问题线性遍历问题调试难度较难调试相对容易栈溢出风险深度大时可能溢出无此风险提示选择原则：问题天然具有递归结构时用递归（如树、分治），需要高效执行时用迭代。两者可以相互转换。Python递归深度限制163第6章函数·6.2函数进阶注意Python默认递归深度限制为1000层。超过限制会抛出RecursionError异常。recursion_limit.pyimportsys#查看当前递归深度限制print(sys.getrecursionlimit())#输出:1000#修改递归深度限制（不推荐）#sys.setrecursionlimit(2000)#测试递归深度deftest(n):

ifn==0:

return

0

returntest(n-1)#test(1000)#会报错！RecursionErrortest(999)#正常运行提示实际应用中应尽量避免深度递归，改用循环或尾递归优化。Python不支持尾递归优化。斐波那契数列的循环实现165第6章函数·6.2函数进阶用循环替代递归既然递归效率存在隐患，我们可以用循环来实现斐波那契数列，避免重复计算和栈溢出。fib_loop.py#循环实现斐波那契数列deffib_loop(n):

ifn==0:

return

0

elifn==1:

return

1a,b=0,1

foriin

range(2,n+1):a,b=b,a+b

returnb#测试importtimestart=time.time()print(f"Fib(100)={fib_loop(100)}")t=time.time()-startprint(f"用时:{t:.6f}秒")循环实现无需额外空间，效率高，无栈溢出风险。扩展应用：最小公倍数167第6章函数·6.2函数进阶最小公倍数（LCM）最小公倍数与最大公约数有密切关系：LCM(a,b)=a*b/GCD(a,b)。利用已实现的GCD函数，可以轻松求出最小公倍数。lcm.py#利用GCD求最小公倍数defGCD(p,q):

ifq==0:

returnp

returnGCD(q,p%q)defLCM(a,b):

returna*