遞歸算法思想
特點(diǎn)
- 遞歸過程一般通過函數(shù)或子過程來實(shí)現(xiàn)吴超。
- 遞歸算法在函數(shù)或子過程的內(nèi)部踏施，直接或間接地調(diào)用自己的算法。
- 遞歸算法實(shí)際上是把問題轉(zhuǎn)換成規(guī)陌埃縮小的同類問題的子問題，然后遞歸調(diào)用函數(shù)或子過程來表示問題的解衬横。
注意點(diǎn)
- 遞歸是在過程或函數(shù)中調(diào)用自身的過程裹粤。
- 在使用遞歸策略時(shí)终蒂，必須有一個(gè)明確的遞歸結(jié)束條件蜂林，稱為遞歸出口。
- 遞歸算法通常顯得很簡(jiǎn)潔拇泣，但是運(yùn)行效率較低噪叙，所以一般不提倡用遞歸算法設(shè)計(jì)程序。
- 在遞歸調(diào)用過程中霉翔，系統(tǒng)用棧來存儲(chǔ)每一層的返回點(diǎn)和局部量睁蕾。如果遞歸次數(shù)過多，則容易造成棧溢出债朵，所以一般不提倡用遞歸算法設(shè)計(jì)程序子眶。
斐波那契數(shù)列
遞歸寫法：
def fib_num(n):
num_list = [0, 1]
if n <= 1:
return num_list[n]
return fib_num(n - 1) + fib_num(n - 2)
n = 10
for i in range(n):
print(fib_num(i), end=' ') # 0 1 1 2 3 5 8 13 21 34
Python 特有寫法：
def fib(n):
a, b = 0, 1
while n:
print(a, end=" ")
a, b = b, a + b
n -= 1
fib(10) # 0 1 1 2 3 5 8 13 21 34
漢諾塔問題
i = 1
def move(n, mfrom, mto):
global i
print("第%d步：將%d號(hào)盤子從%s -> %s" % (i, n, mfrom, mto))
i += 1
def hanoi(n, A, B, C):
if n == 1:
move(1, A, C)
else:
hanoi(n - 1, A, C, B)
move(n, A, C)
hanoi(n - 1, B, A , C)
n = 2
hanoi(n, 'A', 'B', 'C')
# 輸出
第1步：將1號(hào)盤子從A -> B
第2步：將2號(hào)盤子從A -> C
第3步：將1號(hào)盤子從B -> C
階乘問題
def fact(n):
if n <= 1:
return 1
else:
return n * fact(n - 1)
n = 5
print(fact(n)) # 120
