遞歸函數(shù)在python的作用
提問人:楊紫紅發(fā)布時(shí)間:2020-11-26
在函數(shù)內(nèi)部,可以調(diào)用其他函數(shù)。如果一個(gè)函數(shù)在內(nèi)部調(diào)用自身本身,這個(gè)函數(shù)就是遞歸函數(shù)。
舉個(gè)例子,我們來計(jì)算階乘 n! = 1 * 2 * 3 * ... * n,用函數(shù) fact(n)表示,可以看出:
fact(n) = n! = 1 * 2 * 3 * ... * (n-1) * n = (n-1)! * n = fact(n-1) * n
所以,fact(n)可以表示為 n * fact(n-1),只有n=1時(shí)需要特殊處理。
于是,fact(n)用遞歸的方式寫出來就是:
def fact(n):
if n==1:
return 1
return n * fact(n - 1)
遞歸函數(shù)的優(yōu)點(diǎn)是定義簡(jiǎn)單,邏輯清晰。理論上,所有的遞歸函數(shù)都可以寫成循環(huán)的方式,但循環(huán)的邏輯不如遞歸清晰。
使用遞歸函數(shù)需要注意防止棧溢出。在計(jì)算機(jī)中,函數(shù)調(diào)用是通過棧(stack)這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的,每當(dāng)進(jìn)入一個(gè)函數(shù)調(diào)用,棧就會(huì)加一層棧幀,每當(dāng)函數(shù)返回,棧就會(huì)減一層棧幀。由于棧的大小不是無限的,所以,遞歸調(diào)用的次數(shù)過多,會(huì)導(dǎo)致棧溢出。
舉個(gè)例子,我們來計(jì)算階乘 n! = 1 * 2 * 3 * ... * n,用函數(shù) fact(n)表示,可以看出:
fact(n) = n! = 1 * 2 * 3 * ... * (n-1) * n = (n-1)! * n = fact(n-1) * n
所以,fact(n)可以表示為 n * fact(n-1),只有n=1時(shí)需要特殊處理。
于是,fact(n)用遞歸的方式寫出來就是:
def fact(n):
if n==1:
return 1
return n * fact(n - 1)
遞歸函數(shù)的優(yōu)點(diǎn)是定義簡(jiǎn)單,邏輯清晰。理論上,所有的遞歸函數(shù)都可以寫成循環(huán)的方式,但循環(huán)的邏輯不如遞歸清晰。
使用遞歸函數(shù)需要注意防止棧溢出。在計(jì)算機(jī)中,函數(shù)調(diào)用是通過棧(stack)這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的,每當(dāng)進(jìn)入一個(gè)函數(shù)調(diào)用,棧就會(huì)加一層棧幀,每當(dāng)函數(shù)返回,棧就會(huì)減一層棧幀。由于棧的大小不是無限的,所以,遞歸調(diào)用的次數(shù)過多,會(huì)導(dǎo)致棧溢出。
繼續(xù)查找其他問題的答案?
相關(guān)視頻回答
點(diǎn)擊加載更多評(píng)論>>