首頁>>技術前沿>>網站系統安全作者：張偉松
遞歸 是程序設計中為了實現多次迭代而使用的一種編程方法。指的是在一個函數中調用自身的技巧。遞歸的實現使得程序設計易于理解，便于操作。而如果應用不當會造成嚴重的內存消耗，甚至死機。在這里，我介紹一下普通遞歸的危害以及如何將它轉換而減少內存損耗，從而提高系統效率，明明白白做一個程序猿。
比如我們要計算階乘，數學上的階乘定義為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個臨時變量?，F在我們計算的是fact(5) 如果要計算10000的階乘，可以預見，程序最多需要保存9999個臨時變量，這對于系統的壓力是比較大的。這里只是舉了一個很微小的例子來說明，對于bp級別的數據，遞歸運用不當可能會造成系統癱瘓。
為了解決這個問題，工程師將如上的普通遞歸轉換為尾遞歸。
“如果一個函數中所有遞歸形式的調用都出現在函數的末尾，我們稱這個遞歸函數是尾遞歸的。當遞歸調用是整個函數體中最后執行的語句且它的返回值不屬于表達式的一部分時，這個遞歸調用就是尾遞歸。尾遞歸函數的特點是在回歸過程中不用做任何操作，這個特性很重要，因為大多數現代的編譯器會利用這種特點自動生成優化的代碼?！?/P>
將上述代碼轉為尾遞歸：
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、本站內容中未聲明為“原創”的內容可能源自其它網站，但并不代表本站支持其觀點，對此帶來的法律糾紛及其它責任與我方無關。如果此內容侵犯了您的權益，請聯系我方進行刪除。
企業動態
