首页>>技术前沿>>网站系统安全作者：张伟松
递归 是程序设计中为了实现多次迭代而使用的一种编程方法。指的是在一个函数中调用自身的技巧。递归的实现使得程序设计易于理解，便于操作。而如果应用不当会造成严重的内存消耗，甚至死机。在这里，我介绍一下普通递归的危害以及如何将它转换而减少内存损耗，从而提高系统效率，明明白白做一个程序猿。
比如我们要计算阶乘，数学上的阶乘定义为X！ X为大于零的正整数。
例如5的阶乘表示
5！ = 1*2*3*4*5 = 120
4！ = 1*2*3*4 = 24
当然多数程序设计语言中有封装的阶乘计算函数，这里我们尝试使用递归自己编写。
def fact(x):
if x == 1:
return 1
return x * fact(x-1)
如上所示，递归需要一个结束条件，否则就成了死循环。阶乘的结束条件是X=1， 因为1的阶乘就是1，无需计算。
函数第三行返回了 当前参数x乘以函数本身。
我们跟随程序运行的步调，深入观察代码运行，以fact(5)为例
fact(5) =
5*fact(4) =
5*(4*fact(3)) =
5*(4*(3*fact(2))) =
5*(4*(3*(2*fact(1)))) =
5*(4*(3*(2*1))) =
5*(4*(3*2)) =
5*(4*6) =
5*24 =
120
可以看到，程序运行到第五行，系统需要保存4个临时变量。现在我们计算的是fact(5) 如果要计算10000的阶乘，可以预见，程序最多需要保存9999个临时变量，这对于系统的压力是比较大的。这里只是举了一个很微小的例子来说明，对于bp级别的数据，递归运用不当可能会造成系统瘫痪。
为了解决这个问题，工程师将如上的普通递归转换为尾递归。
“如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。”
将上述代码转为尾递归：
def fact0(x, prod = 1):
if x == 1:
return prod
return fact0(x-1,x*prod)
观察以上代码的运行：
fact0(5) =
fact0(4,5) =
fact0(3,20) =
fact0(2,60) =
fact0(1,120) =
120
可见函数在进行递归调用的时候已经计算了新的参数，第一个参数是当前需要递归的层数，第二个参数是已经计算的累计乘法值。层数每减1，累计乘法值*当前层数。最终返回阶乘值。运行速度杠杠的！
怎么样？是不是又学会了一种新的装逼技能！
如果你觉得本篇文章对你有帮助，请扫下面二维码爱我左微信右支付宝
【全文完】
版权声明:
1、陕西弈聪网站内容中凡注明“来源：XXX（非陕西弈聪网站）”的作品，转载自其它媒体，转载目的在于传递更多信息，其中涉及的网站建设，网站优化，百度关键词优化，西安软件开发等技术细节并不代表本站赞同支持其观点，并不对其真实性负责。对于署名“陕西弈聪”的作品系本站版权所有，任何人转载请署名来源，否则陕西弈聪将追究其相关法律责任。
2、本站内容中未声明为“原创”的内容可能源自其它网站，但并不代表本站支持其观点，对此带来的法律纠纷及其它责任与我方无关。如果此内容侵犯了您的权益，请联系我方进行删除。
企业动态
