一、遞歸練習

1、上樓梯？（每次都過一下題目，感覺還是沒理解透徹）

image.png

image.png

2、漢諾塔（Hanoi）？

image.png

image.png

• 補充一個小插曲，如何判斷遞歸基是要寫一個還是兩個？
• 如果遞歸里面有 n-1 和 n-2，那么遞歸基就需要 if(n < 2)的情況；
• 如果遞歸里面只有 n-1，那么遞歸基只要判斷 n==1 的情況；

3、漢諾塔的時間復雜度和空間復雜度是多少？

image.png

4、遞歸函數(shù)的調(diào)用棧情況是怎么樣的（腦海中要有個大概）？遞歸能轉(zhuǎn)換成非遞歸嗎？

image.png

5、遞歸轉(zhuǎn)非遞歸的萬能之法是什么？

• 遞歸轉(zhuǎn)非遞歸的萬能之法
• 自己維護一個棧，來保存參數(shù)、局部變量
• 但是空間復雜度依然沒有得到優(yōu)化

image.png

6、從上述自定義棧幀思想，我們可以看出遞歸轉(zhuǎn)非遞歸的核心在什么（細細品味，優(yōu)化方向問題，很重要）？

• 核心：盡量做到使用一組相同的變量來保存每個棧幀的內(nèi)容

image.png

二、尾調(diào)用

1、什么是尾調(diào)用？什么是尾遞歸？

image.png

image.png

2、對于尾調(diào)用，編譯器如果要進行優(yōu)化，需要什么技術(shù)支持？尾調(diào)用能被優(yōu)化的原因是什么？

• 對于尾調(diào)用，編譯器如果要進行優(yōu)化，需要 能動態(tài)修改棧幀的長度
• 尾調(diào)用能被優(yōu)化，是因為尾調(diào)用的函數(shù)，不在使用當前棧幀的局部變量了，所以可以重復利用棧幀

3、為什么尾遞歸的優(yōu)化比尾調(diào)用簡單多了？要能簡述尾遞歸優(yōu)化思路？

image.png

• 下圖是未進行尾遞歸優(yōu)化的匯編

image.png

• 下圖進行尾調(diào)用優(yōu)化后的匯編代碼

image.png

4、使用尾遞歸的思想優(yōu)化斐波那契數(shù)列（了解即可）？

image.png

三、回溯（Back Tracking）

1、回溯（Back Tracking）的思想是什么？之前學過的什么搜索是典型的回溯應用？

image.png

2、八皇后問題描述？

image.png

3、八皇后解決思路？

image.png

4、 使用回溯法解決此問題的思路？（太神奇、太強了?。?/h4>

image.png

image.png

image.png

image.png