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

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

常見的兩個(gè)遞歸例子：求和、求階乘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ù)默認(rèn)限制為1000，如果遞歸次數(shù)較多會(huì)導(dǎo)致棧溢出的問(wèn)題

比如

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

會(huì)報(bào)RecursionError: maximum recursion depth exceeded in comparison的錯(cuò)誤

解決問(wèn)題的辦法是修改可遞歸的次數(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í)需要注意，修改可遞歸次數(shù)為1500，遞歸深度到不了1500，在1400左右。默認(rèn)可遞歸次數(shù)為1000，遞歸深度也到不了1000，到992左右

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

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

用lua嘗試了幾種方法，

第一種

在方法內(nèi)定義一個(gè)變量計(jì)數(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í)行下來(lái)，是無(wú)法限制的，因?yàn)榫植孔兞棵看味紩?huì)重置為0。

第二種

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

這種方法可以控制次數(shù)，但是變量需要定義在方法體外，執(zhí)行函數(shù)前都需要先把這個(gè)變量設(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

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