黑马程序员技术交流社区
标题:
浅谈python中的递归函数
[打印本页]
作者:
小李子爱生活
时间:
2018-6-2 00:20
标题:
浅谈python中的递归函数
最近两天刚好学习了递归函数，这篇文章试着跟大家解释一下什么是递归函数
另外，递归在实际应用中使用场景特别少，经常被循环替代，这里顺便比较一下递归和循环的区别
两张图秒懂递归函数
所谓的递归函数就是自己调用自己的函数
我在网上找到一张照片帮助大家理解，看我是不是很机智（一波小花花刷起来，哈哈哈）
递归函数的原理简单，操作起来更加便捷，下面这张图帮助你秒写递归
小伙伴们是不是已经迫不及待地要开始来一波操作了呀
先不要着急，正式练习之前我们需要科普一个数学知识
斐波那契数列
这次我们拿数学界知名的斐波那契数列为例
关于这个数列细节详见百度百科
[来来来，点这里](
https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97
)
简单来说斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
在数学上，斐波纳契数列以如下被以递归的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）
那么如何用python中的递归函数实现斐波那契数列F(n)的值呢
小伙伴们不要慌，容我细细道来
还记得我刚刚图片里提到的递归函数的思想么
递归函数其实是倒着来思考，先要考虑最后一个数是怎么产生的
很显然，斐波纳契数列定义里面已经告诉了我们F(n)=F(n-1)+F(n-2)
然后我们层层倒退到最开始的时候，是什么情况呢
同样，定义已经告诉我们，最开始是这个样子的F(1)=1，F(2)=1
于是我们就可以写出下面这段代码，来实现递归函数
%%%
def getFib(n):
if n==1:
return 1
elif n==2:
return 2
result=getFib(n-1)+getFib(n-2)
return result
n=30
result=getFib(n)
print("第%d个Fibonacci数为%d"%(n,result))
%%%
看起来一切都是那么顺利和完美
但是没多久我们就发现了递归函数的知名缺陷
递归函数执行效率低下
刚刚我们只是计算了第30个斐波纳契数，看起来并没有什么异常
但当我们计算第40个斐波纳契数时，解释器看起来没什么反应，出现了假死状态，过了好久才出现结果
经过网上的一番搜索，发现递归函数存在致命的缺陷：递归算法解题的运行效率较低
在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等
不仅浪费时间而且还浪费空间（具体原理解释详见文章末尾参考资料：
为了实际验证这一点，我用不久前学过了while循环，实现了同样的功能，代码如下：
%%%
def getFib1(n):
if n == 1:
return 1
elif n == 2:
return 2
else:
n1 = 1
n2 = 1
result = 0
i = 3
while i <= n:
result = n1 + n2
n1 = n2
n2 = result
i += 1
return result
n=40
result=getFib1(n)
print("第%d个Fibonacci数为%d"%(n,result))
%%%
同时我利用pycharm自带的计算程序运行时间的功能，当n取不同值时，比较了两段代码的运行时间差异
为了让比较结果更加直观，我做了一个简单的表格
由这张表格可以看出，while循环即使是运算第200个斐波纳契数，也是毫无压力的（运行时间几乎为零）
其实第200个斐波纳契数已经很夸张了，大家看电脑结果
而递归函数在运算到第40个数就已经出现明显吃力的感觉
基于这样的原因，##递归函数在实际应用场景非常小，通常都被循环所取代
好了，今天关于递归函数就讨论到这里吧
让我们下次再见
see you 啦啦
参考资料：
[Python递归（recursion）专题](
http://www.cnblogs.com/balian/archive/2011/02/11/1951054.html
)
[漫谈递归：递归的效率问题](
http://www.nowamagic.net/librarys/veda/detail/2321
)
[Python 递归函数](
https://blog.csdn.net/liang19890820/article/details/72850612
)
作者:
wuzhengjun
时间:
2018-6-2 16:20
小李子好用心呀，点赞
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2
)
)
)
)
)
)
))