函数(三)
前言:
函数真的是一个内容非常丰富的话题,在实际应用中,如何更好的发挥函数的作用,就成了我们要努力去学习去思考的问题.
编程是一门具有创造性的学科.当我们掌握了基础的用法以后,就要学会独立思考,如何创造出更美好的事物出来
递归
今天的话题 ,想谈谈递归函数.
什么是递归函数呢?
百度百科如此定义:
编程语言中，函数Func直接或间接调用函数本身，则该函数称为递归函数。
案例分析
斐波那契数列
有这么一组数:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
我们能发现什么规律呢?
可以发现:
第三个数:2 = 1 + 1
第四个数:3 = 2 + 1
第五个数:5 = 3 + 2
第六个数:8 = 5 + 3
...
第n个数 = 第n-1个数 + 第n-2个数
因此,要想求出第n个数,我们要先求第n-1个数,与第n-2个数
我们先来一个函数来实现这个任务
def fb1(n):
# 初始化第一个数与第二个数
if n == 1 or n == 2:
return 1
# 当n >=3时
f1 = 1 # 初始化前二个数
f2 = 1 # 初始化前一个数
for i in range(3, n+1):
f3 = f1 + f2 # 计算当前个数的值,
f1, f2 = f2, f3 # 更新前两个数的值,分别往生移一个数
# 以上代码等效于:
# f1 = f2
# f2 = f3
return f3 # 循环结束的时候,返回最终的当前个数的值
代码分析:
先把两种最简单的情况的值返回,也就是如果求的是第一个或第二个数,就直接返回1
如果是第三个数及以后的数,就从第三个数开始算起,一直算到我们想要的那个数为止,这是我们普通函数处理方法
再来看下一段代码
def fb2(n):
if n == 1 or n == 2:
return 1
return fb2(n-1) +fb2(n-2)
如果这个时候,你调用一下这个函数,就可以轻易的发下,这个东西的返回值和上一个函数的返回值是一样的,也就,这个函数同样实现求我们例子中的第几个数的值的任务.
但是我们看代码却会发现,两者差异相当大.后者的代码非常干净整洁.
我们来看一下,这段代码做了些什么
一个条件结构,返回了 第一个数与第二个数的值 1
当不是第一个数的时候,直接返回了fb2(n-1) + fb2(n-2)
这个是什么意思呢?
我们设想一下: n = 3 时
fb2(n-1) + fb2(n-2) = fb2(2) +fb2(1) = 1 + 1 = 2
当 n = 4 时
fb2(n-1) + fb2(n-2) = fb2(3) + fb2 (2) = fb2(3) + 1
这个时候fb2(3) 因为n 不是1 也不是2 ,因此,会继续按第一个设想这样变成fb2(2) + fb2(1)
因此,这个式子,最终变成了
fb2(n-1) + fb2(n-2) = fb2(3) + fb2 (2) =fb2(2) +fb2(1) +fb2(1) = 3
以此类推.
像这样,在函数定义的时候,会调用自身的函数,称为递归函数.
由这个代码可知,程序逻辑比较复杂的时候,递归函数会比正常的函数实现代码要整洁很多.
如果我们仔细分析,发现原理也不是那么不好理解 .
求和
求一组无规律数字的和:
nums = [1, 19, 9, 8, 18, 18,17, 20, 100, 200, 91, 22]
正常的代码实现:
def sum1(num_list):
result = 0
for num in num_list:
result += num
return result
递归的方法
def sum2(num_list):
if len(num_list) == 1:
return num_list[0]
return num_list[0] + sum2(num_list[1:])
当然,这个例子不是很能体现这递归的优势,重点在于理解递归的处理逻辑
案例3
一个数列满足:
写一个函数来求这个数列的第n项
常规函数解法:
def an(n):
if n == 1:
return 1
if n == 2:
return 2
a1 = 1
a2 = 2
for i in range(3,n):
a3 = a2*a2 + a1
a1 = a2
a2 = a3
retun a3
递归的写法:
def an2(n):
if n == 1:
return 1
if n == 2:
return 2
return an2(n-1) * an2(n-1) + an2(n-2)
案例4
在讲turtle的时候,我们画了一个二叉树.就是一个枝头分两枝,再小枝头又分两枝,如此继续的情况
我们当时因为层数不多,直接使用了顺序结构.
我们现在努力用优雅的方式,来实现那个目标:递归
思路分析:
1.先画一个树干(因为树干只有一个)
以树干的顶点为起点,先朝左画一个枝头
如果没有下一层了,就返回,然后画右枝
如果还有下一层的枝头,就调用自己往下画枝头
def ecs(n):
if n == 1:
a = (10, 45)
(a)
(n*10)
(n*10)
(a*2)
(n*10)
(n*10)
(a)
return
a = (10, 45)
(a)
(n*10)
ecs(n-1)
(n*10)
(a*2)
(n*10)
ecs(n-1)
(n*10)
(a)
# 画树干
(1000, 800)
()
(0, -300)
()
(90)
(100)
(0)
# 调用函数画树枝
ecs(8)
() # 画好后停止
作品赏析
微信截图_20201217210247.png
当我们需要在函数执行过程中要重复一个动作,就可以考虑对自身调用,(递归)来实现.这样可以避免一些过为烦杂的循环程序
努力去学习,掌控递归函数,可以画出很多优美的作品.