遞歸的定義：

遞歸的定義：你打開面前這扇門，看到屋里面還有一扇門。你走過去，發現手中的鑰匙還可以打開它，你推開門，
發現里面還有一扇門，你繼續打開它。若干次之后，你打開面前的門后，發現只有一間屋子，沒有門了。然后，
你開始原路返回，每走回一間屋子，你數一次，走到入口的時候，你可以回答出你到底用這你把鑰匙打開了幾扇門。循環
：你打開面前這扇門，看到屋里面還有一扇門。你走過去，發現手中的鑰匙還可以打開它，你推開門，發現里面還有一扇門（
若前面兩扇門都一樣，那么這扇門和前兩扇門也一樣；如果第二扇門比第一扇門小，那么這扇門也比第二扇門小，你繼續打開這扇門，一
直這樣繼續下去直到打開所有的門。但是，入口處的人始終等不到你回去告訴他答案。上面的比喻形象地闡述了遞歸與循環的內涵，那么我們來思
考以下幾個問題：
什么是遞歸呢？
遞歸的精髓(思想)是什么？
遞歸和循環的區別是什么？
什么時候該用遞歸？
使用遞歸需要注意哪些問題？遞歸思想解決了哪些經典的問題？
這些問題正是筆者準備在本文中詳細闡述的問題。
二. 遞歸的內涵1、定義 (什么是遞歸？)在數學與計算機科學中，遞歸(Recursion)是指在函數
的定義中使用函數自身的方法。實際上，遞歸，顧名思義，其包含了兩個意思：遞 和 歸，這正是遞歸思想的精華所在。
2、遞歸思想的內涵(遞歸的精髓是什么？)正如上面所描述的場
景，遞歸就是有去（遞去）有回（歸來）
，如下圖所示?！坝腥ァ笔侵?#xff1a;遞歸問題必須可以分解為若干個規模較小，與原問題形式相同的子問題，這些子問題可以用相同的解題思路來解決，就
像上面例子中的鑰匙可以打開后面所有門上的鎖一樣；“有回”是指 : 這些問題的演化過程是一個從大到小，由近及遠的過程，并且會有一個明確的終點(臨界點)，一旦到達了這個臨界點，
就不用再往更小、更遠的地方走下去。
最后，從這
個臨界點開始，原路返回到原點，原問題解決。

第一題了解遞歸：

package 第七章遞歸知識講解; /*** 遞歸的定義：你打開面前這扇門，看到屋里面還有一扇門。你走過去，發現手中的鑰匙還可以打開它，你推開門， 發現里面還有一扇門，你繼續打開它。若干次之后，你打開面前的門后，發現只有一間屋子，沒有門了。然后， 你開始原路返回，每走回一間屋子，你數一次，走到入口的時候，你可以回答出你到底用這你把鑰匙打開了幾扇門。循環 ：你打開面前這扇門，看到屋里面還有一扇門。你走過去，發現手中的鑰匙還可以打開它，你推開門，發現里面還有一扇門（ 若前面兩扇門都一樣，那么這扇門和前兩扇門也一樣；如果第二扇門比第一扇門小，那么這扇門也比第二扇門小，你繼續打開這扇門，一 直這樣繼續下去直到打開所有的門。但是，入口處的人始終等不到你回去告訴他答案。上面的比喻形象地闡述了遞歸與循環的內涵，那么我們來思 考以下幾個問題： 什么是遞歸呢？ 遞歸的精髓(思想)是什么？ 遞歸和循環的區別是什么？ 什么時候該用遞歸？ 使用遞歸需要注意哪些問題？遞歸思想解決了哪些經典的問題？ 這些問題正是筆者準備在本文中詳細闡述的問題。 二. 遞歸的內涵1、定義 (什么是遞歸？)在數學與計算機科學中，遞歸(Recursion)是指在函數 的定義中使用函數自身的方法。實際上，遞歸，顧名思義，其包含了兩個意思：遞 和 歸，這正是遞歸思想的精華所在。 2、遞歸思想的內涵(遞歸的精髓是什么？)正如上面所描述的場 景，遞歸就是有去（遞去）有回（歸來） ，如下圖所示。“有去”是指：遞歸問題必須可以分解為若干個規模較小，與原問題形式相同的子問題，這些子問題可以用相同的解題思路來解決，就 像上面例子中的鑰匙可以打開后面所有門上的鎖一樣；“有回”是指 : 這些問題的演化過程是一個從大到小，由近及遠的過程，并且會有一個明確的終點(臨界點)，一旦到達了這個臨界點， 就不用再往更小、更遠的地方走下去。 最后，從這 個臨界點開始，原路返回到原點，原問題解決。* @author MZFAITHDREAM**/ public class 遞歸0 { /*** 什么是遞歸自己調用自己,利用加法。來看看什么是遞歸* @param args*/public static void main(String[] args) {// TODO Auto-generated method stubint n=sum_recursion(1, 3);//1+2+3+4+5+6=21System.out.println(sum_recursion(n, n));/*** @author MZFAITHDREAM* 定義一個- 法*/int m=sum_recursion1(6, 1);System.out.println(sum_recursion1(m, m));}private static int sum_recursion1(int end, int start) {if(end==start) {return start;} return end-sum_recursion1(end-1, start); }private static int sum_recursion(int start,int end) {// TODO Auto-generated method stubif(start==end) {return end;} // 自己調用自己return start+sum_recursion(start+1, end);}}

第二題雙管齊下解決遞歸問題。

package 第七章遞歸知識講解; /*** 第七章第一課* 7.2 雙管齊下解決遞歸問題* 上樓梯問題* @author MZFAITHDREAM**/ public class 遞歸2 {public static void main(String[] args) {System.out.println(f1(39));}//用遞歸public static long f1(int n) {if(n<0) return 0;if(n==0||n==1) return 1;if(n==2) return 2;return f1(n-1)+f1(n-2);}}

第三題企面試題：硬幣表示某個給定數值。

package 第七章遞歸知識講解; /*** 7.4 名企面試題：硬幣表示某個給定數值* 循環中遞歸* @author MZFAITHDREAM** 假設我們有8種不同面值的硬幣｛1，2，5，10，20，50，100，200｝， 用這些硬幣組合夠成一個給定的數值n。例如n=200，那么一種可能的組合 方式為 200 = 3 * 1 + 1＊2 + 1＊5 + 2＊20 + 1 * 50 + 1 * 100. 問總共有多少種可能的組合方式？ 2、華為面試題 1分2分5分三種硬幣，組成已一角/共有多少解法 3.cc150 給出 1 5 10 25 有多少種方法 */ public class 遞歸3 {public static void main(String[] args) {int res=countWays(15);System.out.println(res);}public static int countWays(int n) {//輸入面值if(n<=0) {//如果小于零return 0;}//定義總價 數組面值 下標return countWaysCore(n,new int[] {1,2,5,10,20,50,100,200},7);}//代入private static int countWaysCore(int n,int[]coins,int cur) {if(cur==0) {return 1;}int res=0;//要么不選， 可以選1 2 3 4 for(int i=0;i*coins[cur]<=n;i++) {//100 25 *4 iint shenyu=n-i*coins[cur];//取大的多少個res+=countWaysCore(shenyu,coins,cur-1);//遞歸+}return res; } }

第四題“逐步生成結果”之非數值型問題。

package 第七章遞歸知識講解;import java.util.HashSet; import java.util.Set;/*** 7.5 “逐步生成結果”之非數值型問題* @author MZFAITHDREAM**/ public class 遞歸4 {//遞歸public static Set<String> kuohao1(int m){Set<String> s_M=new HashSet<>(); //因為set可以去重復if(m==1) {s_M.add("()");return s_M;}Set<String> set_m_1=kuohao1(m-1); //調m-1層，添加元素for (String s : set_m_1) {s_M.add("()"+s);s_M.add(s+"()");s_M.add("("+s+")");}return s_M;}//迭代public static Set<String> kuohao2(int m){Set<String> res=new HashSet<>();res.add("()");if(m==1) return res; for (int i = 2; i <=m; i++) {Set<String> res_new=new HashSet<>(); //創建一個新的集合用于存儲上一個集合更新后的結果for (String s : res) { //添加res_new.add("()"+s);res_new.add(s+"()");res_new.add("("+s+")");}res=res_new; //更新集合}return res;}public static void main(String[] args) {Set<String> kuohao1 = kuohao1(8);for (String s : kuohao1) {System.out.print(s+" ");}System.out.println();Set<String> kuohao2 = kuohao2(3);for (String s : kuohao2) {System.out.print(s+" ");}} }

第五題?子集生成

package 第七章遞歸知識講解;import java.util.ArrayList; import java.util.HashSet; import java.util.Set;/*** 7.6 子集生成* @author MZFAITHDREAM* 給定一個數組A和數組的大小int n，請返回A的所有非空子集。**//*** 2的n次方-1* arr目標數組* cur:數組下標1* @author MZFAITHDREAM**/ public class 遞歸6 {public static void main(String[] args) {遞歸6 obj=new 遞歸6();int[] a= {1,2,3};Set<Set<Integer>> subSets=obj.getSubset(a,a.length);System.out.println(subSets);}public Set<Set<Integer>> getSubset(int[] a,int n){return solve(a,n,n-1);}private static Set<Set<Integer>> solve(int[] a, int n, int cur) {/*** 下面是大集合* 對每一個元素 建立集合*/Set<Set<Integer>> newset=new HashSet<>();/*** 判斷*/if(cur==0) {Set<Integer> nil=new HashSet<>();//空集Set<Integer> first=new HashSet<>();//第一個元素first.add(a[0]);newset.add(nil);newset.add(first);return newset;} // 大集合里面Set<Set<Integer>> oldset=solve(a,n,cur-1);for(Set<Integer> set:oldset){//對于每個子集cur下標對應的元素可以加進去也可以不加進去newset.add(set);//保留原樣Set<Integer> clone=(Set<Integer>)((HashSet)set).clone();//拷貝setclone.add(a[cur]);//添加當前元素newset.add(clone);}return newset;}}

第六題子集生成之二進制法。

package 第七章遞歸知識講解;import java.util.HashSet; import java.util.Set;/*** 7.6 子集生成之二進制法* @author MZFAITHDREAM***/ public class 遞歸7 {private static Set<Set<Integer>> newSet;public static void main(String[] args) { // 調用自己定義的方法int [] A= {123,456,789};Set<Set<Integer>> set=new 遞歸7().getSubset(A, A.length);System.out.println(set);}public static Set<Set<Integer>> getSubset(int[] A,int n){return solve(A,n,n-1);}/*** 遞歸增量構造法* @param A* @param n* @param cur* @return */private static Set<Set<Integer>> solve(int[] A, int n, int cur) {if(cur==0) {//處理第一個元素 // nullSet<Integer> nil=new HashSet(); // fistSet<Integer> fist=new HashSet();fist.add(A[0]);newSet.add(nil);newSet.add(fist);try {Set<Set<Integer>> oldSet =getSubset(A, n);} catch (Exception e) {// TODO Auto-generated catch blocke.printStackTrace();}Set<Set<Integer>> newSet =new HashSet();for (Set<Integer> set : newSet) { // 對于每個子集，cur這個元素可以加進去，也可以不加進去newSet.add(set);//保留原樣 // set轉為HashSetSet<Integer>clone= (Set<Integer>) ((HashSet)set).clone(); // 上面是技術克隆 clone.add(A[cur]); //增加元素newSet.add(clone);} return newSet;}return newSet;} }

?7.7 子集生成之二進制法。

package 第七章遞歸知識講解;import java.util.HashSet; import java.util.Set;/*** 7.7 子集生成之二進制法* @author MZFAITHDREAM**2的n次方-1*/ public class 遞歸71 {public static void main(String[] args) {Object[] arr = {1,2,3};Set<Set<Object>> subSets = getSubSets( arr,arr.length-1); subSets.remove(new HashSet<Object>());//移除空集System.out.println(subSets);}/** arr:目標數組* cur:正在操作的數組元素下標 */public static Set<Set<Object>> getSubSets(Object[] arr,int cur) {//當前元素對應的結果,Set<Set<Object>> newSet = new HashSet<Set<Object>>();if(cur == 0) {Set<Object> nil = new HashSet<Object>();//借助空集Set<Object> first = new HashSet<Object>();//只包含第一個元素的子集first.add(arr[cur]);newSet.add(nil);newSet.add(first);return newSet;}//上一個元素的結果Set<Set<Object>> oldSet = getSubSets(arr,cur-1);for (Set<Object> set : oldSet) {newSet.add(set);Set<Object> temp = new HashSet<Object>(set);temp.add(arr[cur]);newSet.add(temp);}return newSet;}/*** //遞推實現:* @param args*/public static void main1(String[] args) {Object[] arr = {"c","d","a"};Set<Set<Object>> subSets = getSubSets( arr,arr.length-1);subSets.remove(new HashSet<Object>());System.out.println(subSets);}/* arr:目標數組* cur:正在操作的數組元素下標 */public static Set<Set<Object>> getSubSets1(Object[] arr,int cur) {//當前元素對應的結果,Set<Set<Object>> res_set = new HashSet<Set<Object>>();res_set.add(new HashSet<Object>());for (Object i : arr) {Set<Set<Object>> tempSet = new HashSet<Set<Object>>();tempSet.addAll(res_set);for (Set<Object> set : res_set) {Set<Object> temp = new HashSet<Object>(set);temp.add(i);tempSet.add(temp);}res_set = tempSet;}return res_set;} }

第八題：全排列（上）

package 第七章遞歸知識講解; import java.util.ArrayList; /*** 7.8 全排列（上）* @author MZFAITHDREAM*給定一個字符串String s = "abc";求s的全排列 遞歸實現: 對于字符串s的全排列可以再s.length()-1的字符串全排列基礎上放左邊,放右邊和放中間幾種方式實現*/ import java.util.HashSet; import java.util.Set;public class 遞歸8 {public static void main(String[] args) {Set<String>res=new 遞歸8().getPermutations("ab");System.out.println(res);System.out.println("----------------------全排列方式------------------------------------");Set<String>re=new 遞歸8().getPermutations1("abc");System.out.println(re);}/*** *全排列* @param str* @return*/public static Set<String> getPermutations1(String str) {//當前元素對應的結果,Set<String> res_set = new HashSet<String>(); // 判斷長度==1if(str.length()==1) {res_set.add(str);return res_set;}//字符串長度-1的全排列Set<String> pre_set =getPermutations1(str.substring(0,str.length()-1));String addStr = str.charAt(str.length()-1)+"";//需要添加的字符串for (String s : pre_set) {//放左邊String tempStr = addStr+s;res_set.add(tempStr);//放右邊tempStr = s+addStr;res_set.add(tempStr);//放中間for (int j = 1; j < s.length(); j++) {tempStr = s.substring(0,j)+addStr+s.substring(j);res_set.add(tempStr);}}return res_set;}/*** 遞推實現:* @param str* @return*/public static Set<String> getPermutations(String str) {//當前元素對應的結果,Set<String> res_set = new HashSet<String>();res_set.add(str.substring(0,1));if(str.length()==1) {return res_set;}for (int i = 1; i < str.length(); i++) {Set<String> tempSet = new HashSet<String>();String addStr = str.substring(i,i+1);for (String s : res_set) {//放左邊String tempStr = addStr+s;tempSet.add(tempStr);//放右邊tempStr = s+addStr;tempSet.add(tempStr);//放中間for (int j = 1; j < s.length(); j++) {tempStr = s.substring(0,j)+addStr+s.substring(j);tempSet.add(tempStr);}}res_set = tempSet;}return res_set;}}

全排列（中）

package 第七章遞歸知識講解;import java.util.HashSet; import java.util.Set;/*** 7.8 全排列（中）* @author MZFAITHDREAM**/ public class 遞歸9 {public static void main(String[] args) {Set<String>res= new 遞歸9().getPermutations("abcdef".toCharArray(),3);System.out.println(res);}private static Set<String> res = new HashSet();;public static Set<String> getPermutations(char[] charArr,int k) {if(k==charArr.length) {res.add(new String(charArr));}for (int i = k; i < charArr.length; i++) {swap(charArr,k,i);getPermutations(charArr,k+1);//將剩余元素一次放在k+1位置swap(charArr,k,i);//還原(回溯)}return res;}static void swap(char[] charArr,int i,int j) {char temp = charArr[i];charArr[i] = charArr[j];charArr[j] = temp;}}

全排列（下)

package 第七章遞歸知識講解; /*** 7.8 全排列（下)* @author MZFAITHDREAM**/ public class 遞歸10 {/*** 前綴法* @param args*/public static void main(String[] args) {permutations("","abc");}final static int k = 5;static int count = 0;public static void permutations(String prefix,String target) {if(prefix.length() == target.length()) {count++;if(count==k) {System.out.println(prefix);System.exit(0);}}for (int i = 0; i < target.length(); i++) {char ch = target.charAt(i);if(!prefix.contains(ch+"")) {permutations(prefix+ch,target);}}}}

?

?

?

總結

以上是生活随笔為你收集整理的第七章递归知识讲解。的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。