遞歸及尾遞歸優化

1、遞歸介紹

遞歸簡而言之就是自己調用自己。使用遞歸解決問題的核心就是分析出遞歸的模型，看這個問題能拆分出和自己類似的問題并且有一個遞歸出口。比如最簡單的就5的階乘，可以把它拆分成5*4!，然後求4!又可以調用自己，這種問題顯然可以用遞歸解決，遞歸的出口就是求1！，可以直接傳回1。用Python實作如下：

[python] 

​​view plain​​​

 ​​​copy​​

1. def fact(n):
2. if n==1:
3. return n
4. return n*fact(n - 1);
5. print(fact(5))

2、尾遞歸優化

在上面的求遞歸中，也有一定的缺點，假如說求1000!的階乘，會出現棧溢出的問題，因為在函數執行中，沒調用一個函數都會把目前函數的調用位置和内部變量儲存在棧裡面，由于棧的空間不是無限大（具體棧的最大空間還沒有查找到），假如說調用層數過多，就是出現棧溢出的情況。

這個時候就可以用尾遞歸優化來解決，尾調用的概念非常簡單，一句話就能說清楚，就是指某個函數的最後一步是調用另一個函數。

[python] 

​​view plain​​​

 ​​​copy​​

1. function f(x){
2. return g(x);
3. }

尾遞歸優化後的階乘函數如下：

[python] 

​​view plain​​​

 ​​​copy​​

1. def fact(n):
2. return fact_iter(n,1);
3. def fact_iter(num, product):
4. if num == 1:
5. return product
6. return fact_iter(num - 1, num * product)
7. print(fact(5))
8. print(fact(1000))

尾調用由于是函數的最後一步操作，是以不需要保留外層函數的調用記錄，因為調用位置、内部變量等資訊都不會再用到了。是以尾遞歸優化可以有效的防止棧溢出，但是尾遞歸優化需要編譯器或者解釋器的支援，遺憾的是，大多數程式設計語言沒有針對尾遞歸做優化，Python解釋器也沒有做優化，是以，即使把上面的fact(n)函數改成尾遞歸方式，也會導緻棧溢出。

3、漢諾塔問題

漢諾塔問題也是一個經典的遞歸問題，具體題目就不說了，這裡分析思路。假設hanoi(n, a, b, c)實作把a上的n個盤子移到c上。

當隻有一個盤子時，直接從A移動到C即可

如果有3個盤子，可以這樣：

[cpp] 

​​view plain​​​

 ​​​copy​​

1. # A --> C
2. # A --> B
3. # C --> B
4. # A --> C
5. # B --> A
6. # B --> C
7. # A --> C

如果有很多盤子，我們分析一下該怎麼移動，首先，我們需要把n-1個盤子移動到b中，才可以實作最簡單的一步，把a中最大的盤子移動到c中，具體怎麼轉移到b中後面再讨論。移動最大的盤子後，a和c都可以看成是空的，接下來，把b看成是a，把a看成是b，把a中的n-1個盤子（這裡的n是已經減1的n）移動到b後，又可以移動第二大的盤子。這顯然是一個遞歸問題。

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

那麼怎麼接下來讨論，怎麼把n-1個盤子移動到b，這不又是一個遞歸問題嘛！可以調用它自己呀，隻不過需要把b看成是c，把c看成是b。是以代碼如下：

[python] 

​​view plain​​​

 ​​​copy​​

1. def hanoi(n,a,b,c):
2. #隻有一個盤子，直接移動
3. if n==1:
4. print(a,'->',c)
5. else:
6. #通過c把n-1個盤子移動到b
7. 1, a,c,b)
8. #移動最大的盤子
9. print(a,'->',c)
10. #通過a把n-1個盤子移動到c
11. 1, b,a,c)
12. hanoi(3,'A','B','C')

尾遞歸