实用Python程序设计MOOC-第四章函数和递归
实用Python程序设计MOOC-第四章函数和递归

实用Python程序设计MOOC-第四章函数和递归

[TOC]

实用Python程序设计MOOC-第四章函数和递归

函数的概念和用法

为什么需要函数?

写了一段平方根的代码,程序里面无数地方都要求平方根,难道需要的地方都把这段代码拷贝一遍?

数百个程序员如何合写一个程序?都在一个. py文件上操作吗?不同程序员实现不同功能,一个程序员要使用另一个程序员写的功能时怎么办?

“函数”:将实现了某一功能,并需要在程序中多处使用的代码包装起来形成一个功能模块(即写成一个”函数”),那么当程序中需要使用该项功能时,只需写一条语句,调用实现该功能的”函数”即可。

不同的程序员可以分别写不同的函数,拼起来形成一个大程序。

函数的定义

1
2
def 函数名(参数1, 参数2....):
语句体(函数体)
1
2
def 函数名():
语句体(即"函数体")

函数调用和return语句

调用函数:

1
函数名(参数1, 参数2, ...)

对函数的调用,也是一个表达式。函数调用表达式的值,由函数内部的return语句决定。return语句语法如下:

1
return 返回值

return语句的功能是结束函数的执行,并将”返回值”作为结果返回。”返回值”是常量、变量或复杂的表达式均可。如果函数不需要返回值,return语句就直接写:

1
return

return语句作为函数的出口,可以在函数中多次出现。多个return语句的”返回值”可以不同。在哪个return语句结束函数的执行,函数的返回值就和哪个return语句里面的”返回值”相等。

函数使用实例1 : Max函数

1
2
3
4
5
6
def Max(x,y):	#传入形参
if x > y:
return X
else:
return y
#函数到此结束
1
2
3
n = Max(4, 6)	#传入实参
print(n, Max(20, n)
print(Max("about", "take"))
1
2
6 20
take

函数使用实例2 :判断是否是素数的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def IsPrime(n):
if n <= 1 or n % 2 == 0 and n != 2:
return False
elif n == 2:
return True
else :
for i in range(3, n, 2):
if n % i == 0:
return False
if i * i > n:
break
return True
for i in range(100):
if(IsPrime(i)):
print(i, end = " ")
1
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

不返回值的函数

1
2
3
def DrawCircle(x, y, r):
#下面的代码在屏幕上以(x,y)点为圆心,r为半径画圆
return #没有也可以

调用:

1
DrawCircle(0, 0, 1)

函数返回多个值

1
2
3
4
def sumAndDifference(x, y):
return x+y, x-y
s, d = sumAndDifference(10, 5)
print(s, d)

=>155

函数中的变量

  • 一个函数内部定义(赋值)的变量,在这个函数外部不能使用
  • 不同函数中的同名变量不会互相影响
  • 函数中的变量和全局变量(在函数外面定义的变量)同名的情况(假设都叫x):
    1)如果没有对x赋值,函数中的x就是全局的x
    2)如果对x赋值,且没有特别声明,则在函数中全局的x不起作用,函数中的x就是只在函数内部起作用的x
    3)函数内部可以用global x声明函数里的x就是全局变量x
1
2
3
4
5
6
7
8
9
10
11
12
13
14
x = 4	#全局的x 
def f0():
print("x in f0:", x) #这个x是全局的x
def f1():
x = 8 #这个x是局部的x,不会改变全局的x
print("x in f1:", x)
def f2():
global x #说明本函数中的x都是全局的x
print("x in f2:", x)
x = 5
print("x in f2:", x)
def f3():
print("x in f3=", x) #会出错。因后面有赋值而被当作局部的x,此处没赋值就先使用了,不行
x = 9
1
2
3
4
5
6
7
8
f0() #>> x in f0:4
f1() #>> x in f1:8
print(x) #>>4
f2()
#>> x in f2:4
#>> x in f2:5
print(x) #>> 5
f3() #调用f3会出错

python内置函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int(x)
float(x)
str(x)
ord(x)
chr(x)
abs(x)
len(x)
len("123")
len([2,3,4])
max(x)
x是列表,如max([2,3,5])
min(x)
x是列表,如min([2,3,5])
max(x1, x2, x3...)
min(x1, x2, x3...)
print(max(1, 2, 3)) #>> 3
print(min("ab", "cd", "af")) #>> ab

什么是递归

  • 一个概念的定义中用到了这个概念本身,这就叫递归

用递归的方式定义”n的阶乘”

1) “1的阶乘”是1
2)”n的阶乘”就是n乘以”(n-1)的阶乘”

第二句中用到了阶乘这个需要定义的概念

  • 一个函数,自己调用自己,就是递归。
  • 和调用别的函数无本质区别,可以看作是调用另一个同名同功能函数
1
2
3
4
5
def Factorial(n):	#函数返回n的阶乘
if n < 2:
return 1 #终止条件
else:
return n * Factorial(n - 1)
1
2
print(Factorial(4))	#>>24
print(Factoria1(5)) #>>120
  • 递归函数需要有终止条件,否则就会无穷递归导致程序无法终止甚至崩溃
  • 递归定义也需要有终止条件,否则无法让人明表。例如”n的阶乘”的定义中的:
    1) “1的阶乘”是1
Factorial函数执行过程
  • 求斐波那契数列第n项的函数
1
2
3
4
5
def Fib(n):
if n == 1 or n == 2:
return 1
else:
return Fib(n-1) + Fib(n-2)
1
2
3
4
5
6
7
8
9
10
11
def f(n,m):
if n== 0:
return m
elif m == 0:
return n
else:
if n >= m:
return f(m, n-m) + 1
else:
return f(n, m-n) + 2
print(f(3,4)) #>> 7

递归例题:上台阶

上台阶问题:有n级台阶,每步可以走一级或两级,问有多少种不同的走法?

先做一步,剩下问题和原问题形式相同,规模变小

1
2
3
4
5
6
7
8
def ways(n):
if n == 1:
return 1
elif n == 2:
return 2
else:
return ways(n-1) + ways(n-2) #第一步走一级的走法+第一步走2两级的走法
print(ways(4)) #>> 5

递归例题:汉诺塔(Hanoi)

汉诺塔问题
1
2
3
4
5
6
7
8
9
10
def Hanoi(n, src, mid, dest):	#将src座上的n个盘子,以mid座为中转,移动到dest座
if(n == 1): #只需移动一个盘子
#直接将盘子从src移动到dest即可
print(src + "->" + dest)
return #递归终止
Hanoi(n-1, src, dest, mid) #先将n-1个盘子从src移动到mid
print(src + "->" + dest) #再将一个盘子从src移动到dest
Hanoi(n-1, mid, src, dest) #最后将n-1个盘子从mid移动到d
n = int(input())
Hanoi(n, 'A', 'B', 'C')
1
2
3
4
5
6
7
8
3
A->C
A->B
C->B
A->C
B->A
B->C
A->C

n个盘子需要2^n-1次

汉诺塔手工解法

递归例题:绘制雪花曲线(科赫曲线)

雪花曲线的递归定义
1)长为size,方向为x(x是角度)的0阶雪花曲线,是方向x上一根长为size的线段
2)长为size,方向为x的n阶雪花曲线,由以下四部分依次拼接组成:
1.长为size/3,方向为x的n-1阶雪花曲线
2.长为size/3,方向为x+60的n-1阶雪花曲线
3.长为size/3,方向为x-60的n-1阶雪花曲线
4.长为size/3,方向为x的n-1阶雪花曲线

size是整体长度

1阶0度雪花曲线 2阶0度雪花曲线

四段一阶的雪花曲线构成
1.长度为size/3,方向为0°的1阶雪花曲线
2.长度为size/3,方向为60°的1阶雪花曲线
3.长度为size/3,方向为-60°的1阶雪花曲线
4.长度为size/3,方向为0°的1阶雪花曲线

3阶0度雪花曲线

四段二阶的雪花曲线构成
1.长度为size/3,方向为0°的2阶雪花曲线
2.长度为size/3,方向为60°的2阶雪花曲线
3.长度为size/3,方向为-60°的2阶雪花曲线
4.长度为size/3,方向为0°的2阶雪花曲线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import turtle	#曲图要用这个turtle包
def snow(n,size): #n是阶数目,size是长度 从当前起点出发,在当前方向画一个丧度为size,阶为n的雪花曲线
if n== 0:
turtle.fd(size) # 笔沿着当前方向前进size
else:
for angle in [0, 60, -120, 60]: #对列表中的每个元素angle:
turtle.left(angle) #笔左转ang1e度 ,turtle .1t (ang1e)也可
snow(n-1, size/3)

turtle.setup(800, 600)#窗口缺省位于屏幕正中间,宽高800*600像素,窗口中央坐标(0,0)
#初始笔的前进方向是0度。正东方是0度,正北是90度
turtle.penup() #抬起笔
turtle.goto(-300, -50) #将笔移动到-300, -50位置
turtle.pendown() #放下笔
turtle.pensize(3) #笔的粗度是3
snow(3, 600) #绘制长度为600 ,阶为3的雪花曲线,方向水平
turtle.done() #保持绘图窗口
3阶0度雪花曲线

窗口正中心位置是(0, 0)
画图要有画笔,画笔需要有方向
雪花曲线画完之后笔的方向和初始方向一样

  • 画整个雪花
3阶全雪花曲线
1
2
3
4
5
6
7
8
9
10
11
12
13
turtle.setup(800, 800)
turtle.speed(1000)
turtle.penup()
turtle.goto(-200, 100)
turtle.pendown()
turtle.pensize(2)
level = 3
snow(level, 400)
turtle.right(120) #右拐120度
snow(level, 400)
turtle.right(120)
snow(level, 400)
turtle.done()
3阶全雪花曲线
  • 递归问题解法

1.先做一步,观察剩下问题是否和原问题相同,规模更小
2.将一个大问题分解成若干个子问题,有些子问题和原问题都是形式相同,规模更小的
3.选取合适的边界条件

奇异三角形

一个边长为x的0阶奇异三角形,是一个边长为x的等边三角形
一个边长为x的n阶奇异三角形,是一个边长为x的等边三角形,三个角上分别是一个边长为x/2的n-1阶奇异三角形

  • 0阶奇异三角形
0阶奇异三角形
  • 1阶奇异三角形
1阶奇异三角形
  • 2阶奇异三角形
2阶奇异三角形
  • 输入整数n,(0<=n<=5),绘制n阶奇异三角形

  • 提示

1) turtle.left(x) 可以向左拐 x 度
2) turtle.right(x)可以向右拐 x 度
3) pos = turtle.pos() 可以取得画笔当前位置, 以后 turtle.goto(pos)就可以移动画笔到那个位置
4) turtle.seth(x)可以设置画笔方向为角度 x
5) 绘图完成后调用 turtle.done() 可以保持绘图窗口

  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
intn = int(input())

import turtle
def san(n, x):
if 0 == n:
for angle in [60, -120, -120]:
turtle.left(angle)
turtle.fd(x)
else:
pos = turtle.pos()
san(n - 1, x / 2)
turtle.penup()

turtle.goto(pos) #-180
turtle.right(120)
turtle.fd(x / 2)
turtle.right(60)

turtle.pendown()
san(n - 1, x / 2)
turtle.penup()

turtle.goto(pos)
turtle.right(180)
turtle.fd(x / 2)
turtle.pendown()

san(n - 1, x / 2)

turtle.setup(600, 600)
turtle.pensize(2)
san(intn, 200)
turtle.done()
1阶奇异三角形 2阶奇异三角形 3阶奇异三角形
文章作者: HibisciDai
文章链接: http://hibiscidai.com/2022/09/23/实用Python程序设计MOOC-第四章函数和递归/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 HibisciDai
好用、实惠、稳定的梯子,点击这里