【藍橋杯Java_C組·從零開始卷】第七節、遞歸
目錄
遞歸概述
遞歸：
循環：
疑問：
是什么遞歸？
遞歸的精髓(思想)是什么?
遞歸的三要素
1). 明確遞歸終止條件
2). 給出遞歸終止時的處理辦法
3). 提取重復的邏輯，縮小問題規模*
遞歸模型
遞歸基礎案例
遞歸的應用場景
遞歸與循環
經典遞歸問題實戰
階乘
斐波納契數列
回文字符串的判斷
字符串全排列
二分查找
漢諾塔問題
遞歸概述
人理解迭代，神理解遞歸。毋庸置疑地，遞歸確實是一個奇妙的思維方式。對一些簡單的遞歸問題，我們總是驚嘆于遞歸描述問題的能力和編寫代碼的簡潔，但要想真正領悟遞歸的精髓、靈活地運用遞歸思想來解決問題卻并不是一件容易的事情。本文剖析了遞歸的思想內涵，分析了遞歸與循環的聯系與區別，給出了遞歸的應用場景和一些典型應用，并利用遞歸和非遞歸的方式解決了包括階乘、斐波那契數列、漢諾塔、楊輝三角的存取、字符串回文判斷、字符串全排列、二分查找、樹的深度求解在內的八個經典問題。
遞歸：
你打開面前這扇門，看到屋里面還有一扇門。你走過去，發現手中的鑰匙還可以打開它，你推開門，發現里面還有一扇門，你繼續打開它。若干次之后，你打開面前的門后，發現只有一間屋子，沒有門了。然后，你開始原路返回，每走回一間屋子，你數一次，走到入口的時候，你可以回答出你到底用這你把鑰匙打開了幾扇門。
循環：
你打開面前這扇門，看到屋里面還有一扇門。你走過去，發現手中的鑰匙還可以打開它，你推開門，發現里面還有一扇門（若前面兩扇門都一樣，那么這扇門和前兩扇門也一樣；如果第二扇門比第一扇門小，那么這扇門也比第二扇門小，你繼續打開這扇門，一直這樣繼續下去直到打開所有的門。但是，入口處的人始終等不到你回去告訴他答案。
疑問：
什么是遞歸呢？
遞歸的精髓(思想)是什么？
遞歸和循環的區別是什么？
什么時候該用遞歸？
使用遞歸需要注意哪些問題？
遞歸思想解決了哪些經典的問題？
是什么遞歸？
定義
在數學與計算機科學中，遞歸(Recursion)是指在函數的定義中使用函數自身的方法。實際上，遞歸，顧名思義，其包含了兩個意思：遞 和 歸，這正是遞歸思想的精華所在。
遞歸的精髓(思想)是什么?
正如上面所描述的場景，遞歸就是有去（遞去）有回（歸來），如下圖所示。“有去”是指：遞歸問題必須可以分解為若干個規模較小，與原問題形式相同的子問題，這些子問題可以用相同的解題思路來解決，就像上面例子中的鑰匙可以打開后面所有門上的鎖一樣；“有回”是指 : 這些問題的演化過程是一個從大到小，由近及遠的過程，并且會有一個明確的終點(臨界點)，一旦到達了這個臨界點，就不用再往更小、更遠的地方走下去。最后，從這個臨界點開始，原路返回到原點，原問題解決。
更直接地說，遞歸的基本思想就是把規模大的問題轉化為規模小的相似的子問題來解決。特別地，在函數實現時，因為解決大問題的方法和解決小問題的方法往往是同一個方法，所以就產生了函數調用它自身的情況，這也正是遞歸的定義所在。格外重要的是，這個解決問題的函數必須有明確的結束條件，否則就會導致無限遞歸的情況。
用歸納法來理解遞歸
數學都不差的我們，第一反應就是遞歸在數學上的模型是什么，畢竟我們對于問題進行數學建模比起代碼建模拿手多了。觀察遞歸，我們會發現，遞歸的數學模型其實就是 數學歸納法，這個在高中的數列里面是最常用的了，下面回憶一下數學歸納法。
數學歸納法適用于將解決的原問題轉化為解決它的子問題，而它的子問題又變成子問題的子問題，而且我們發現這些問題其實都是一個模型，也就是說存在相同的邏輯歸納處理項。當然有一個是例外的，也就是歸納結束的那一個處理方法不適用于我們的歸納處理項，當然也不能適用，否則我們就無窮歸納了。總的來說，歸納法主要包含以下三個關鍵要素：
步進表達式：問題蛻變成子問題的表達式
結束條件：什么時候可以不再使用步進表達式
直接求解表達式：在結束條件下能夠直接計算返回值的表達式
事實上，這也正是某些數學中的數列問題在利用編程的方式去解決時可以使用遞歸的原因，比如著名的斐波那契數列問題。
遞歸的三要素
在我們了解了遞歸的基本思想及其數學模型之后，我們如何才能寫出一個漂亮的遞歸程序呢？筆者認為主要是把握好如下三個方面：
1、明確遞歸終止條件；
2、給出遞歸終止時的處理辦法；
3、提取重復的邏輯，縮小問題規模。
1). 明確遞歸終止條件
我們知道，遞歸就是有去有回，既然這樣，那么必然應該有一個明確的臨界點，程序一旦到達了這個臨界點，就不用繼續往下遞去而是開始實實在在的歸來。換句話說，該臨界點就是一種簡單情境，可以防止無限遞歸。
2). 給出遞歸終止時的處理辦法
我們剛剛說到，在遞歸的臨界點存在一種簡單情境，在這種簡單情境下，我們應該直接給出問題的解決方案。一般地，在這種情境下，問題的解決方案是直觀的、容易的。
3). 提取重復的邏輯，縮小問題規模*
我們在闡述遞歸思想內涵時談到，遞歸問題必須可以分解為若干個規模較小、與原問題形式相同的子問題，這些子問題可以用相同的解題思路來解決。從程序實現的角度而言，我們需要抽象出一個干凈利落的重復的邏輯，以便使用相同的方式解決子問題。
遞歸模型
在我們明確遞歸算法設計三要素后，接下來就需要著手開始編寫具體的算法了。在編寫算法時，不失一般性，我們給出兩種典型的遞歸算法設計模型，如下所示。
遞歸基礎案例
package Action; public class demo { public static void main(String[] args) { f(10); } public static int f(int i){//參數 System.out.println(i); if (i==0){ // 明確的遞歸終止條件 return 0; // 簡單情景 } else { // 在將問題轉換為子問題的每一步，解決該步中剩余部分的問題 i--; // 遞去 return f(i);// 遞到最深處后，不斷地歸來 } } }
遞歸的應用場景
在我們實際學習工作中，遞歸算法一般用于解決三類問題：
(1). 問題的定義是按遞歸定義的（Fibonacci函數，階乘，…）；
(2). 問題的解法是遞歸的（有些問題只能使用遞歸方法來解決，例如，漢諾塔問題，…）；
(3). 數據結構是遞歸的（鏈表、樹等的操作，包括樹的遍歷，樹的深度，…）。
遞歸與循環
遞歸與循環是兩種不同的解決問題的典型思路。遞歸通常很直白地描述了一個問題的求解過程，因此也是最容易被想到解決方式。循環其實和遞歸具有相同的特性，即做重復任務，但有時使用循環的算法并不會那么清晰地描述解決問題步驟。單從算法設計上看，遞歸和循環并無優劣之別。然而，在實際開發中，因為函數調用的開銷，遞歸常常會帶來性能問題，特別是在求解規模不確定的情況下；而循環因為沒有函數調用開銷，所以效率會比遞歸高。遞歸求解方式和循環求解方式往往可以互換，也就是說，如果用到遞歸的地方可以很方便使用循環替換，而不影響程序的閱讀，那么替換成循環往往是好的。問題的遞歸實現轉換成非遞歸實現一般需要兩步工作：
(1). 自己建立“堆棧(一些局部變量)”來保存這些內容以便代替系統棧，比如樹的三種非遞歸遍歷方式；
(2). 把對遞歸的調用轉變為對循環處理。
特別地，在下文中我們將給出遞歸算法的一些經典應用案例，對于這些案例的實現，我們一般會給出遞歸和非遞歸兩種解決方案，以便讀者體會。
經典遞歸問題實戰
階乘
package Action; public class demo { public static void main(String[] args) { System.out.println(f(10));; } public static long f(int n) { if (n == 1) { // 遞歸終止條件 return 1; // 簡單情景 } return n * f(n - 1); // 相同重復邏輯，縮小問題的規模 } }
斐波納契數列
/**
* Title: 斐波納契數列
*
* Description: 斐波納契數列，又稱黃金分割數列，指的是這樣一個數列：1、1、2、3、5、8、13、21、……
* 在數學上，斐波納契數列以如下被以遞歸的方法定義：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）。
*
* 兩種遞歸解法：經典解法和優化解法
* 兩種非遞歸解法：遞推法和數組法
*
package Action; public class demo { public static void main(String[] args) { System.out.println(f(10)); } public static int f(int n) { if (n == 1 || n == 2) { // 遞歸終止條件 return 1; // 簡單情景 } return f(n - 1) + f(n - 2); // 相同重復邏輯，縮小問題的規模 } }
回文字符串的判斷
回文字符串就是正讀倒讀都一樣的字符串。如”98789”, “abccba”都是回文字符串
package Action; public class demo { public static void main(String[] args) { System.out.println(f("952757259")); } public static boolean f(String s){ int start = 0; int end = s.length()-1; if(end > start){ // 遞歸終止條件:兩個指針相向移動，當start超過end時，完成判斷 if(s.charAt(start) != s.charAt(end)){ return false; }else{ // 遞歸調用，縮小問題的規模 return f(s.substring(start+1).substring(0, end-1)); } } return true; } }
字符串全排列
從字符串數組中每次選取一個元素，作為結果中的第一個元素;然后，對剩余的元素全排列
package Action; public class demo { public static void main(String[] args) { String s="abc"; f(s.toCharArray(),0,s.length()-1); } public static void f(char[] s, int from, int to) { if (s != null && to >= from && to < s.length && from >= 0) { // 邊界條件檢查 if (from == to) { // 遞歸終止條件 System.out.println(s); // 打印結果 } else { for (int i = from; i <= to; i++) { swap(s, i, from); // 交換前綴,作為結果中的第一個元素，然后對剩余的元素全排列 f(s, from + 1, to); // 遞歸調用，縮小問題的規模 swap(s, from, i); // 換回前綴，復原字符數組 } } } } public static void swap(char[] s, int from, int to) { char temp = s[from]; s[from] = s[to]; s[to] = temp; } }
二分查找
package Action; public class demo { /** * @search 返回被查找的數的位置下標 * @param arr 查找的數組 * @param n 是要查找的數 * @param begin 低位 * @param end 高位 * @return */ public static int search(int []arr,int n,int begin ,int end){ int mid=(begin+end)/2; if(n
漢諾塔問題
/**
* Title: 漢諾塔問題
* Description:古代有一個梵塔，塔內有三個座A、B、C，A座上有64個盤子，盤子大小不等，大的在下，小的在上。
* 有一個和尚想把這64個盤子從A座移到C座，但每次只能允許移動一個盤子，并且在移動過程中，3個座上的盤子始終保持大盤在下，
* 小盤在上。在移動過程中可以利用B座。要求輸入層數，運算后輸出每步是如何移動的。
*/
package Action; public class demo { /** * @description 在程序中，我們把最上面的盤子稱為第一個盤子，把最下面的盤子稱為第N個盤子 * @param level：盤子的個數 * @param from 盤子的初始地址 * @param inter 轉移盤子時用于中轉 * @param to 盤子的目的地址 */ public static void moveDish(int level, char from, char inter, char to) { if (level == 1) { // 遞歸終止條件 System.out.println("從" + from + " 移動盤子" + level + " 號到" + to); return; } else { // 遞歸調用：將level-1個盤子從from移到inter(不是一次性移動，每次只能移動一個盤子,其中to用于周轉) moveDish(level - 1, from, to, inter); // 遞歸調用，縮小問題的規模 // 將第level個盤子從A座移到C座 System.out.println("從" + from + " 移動盤子" + level + " 號到" + to); // 遞歸調用：將level-1個盤子從inter移到to,from 用于周轉 moveDish(level - 1, inter, from, to); // 遞歸調用，縮小問題的規模 } } public static void main(String[] args) { int nDisks = 10; moveDish(nDisks, 'A', 'B', 'C'); } }
從A 移動盤子1 號到C
從A 移動盤子2 號到B
從C 移動盤子1 號到B
從A 移動盤子3 號到C
從B 移動盤子1 號到A
從B 移動盤子2 號到C
從A 移動盤子1 號到C
這篇內容對初學者不是很友好，可以慢慢來。
Java 數據結構
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
相關文章
