1. 首頁 > 生活百科 > >

二級結論高中數學 遞歸數列

越眾創業網

遞歸序列(中學結論高中數學)原始數據結構與算法2020-08-10 10:19:13
什么是遞歸？在講遞歸之前，我們先來看看遞歸 。遞歸就是在運行的過程中調用自己 。
遞歸的條件如下:1 。子問題必須與原問題相同，且更簡單；2.你不能無限期地稱呼自己 。必須有出口，簡化為非遞歸條件處理 。
遞歸語言的例子讓我們用兩個故事來解釋什么是遞歸 。
1.從前有座山，山里有座廟，廟里有個老和尚在給小和尚講故事！有什么故事？“從前，有座山，山里有座廟，廟里有個老和尚在給小和尚講故事！有什么故事？從前有座山，山里有座廟，廟里有個老和尚在給小和尚講故事！有什么故事？……'"
2.大雄在自己房間里，用時光電視看往事 。當時在電視畫面中，他在自己的房間里，看著過去的時光電視 。當時的電視屏幕出現在電視屏幕上，他正在自己的房間里，看著時間電視上過去的情形...
遞歸模板我們知道遞歸必須有兩個條件，一個是調用自身，一個是有終止條件 。這兩個條件必須同時滿足，一個都不能少 。并且終止條件必須在遞歸的開始，如下 。
publicvoidrecursion(參數0){if(終止條件){return;}recursion(參數1);}你不能把終止條件寫在遞歸的末尾 。下面的寫法不對 。
publicvoidrecursion(參數0){recursion(參數1);if(終止條件){return;}}在這種情況下，遞歸永遠不會后退，并且會發生StackOverflowError 。
但實際上遞歸可能不止一次調用自己，很多遞歸在調用之前或之后都會有一些邏輯處理，比如下面 。
publicvoidrecursion(參數0){if(終止條件){return;}可能有一些邏輯運算recursion(參數1)可能有一些邏輯運算recursion(參數2)……recursion(參數n)可能有一些邏輯運算}
實例分析我對遞歸的理解是一層一層往下傳，滿足終止條件就會反彈，最終會反彈到調用的地方 。我們拿五個最常見的例子來分析一下 。
1，階乘
我們先來看看最簡單的遞歸調用——階乘 。代碼如下所示
publicintrecursion(intn){if(n==1)return1;returnn*recursion(n-1);5}這種遞歸太熟悉了 。第2-3行是終止條件，第4行是給自己打電話 。我們來畫一個n = 5時的圖，看看遞歸是怎么調用的 。
如果看不清楚，點擊放大圖片 。
這種遞歸還是很簡單的 。當我們找到f(5)時，我們只需要找到f(4) 。如果我們找到f(4)，我們將要求f (3)...，層層調用 。當n=1時，我們會直接返回1，然后逐層返回，直到返回f(5) 。
【二級結論高中數學 遞歸數列】遞歸的目的是將一個大問題細分成更小的子問題 。我們只需要知道遞歸函數的作用，不要一層一層的去想遞歸 。如果同時調用幾次，很可能會陷入循環，出不來 。比如上面問題中需要f(5)，我們只需要計算f(4)，即F(5)= 5 * F(4)；至于f(4)是怎么算出來的，先不說了 。因為我們知道f(n)中的n可以表示任意正整數，所以只需要傳入4就可以計算f(4) 。
2.斐波那契數列
我們再來看另一個經典的遞歸問題，就是斐波那契數列 。該序列的前幾項如下
[1,1,2,3,5,8,13……]
我們參考遞歸模板把它寫下來 。第一個終止條件是當n等于1或2時返回1，即序列的前兩個值為1 。代碼如下所示
publicintfibonacci(intn){if(n==1||n==2)return1;這里是遞歸調用；}遞歸的兩個條件，一個是終止條件，我們已經找到了 。另一種是給自己打電話 。我們知道斐波那契數列的當前值是前兩個值之和，也就是
斐波那契(n)=斐波那契(n - 1) +斐波那契(n - 2)
所以代碼很容易寫 。
//1,1,2,3,5,8,13……publicintfibonacci(intn){if(n==1||n==2)return1;returnfibonacci(n-1)+fibonacci(n-2);}3.河內塔
通過對前兩個例子的分析，我們對遞歸有了一個大致的了解 。再來看另一個例子——河內塔 。其實這個之前已經提過了 。有興趣的可以去河內塔362看看 。
這里簡單說一下漢諾塔的原理，就是有A、B、c三根柱子，A盤在柱子上從上到下從小到大排列 。通過B列將A列上的磁盤全部移動到C列，移動的過程永遠是小盤在上，大盤在下 。讓我們遞歸地解決這個問題 。我們先定義一個函數 。
Public void Hanoi (int n，char a，char b，char c)他的意思是在b的幫助下成功地將n個磁盤從A移動到C 。
我們先來回顧一下遞歸的條件 。一個是終止條件，一個是給自己打電話 。我們先來看遞歸的終止條件，即當n等于1時，也就是A列只有一個磁盤時，我們可以直接把A列的磁盤移到c列 。
//表示的是把n個圓盤借助柱子B成功的從A移動到Cpublicstaticvoidhanoi(intn,charA,charB,charC){if(n==1){//如果只有一個，直接從A移動到C即可System.out.println("從"+A+"移動到"+C);return;}這里是遞歸調用}我們再來看看遞歸調用 。如果n不等于1，我們就要把它分成3步 。

推薦閱讀