Python中的递归函数和斐波那契数列

鳄鱼君

发表文章数:643

Vieu四代商业主题

高扩展、安全、稳定、响应式布局多功能模板。

¥69 现在购买
首页 » Python » Python中的递归函数和斐波那契数列

Python中的递归函数

在函数内部可以调用其它函数,如果一个函数在内部调用自己本身,这个函数就是递归函数

递归特性

  • 1.必须有一个明确的结束条件
  • 2.每次进入更深一层递归时,问题的规模相比上次递归都应有所减少
  • 3.递归效率不高,递归层次过多会导致栈溢出(在计算机中,函数调用时通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈,每当函数返回,栈就会减少一层栈帧,每当函数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以递归调用的次数过多就会导致栈溢出)
  • 4.递归的最大深度为999左右,不同的机器应该是不一样的吧(๑Ő௰Ő๑)~,超过这个深度就会报错,所以需要一个明确的结束条件

实例引入

def number(n):
    print(n)
    return number(n+1)
number(0)
#这个即使函数自己不断地循环调用,知道最大深度位置

在学Python时,不可避免的是斐波那契数列,我现在就觉得它还有点模糊,不过没关系,只要基础狗牢固,理解只是时间问题(✿◡‿◡)

# 两个元素的总和确定了下一个数
a, b = 0, 1
while b < 10:
    print(b)
    a, b = b, a+b    
#这个可以分析一下,其中代码 a, b = b, a+b 的计算方式为先计算右边表达式,
#然后同时赋值给左边,等价于:
a=0,b=1
a=1,b=1
a=1,b=2
a=2,b=3
a=3,b=5
a=5,b=8
#第一行包含了一个复合赋值:变量 a 和 b 同时得到新值 0 和 1。
#最后一行再次使用了同样的方法,可以看到,右边的表达式会在赋值变动之前执行。
#右边表达式的执行顺序是从左往右的。
a, b = 0, 1
while b < 1000:
    print(b, end=',')
    a, b = b, a+b
#两个代码的意思是一样的,只不过第二个,输出一个b不会换行,print是默认换行

print() sep 参数使用:

a,b,c=10,20,30
print(a,b,c,sep='@') #输出10@20@30
print(a,b,c,sep='#$') #输出10#$20#$30
#我也不知道这个有什么用(๑→ܫ←)

φ(゜▽゜*)♪还有一个递归也需要说一下

递归方式求斐波纳契数列

#递归就是函数内部调用自身
#使用 print(fab(num)) #num 是一个数字
#可用递归方式求输入数字的斐波纳契结果
def fab(n):
    if n<1:
        print('输入有误!')
        return -1    
    if n==1 or n==2:
        return 1    
    else:
        return fab(n-1)+fab(n-2)
#这是一个函数,调用方法fab(num)
#假设fab(10) 先设小一点,理解一下
#直接else呢句
#fab(9)+fab(8)
#fab(7)+fab(6)
#fab(5)+fab(4)
#fab(3)+fab(2)
#fab(1)+fab(0)
#我直接全部列出来了
#然后你需要再往下,吧fab(9)...全部求出来
#想想都复杂
#fab(3)=2 前面的fab(0)=-1,fab(1),fab(2)=1
#fab(4)=fab(3)+fab(2)=3 可能有些不知道我在列什么
#fab(5)=fab(4)+fab(3)=5 其实是有规律的
#往下面自己列出来,输出55

单纯说递归还好吧,因为递归在很大程度上牺牲了空间换取了可读性。每次调用递归函数的时候都会创建一个函数栈,如果递归深度过大,则会造成溢出状况。同样是斐波那契数列,有很多大神方法列出来,我一个小白根本想不到,下面是大神的一些方法,我也不知道能不那个理解,我尽量写清楚颠。

利用列表可以将前20项输出.这个指的是上面的呢一种方法,如果数字太大,就会浪费资源,然后大神算法开始:利用列表记录n-1项,可以很大程度上减少重复计算量.利用字典记录也可以实现相同运算.

n=int(input('请输入一个整数:'))
def fab(n):
    if n<1:
        print('输入有误!')
        return -1    
    if n==1 or n==2:
        return 1
    else:
        return fab(n-1)+fab(n-2)
result=[]
for i in range(1,n+1):
    result.append(fab(i))

print(result) 

n=int(input('请输入一个整数:')) 
dic = {0:0,1:1}
def fib(n):
    if n in dic:
        return dic[n]
    else:
        temp = fib(n-1)+fib(n-2)
        dic[n] = temp
        return temp
for i in range(n):
    print(fib(i+1),end=" " )

这种方法其实就是用List和Dict来储存记录,原理都是一样的,只不过是提高效率,不在解释过多了,有点上头了

采用尾递归的方法,不需要保存额外的栈帧,既保证了运行效率,又具有可读性。实例:

#尾递归算法实现
import time
n=int(input('请输入一个整数:'))
a=0
b=1
start = time.time() #计算开始时间
def F(n,a,b):
 if n==0:
    return a
 return F(n-1,b,a+b)
print(F(n,a,b))
end = time.time() #计算结束时间,简单测试一下效率
print("运行时间:%.2f秒"%(end-start))
# %f格式化浮点数字,可指定小数点后的精度
#如果不懂的话去前面字符串格式化看看
#m.n. m 是显示的最小总宽度,n 是小数点后的位数(如果可用的话)
#这比较复杂,举个数吧10,小一点
#如果n!=0,会一直循环下去
#F(10,0,1)
#F(9,1,1)
#F(8,1,2)
#F(7,2,3)
#F(6,3,5)
#F(5,5,8)
#F(4,8,13)
#F(3,13,21)
#F(2,21,34)
#F(1,34,55)
#F(0,55,89)
#n=0,return a值为55
#这个只是看懂了,如果没有这个算法,你会不会想出来

未经允许不得转载:作者:鳄鱼君, 转载或复制请以 超链接形式 并注明出处 鳄鱼君
原文地址:《Python中的递归函数和斐波那契数列》 发布于2019-11-06

分享到:
赞(2) 赏杯咖啡

评论 抢沙发

2 + 1 =


文章对你有帮助可赏作者一杯咖啡

支付宝扫一扫打赏

微信扫一扫打赏

Vieu4.6主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。
切换注册

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录
切换登录

注册