Python遞歸及尾遞歸優(yōu)化操作實(shí)例分析

本文實(shí)例講述了Python遞歸及尾遞歸優(yōu)化操作。分享給大家供大家參考，具體如下：

1、遞歸介紹

遞歸簡(jiǎn)而言之就是自己調(diào)用自己。使用遞歸解決問題的核心就是分析出遞歸的模型，看這個(gè)問題能拆分出和自己類似的問題并且有一個(gè)遞歸出口。比如最簡(jiǎn)單的就5的階乘，可以把它拆分成5*4!，然后求4!又可以調(diào)用自己，這種問題顯然可以用遞歸解決，遞歸的出口就是求1！，可以直接返回1。用Python實(shí)現(xiàn)如下：

def fact(n):
  if n==1:
    return n
  return n*fact(n - 1);
print(fact(5))

運(yùn)行結(jié)果：

120

2、尾遞歸優(yōu)化

在上面的求遞歸中，也有一定的缺點(diǎn)，假如說求1000!的階乘，會(huì)出現(xiàn)棧溢出的問題，因?yàn)樵诤瘮?shù)執(zhí)行中，沒調(diào)用一個(gè)函數(shù)都會(huì)把當(dāng)前函數(shù)的調(diào)用位置和內(nèi)部變量保存在棧里面，由于棧的空間不是無限大（具體棧的最大空間還沒有查找到），假如說調(diào)用層數(shù)過多，就是出現(xiàn)棧溢出的情況。

這個(gè)時(shí)候就可以用尾遞歸優(yōu)化來解決，尾調(diào)用的概念非常簡(jiǎn)單，一句話就能說清楚，就是指某個(gè)函數(shù)的最后一步是調(diào)用另一個(gè)函數(shù)。

function f(x){
 return g(x);
}

尾遞歸優(yōu)化后的階乘函數(shù)如下：

def fact(n):
  return fact_iter(n,1);
def fact_iter(num, product):
  if num == 1:
    return product
  return fact_iter(num - 1, num * product)
print(fact(5))
print(fact(1000))

尾調(diào)用由于是函數(shù)的最后一步操作，所以不需要保留外層函數(shù)的調(diào)用記錄，因?yàn)檎{(diào)用位置、內(nèi)部變量等信息都不會(huì)再用到了。所以尾遞歸優(yōu)化可以有效的防止棧溢出，但是尾遞歸優(yōu)化需要編譯器或者解釋器的支持，遺憾的是，大多數(shù)編程語言沒有針對(duì)尾遞歸做優(yōu)化，Python解釋器也沒有做優(yōu)化，所以，即使把上面的fact(n)函數(shù)改成尾遞歸方式，也會(huì)導(dǎo)致棧溢出。

3、漢諾塔問題

漢諾塔問題也是一個(gè)經(jīng)典的遞歸問題，具體題目就不說了，這里分析思路。假設(shè)hanoi(n, a, b, c)實(shí)現(xiàn)把a(bǔ)上的n個(gè)盤子移到c上。

當(dāng)只有一個(gè)盤子時(shí)，直接從A移動(dòng)到C即可

如果有3個(gè)盤子，可以這樣：

# A --> C
# A --> B
# C --> B
# A --> C
# B --> A
# B --> C
# A --> C

如果有很多盤子，我們分析一下該怎么移動(dòng)，首先，我們需要把n-1個(gè)盤子移動(dòng)到b中，才可以實(shí)現(xiàn)最簡(jiǎn)單的一步，把a(bǔ)中最大的盤子移動(dòng)到c中，具體怎么轉(zhuǎn)移到b中后面再討論。移動(dòng)最大的盤子后，a和c都可以看成是空的，接下來，把b看成是a，把a(bǔ)看成是b，把a(bǔ)中的n-1個(gè)盤子（這里的n是已經(jīng)減1的n）移動(dòng)到b后，又可以移動(dòng)第二大的盤子。這顯然是一個(gè)遞歸問題。

遞歸的出口就是n等于1，直接從a移動(dòng)到c即可。

那么怎么接下來討論，怎么把n-1個(gè)盤子移動(dòng)到b，這不又是一個(gè)遞歸問題嘛！可以調(diào)用它自己呀，只不過需要把b看成是c，把c看成是b。所以代碼如下：

def hanoi(n,a,b,c):
  #只有一個(gè)盤子，直接移動(dòng)
  if n==1:
    print(a,'->',c)
  else:
    #通過c把n-1個(gè)盤子移動(dòng)到b
    hanoi(n-1, a,c,b)
    #移動(dòng)最大的盤子
    print(a,'->',c)
    #通過a把n-1個(gè)盤子移動(dòng)到c
    hanoi(n-1, b,a,c)
hanoi(3,'A','B','C')

運(yùn)行結(jié)果：

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

轉(zhuǎn)自https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000/001431756044276a15558a759ec43de8e30eb0ed169fb11000

更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python列表(list)操作技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》

希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。