解決python遞歸函數(shù)及遞歸次數(shù)受到限制的問題

更新時間：2022年06月28日 10:12:05 作者：LLLLLLLLLLLLIU

這篇文章主要介紹了解決python遞歸函數(shù)及遞歸次數(shù)受到限制的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

遞歸函數(shù)及遞歸次數(shù)受到限制

一個函數(shù)在內(nèi)部調(diào)用自己，那么這個函數(shù)是遞歸函數(shù)。遞歸會反復使用本身，每遞歸一次，越接近最終的值。當一個問題可以由許多相似的小問題解決，可以考慮使用遞歸函數(shù)。隨著遞歸的深入，問題規(guī)模相比上次都應所減小。return函數(shù)本身的方法保證了遞歸的持續(xù)進行，但是如果沒有明確的結(jié)束條件，遞歸會無限進行下去。所以當已經(jīng)到了問題解決的程度，應該告訴函數(shù)結(jié)束遞歸，這就需要明確的結(jié)束條件。

常見的兩個遞歸例子：求和、求階乘n!

求和：sum=n+n(n-1)+…+1

def sum(n):
? ? if n > 0: ? ? ? ? ? ? ?
? ? ? ? return n+sum(n-1)
? ? else:
? ? ? ? return 0 ? ? ? ? ??
new_sum = sum(10)
print(new_sum)
#output
55

求階乘：n!=1x2x3…xn

def factorial(n):
? ? if n == 1:
? ? ? ? return 1
? ? else:
? ? ? ? return n*factorial(n-1)
new_sum = factorial(5)
print(new_sum)
#output
120

使用遞歸函數(shù)需要注意遞歸次數(shù)默認限制為1000，如果遞歸次數(shù)較多會導致棧溢出的問題

比如

def sum(n):
? ? if n > 0:
? ? ? ? return 1+sum(n-1) ?
? ? else:
? ? ? ? return 0
new_sum = sum(1000)
print(new_sum)

會報RecursionError: maximum recursion depth exceeded in comparison的錯誤

解決問題的辦法是修改可遞歸的次數(shù)

import sys
sys.setrecursionlimit(1500)#可遞歸次數(shù)修改為1500
def sum(n):
? ? if n > 0:
? ? ? ? return 1+sum(n-1) ?
? ? else:
? ? ? ? return 0
new_sum = sum(1000)
print(new_sum)
#output
1000

修改遞歸次數(shù)時需要注意，修改可遞歸次數(shù)為1500，遞歸深度到不了1500，在1400左右。默認可遞歸次數(shù)為1000，遞歸深度也到不了1000，到992左右

如何控制遞歸的次數(shù)

經(jīng)常會用到遞歸，雖然能解決很多問題，但其缺點很明顯，有可能無法跳出造成死循環(huán)，能控制遞歸次數(shù)就可以避免這種情況。

用lua嘗試了幾種方法，

第一種

在方法內(nèi)定義一個變量計數(shù)：

function recursionTest()
? ? local times = 0
? ? if times < 10 then
? ? ? ? times = times + 1
? ? ? ? recursionTest()
? ? end
? ? if times == 0 then
? ? ? ? print("outer round")
? ? end
end

執(zhí)行下來，是無法限制的，因為局部變量每次都會重置為0。

第二種

local recurTimes = 0
function recursionTest2()
? ? if recurTimes < 10 then
? ? ? ? recurTimes = recurTimes + 1
? ? ? ? recursionTest2()
? ? end
end

這種方法可以控制次數(shù)，但是變量需要定義在方法體外，執(zhí)行函數(shù)前都需要先把這個變量設(shè)為0，需要在遞歸方法外包一層，比較繁瑣。

第三種

function recursion(str, t)
? ? str = str or "first time "
? ? t = t or 0
? ? t = t + 1
? ? print(str, t)
? ? if t < 10 then
? ? ? ? recursion("times:", t)
? ? end
? ? if t == 1 then
? ? ? ? print("outer round")
? ? end
end

在遞歸時傳入一個自增變量，達到閾值時停止遞歸，執(zhí)行最外層時無需傳參，默認值為0，且可根據(jù)t的值判斷當前的遞歸層數(shù)，可以在遞歸結(jié)束時，在最外層執(zhí)行完之前做其他事情，一舉兩得。

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: