java 递归_Java的递归、如何与流相结合
遞歸技術
需求:掃描D:est所有子文件夾及子子文件夾下的.jpg文件。
我們如果用循環來做這件事,我們不知道循環的結束條件,也不知道到底有多少層,所以比較麻煩。
我們可以用一種新的思想:遞歸。
遞歸舉例:
從前有一座山,山里有座廟,廟里有個老和尚,老和尚在給小和尚講故事:
從前有一座山,山里有座廟,廟里有個老和尚,老和尚在給小和尚講故事:
從前有一座山,山里有座廟,廟里有個老和尚,老和尚在給小和尚講故事:
。。。。。。。
故事如何才能結束:小和尚還俗了。廟塌了。山崩了。
Java中的遞歸:
在方法的函數體中又調用了方法自己本身。
遞歸調用的細節:必須要求遞歸中有可以讓函數調用的結束條件。否則函數一直調用,就會導致內存溢出。
遞歸演示
練習1:需求:計算1~5的和值,不許使用循環。
分析和步驟:
1)定義一個DiGuiDemo測試類;
2)在這個類中的main函數中調用自定義函數,5作為函數的參數,使用一個變量sum來接收返回的和值,并輸出和值sum;
3)自定義add()函數接收傳遞的參數5;
4)在自定義函數中書寫if語句判斷i是否大于1,如果大于1,則使用return返回i+add(i-1);
5)否則i<=1時,返回1;
package cn.xuexi.digui.demo;/* * 練習1:需求:計算1~5的和值,不許使用循環。 * 遞歸演示 */public class DiGuiDemo { public static void main(String[] args) { //調用自定義函數求1~5之間的和值 int sum=add(5); System.out.println(sum); } /* * 自定義函數求1~5之間的和值 * 5+4+3+2+1 */ public static int add(int n) { /* * 判斷n是否大于1 */ if(n>1) { //這里的add函數調用了函數自己本身的做法就是函數的遞歸調用 return n+add(n-1); } //返回1作為遞歸的結束條件 return 1; }}上述代碼圖解如下圖所示:
1.png
練習2:需求:求5的階乘!!
分析:
普及一下數學知識:
方式1:5! = 5 * 4 * 3 * 2 * 1 = 120;
方式1 循環方式:
代碼如下所示:
步驟:
1)定義一個DiGuiDemo2測試類;
2)在這個類中的main函數中調用自定義函數jc(),5作為函數的參數,使用一個變量result來接收返回的階乘的值,并輸出結果result;
3)自定義jc()函數接收傳遞的參數5;
4)在自定義函數中定義一個變量result=1,使用for循環來實現方式1求階乘的結果,并返回result階乘的值;
package cn.xuexi.digui.demo;/* * 練習2:需求:求5的階乘!! * 方式1:5!=5*4*3*2*1=120 */public class DiGuiDemo2 { public static void main(String[] args) { int result=jc(5); //輸出階乘后的結果 System.out.println(result);//120 } //使用方式一來求5的階乘 public static int jc(int n) { //定義 一個變量來接收階乘后的結果 int result =1; for (int i = 2; i <= n; i++) { result=result*i; } return result; }}方式2:使用遞歸思想來完成
5! = 5 * 4! 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 1! 1! = 1*0!找規律:n! = n * (n-1)!
補充:0!等于1
結束條件:if(n <= 1) return 1;
方式2 遞歸方式:
代碼如下所示:
步驟:
1)定義一個DiGuiDemo3測試類;
2)在這個類中的main函數中調用自定義函數jc2(),5作為函數的參數,使用一個變量result來接收返回的階乘的值,并輸出結果result;
3)自定義jc2()函數接收傳遞的參數5;
4)在自定義函數中書寫if語句判斷n是否小于等于1,如果小于等于1,則使用return返回1;
5)否則n>1時,使用return返回n * jc2(n - 1);
package cn.xuexi.digui.demo;/* * 方式2:使用遞歸思想來解決5的階乘 *方式一: 5!=5*4*3*2*1; *方式二:5!=5*4! * 4!=4*3! * 3!=3*2! * 2!=2*1! * 1!=1*0! *找規律:n!=n*(n-1)! *找結束條件: * if(n<=1) return 1; */public class DiGuiDemo3 { public static void main(String[] args) { // 調用函數求5的階乘 int result=jc2(5); System.out.println(result);//120 } //自定義函數求5的階乘 public static int jc2(int n) { // 結束條件 if(n<=1) { return 1; } return n*jc2(n-1); }}上述代碼內存圖解如下所示:
2.png
遞歸注意事項
1)遞歸必須有結束條件,否則棧內存會溢出,稱為死遞歸!棧炸了。
3.png
棧內存溢出報的異常如下所示:
4.png
2)遞歸次數不能太多,否則棧溢出。炸了
5.png
棧內存溢出報的異常如下所示:
6.png
3)構造函數不能遞歸,內存溢出,編譯直接報錯。
7.png
總結:遞歸容器容易導致內存溢出。即使遞歸調用中有結束條件,但是如果遞歸的次數太多,也會發生內存溢出。
所以在開發中使用函數的遞歸調用時需謹慎。
遞歸練習
斐波那契數列或者叫做黃金分割數列或者叫做兔子數列:
不死神兔問題:有1對兔子,從出生的第3個月開始,每個月都生1對兔子,假如兔子都不死,問第n個月有幾對兔子。
斐波那契數列思想的圖解如下圖所示:
8.png
斐波那契數列思想如下所示:
找規律:
月份(n): 1 2 3 4 5 6 7 8 9 10 .....
兔子對數(f): 1 1 2 3 5 8 13 21 34 55 .....
f(n) = f(n-1) + f(n-2)
找出口:
if(n <= 2) return 1;
代碼實現如下所示:
分析和步驟:
1)定義一個測試類DiguiDemo4 ;
2)在DiguiDemo4類中調用自定義函數countRabbits(),指定月份作為參數,就是想看第幾個月有多少對兔子,使用一個整數變量接收返回來的兔子的對數num,輸出打印結果;
3)自定義函數countRabbits()根據用戶指定的月份輸出對應月份的兔子的對數;
4)使用判斷結構判斷月份n是否小于等于2,如果是返回1對;
5)如果月份大于2,分別遞歸調用函數countRabbits(n-1)+countRabbits(n-2),并將兔子的對數返回給調用者;
package cn.xuexi.digui.demo;/* * 遞歸練習,斐波那契數列 * 月份 : 1 2 3 4 5 6 7 8 9 10.。。。 * 兔子對數: 1 1 2 3 5 8 13 21 34 55.。。。 * 求第n個月的兔子對數 */public class DiGuiDemo4 { public static void main(String[] args) { // 定義一個函數計算兔子的對數 int num=countRabbits(6);//6表示月份 //輸出第n個月兔子的對數 System.out.println(num); } //自定義函數統計第n個月兔子的對數 public static int countRabbits(int n) //n表示月份 { // 結束條件 if(n<=2) { return 1; } //規律 return countRabbits(n-1)+countRabbits(n-2); }}綜合練習
練習1:掃描D:est所有子文件夾及子子文件夾下的.jpg文件,輸出其絕對路徑
需求:掃描D:est所有子文件夾及子子文件夾下的.jpg文件,輸出其絕對路徑。
分析:
首先我們可以拿到D:est下的所有兒子,我們判斷兒子是不是文件夾,如果是,再次掃描兒子的文件夾,然后獲取兒子下面的所有子文件和子文件夾,即就是D:est的孫子,然后我們再判斷孫子是不是文件夾等等,以此類推,最后我們輸出其絕對路徑;
思路:
A:封裝父目錄的File對象;
B:獲取父目錄下的所有兒子的File數組;
C:循環遍歷,獲取每個兒子;
D:判斷是否是文件夾
是:回到步驟B 繼續獲取孫子
否:判斷是否是.jpg 結束遞歸的條件
是:打印
否:不管
我們發現:B到D的過程是不斷重復。我們可以封裝成遞歸的函數。
步驟:
1)創建測試類FileTest1;
2)在FileTest1類的main函數中封裝父目錄D:est的對象parent;
3)調用遞歸掃描的函數scanFolders(parent);
4)自定義函數scanFolders(),使用父目錄對象parent調用listFiles()函數獲得父目錄下所有兒子的File數組files;
5)循環遍歷,獲取每個兒子對象file;
6)使用file對象調用isDirectory()函數判斷是否是文件夾;
7)如果是文件夾,則遞歸調用scanFolders(file)函數;
8)如果不是文件夾,肯定是文件,使用file對象調用getName()函數獲得文件的全名,調用endsWith()函數判斷后綴名是否是.jpg,如果是輸出文件所屬的絕對路徑;
package cn.xuexi.file.test;import java.io.File;/* * 需求:掃描D:est所有子文件及子子文件下的.jpg文件,輸出其絕對路徑。 * 思路: * A:創建父目錄 * B:調用函數查找文件或者文件夾 * C:通過父目錄對象調用函數獲取所有兒子的File數組 * D:循環遍歷所有的兒子,dir表示父目錄D:est的每一個兒子 * a:判斷獲取的兒子dir是否是文件夾 如果是 執行步驟B * b:不是,判斷后綴名是否是.jpg,是,輸出絕對路徑 * * 我們發現:B到D的過程是不斷重復。我們可以封裝成遞歸的函數。 */public class FileTest1 { public static void main(String[] args) { //封裝父目錄的對象 File parent = new File("D:est"); //調用函數查找文件或者文件夾 scanFolderAndFile(parent); } //自定義函數掃描文件或者文件夾 public static void scanFolderAndFile(File parent) { //通過父目錄對象調用函數獲取所有兒子的File數組 File[] dirs = parent.listFiles(); //循環遍歷所有的兒子,dir表示父目錄D:est的每一個兒子 for (File dir : dirs) { /* * 判斷獲取的兒子dir是否是文件夾 * 如果是文件夾,那么繼續掃描或者查找兒子下面的所有文件或者文件夾 * 以此類推 * 如果不是文件夾,那么肯定是文件,判斷后綴名是否是.jpg * 如果是.jpg 則輸出其絕對路徑 */ if(dir.isDirectory()) { //說明是文件夾 繼續找兒子下面的文件或者文件夾 執行掃描函數 scanFolderAndFile(dir); }else { /* * 說明不是文件夾,是文件,我們判斷是否是.jpg * dir.getName()表示獲取文件的名字 mm.jpg */ if(dir.getName().endsWith(".jpg")) { //說明文件的后綴名是.jpg 輸出其絕對路徑 System.out.println(dir.getAbsolutePath()); } } } }}帶健壯性的代碼:
上述代碼不安全,
1)比如在調用scanFolders(parent)函數時,如果parent變成null,那么scanFolders(File parent) 接收參數時,parent也為null,就會報空指針異常;
判斷parent是否為null,如果為null就拋異常;
2)比如創建父目錄對象時,指定的父目錄在計算機中不存在,那么拋異常;
使用parent對象調用exit()函數判斷創建的文件夾是否存在,如果不存在,則拋異常。
3)比如創建父目錄對象時,指定的父目錄是文件,那么拋異常;
使用parent對象調用isFile()函數,如果是文件,則拋異常。
說明:除了上述三個問題,其他代碼和上述代碼一樣。
代碼如下:
//自定義函數掃描文件夾 public static void scanFolderAndFile(File parent) { //判斷parent是否為null if(parent==null) { throw new RuntimeException("不能傳遞null"); } //判斷文件夾是否存在 if(!parent.exists()) { throw new RuntimeException("文件夾不存在"); } //傳遞的是文件夾,不能是文件 if(parent.isFile()) { throw new RuntimeException("只能是文件夾"); } // 獲取父目錄下面的所有兒子 File[] files = parent.listFiles(); //遍歷上述數組 for (File file : files) { /* * 如果file對象中封裝的是文件夾,那么可以把此文件夾當成父類 * 在掃描其下面的兒子 */ if(file.isDirectory()) { //說明獲得的是文件夾 再次回到scanFolderAndFile()函數處執行該函數 scanFolderAndFile(file); }else { /* * 說明file中封裝的是文件 * 獲得文件名字,然后判斷后綴名是否是.jpg * 如果是,則獲取絕對路徑 */ boolean boo = file.getName().endsWith(".jpg"); if(boo) { //說明后綴名是.jpg的文件 輸出絕對路徑 System.out.println(file.getAbsolutePath()); } } } }練習2:使用過濾器實現練習
演示:需求:掃描D:est所有子文件夾及子子文件夾下的.jpg文件,輸出其絕對路徑。
要求:使用過濾器實現。
思路:
A:創建父目錄的File對象
B:獲取父目錄下的符合條件的兒子
條件是什么?
可以是文件夾 也可以是.jpg文件
C:循環遍歷,取出每個兒子
取出的兒子有兩種情況:文件夾、.jpg文件
D:判斷是否是文件夾
是:回到B
否:打印
B到D封裝成遞歸函數
步驟:
1)創建測試類FileTest2;
2)在FileTest2類的main函數中封裝父目錄D:est的對象parent;
3)調用遞歸掃描的函數scanFolders(parent);
4)自定義函數scanFolders(),使用父目錄對象parent調用listFiles(new FileFilter())函數獲得父目錄下所有兒子的File數組files;
5)使用過濾器FileFilter接口的匿名內部類作為listFiles()函數的參數,匿名內部類實現accept函數;
6在accept函數體中使用父目錄的兒子對象調用isDirectory()函數和getName().endsWith(".jpg")函數來判斷父目錄 的兒子是否是文件夾或者后綴名是.jpg的文件;
7)使用判斷結構判斷files數組是否有文件或者文件夾;
8)如果有,則循環遍歷數組files;
9)使用file對象調用isDirectory()函數判斷是否是文件夾;
10)如果是文件夾,則遞歸調用scanFolders(file)函數;
11)如果不是文件夾,肯定是文件,使用file對象調用getName()函數獲得文件的全名,調用endsWith()函數判斷后綴名是否是.jpg,如果是輸出文件所屬的絕對路徑;
package cn.xuexi.file.test;import java.io.File;import java.io.FileFilter;/* * 思路: A:創建父目錄的File對象 B:獲取父目錄下的符合條件的兒子 條件是什么? 可以是文件夾 也可以是.jpg文件 C:循環遍歷,取出每個兒子 取出的兒子有兩種情況:文件夾、.jpg文件 D:判斷是否是文件夾 是:回到B 否:打印 B到D封裝成遞歸函數 */public class FileTest3 { public static void main(String[] args) { // 封裝父目錄的對象 File parent = new File("D:est"); // 調用函數查找文件或者文件夾 scanFolderAndFile(parent); } public static void scanFolderAndFile(File parent) { // 獲取父目錄下的符合條件的兒子 這里需要使用過濾器 File[] files=parent.listFiles(new FileFilter() { public boolean accept(File pathname) { // 條件是文件夾或者后綴名是.jpg的文件 return pathname.isDirectory() || pathname.getName().endsWith(".jpg"); } }); //循環遍歷,取出每個兒子 for (File file : files) {// 判斷是否是文件夾 if(file.isDirectory()) { //遞歸調用函數 scanFolderAndFile(file); }else { System.out.println(file.getAbsolutePath()); } } }}總結
以上是生活随笔為你收集整理的java 递归_Java的递归、如何与流相结合的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: java des加密解密_JAVA和c#
- 下一篇: serializable接口_Java