Java方法遞歸的形式和常見遞歸算法(方法遞歸結合File類查找文件)
方法遞歸
方法遞歸的形式
什么是方法遞歸?
方法直接調用自己或者間接調用自己的形式稱為方法遞歸( recursion)。
遞歸做為一種算法在程序設計語言中廣泛應用。
遞歸的形式:
直接遞歸:方法自己調用自己。
public static void main(String[] args) { test(); } // 定義一個方法 public static void test() { // 直接遞歸方法內部調用自己 test(); }
間接遞歸:方法調用其他方法,其他方法又回調方法自己。
public static void main(String[] args) { test1(); } public static void test1 () { // 間接遞歸, 方法內部調用其他方法, 其他方法再調用此方法 test2(); } private static void test2() { test1(); }
遞歸存在的問題?
遞歸如果沒有控制好終止,會出現遞歸死循環(huán),導致棧內存溢出現象。
遞歸常見的算法
遞歸案例導學-計算1-n的階乘:
需求:
計算1-n的階乘的結果,使用遞歸思想解決,我們先從數學思維上理解遞歸的流程和核心點。分析:
把一個復雜的問題層層轉化為一個與原問題相似的規(guī)模較小的問題來求解。
假如我們認為存在一個公式是 f(n) = 1234567*…(n-1)*n;
那么公式等價形式就是: f(n) = f(n-1) *n
如果求的是 1-5的階乘 的結果,我們手工應該應該如何應用上述公式計算:
f(5) = f(4) * 5
f(4) = f(3) * 4
f(3) = f(2) * 3
f(2) = f(1) * 2
f(1) = 1當f(1)時作為條件退出遞歸
示例代碼:
public static void main(String[] args) { System.out.println(f(5)); } public static int f(int num) { if (num == 1) { return 1; } else { return num * f(num - 1); } }
遞歸案例導學-計算1-n的和
需求:
計算1-n的和的結果,使用遞歸思想解決,我們先從數學思維上理解遞歸的流程和核心點。分析:
假如我們認為存在一個公式是 f(n) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + …(n-1) + n;
那么公式等價形式就是: f(n) = f(n-1) + n
遞歸的終結點:f(1) = 1
如果求的是 1-5的和 的結果,應該如何計算。
f(5) = f(4) + 5
f(4) = f(3) + 4
f(3) = f(2) + 3
f(2) = f(1) + 2
f(1) = 1
示例代碼:
public static void main(String[] args) { System.out.println(sum(100)); } public static int sum(int num) { if (num == 1) { return 1; } else { return num + sum(num - 1); } }
案例導學-猴子吃桃問題:
猴子第一天摘下若干桃子,當即吃了一半,覺得好不過癮,于是又多吃了一個; 第二天又吃了前天剩余桃子數量的一半,覺得好不過癮,于是又多吃了一個; 以后每天都是吃前天剩余桃子數量的一半,覺得好不過癮,又多吃了一個; 等到第10天的時候發(fā)現桃子只有1個了。
需求:
請問猴子第一天摘了多少個桃子?分析:
整體來看,每一天都是做同一個事件,典型的規(guī)律化問題,考慮遞歸三要素:
遞歸公式(例如第一天桃子的總數用f(n)表示, f(n+1)代表第二天):
f(n) - f(n)/2 - 1 = f(n+1)
變形可得:f(n)= 2f(n+1) + 2
遞歸終結點:f(10) = 1
難點: 使用數學思想, 推導出遞歸公式
示例代碼:
public static void main(String[] args) { System.out.println(foo(1)); } public static int foo(int n) { if (n == 10) { return 1; } else { return 2 * foo(n + 1) + 2; } }
非規(guī)律遞歸案例
在上述的案例中遞歸算法都是針對存在規(guī)律化的遞歸問題。
有很多問題是非規(guī)律化的遞歸問題,比如文件搜索。如何解決?
- 非規(guī)律化遞歸問題自己看著辦,需要流程化的編程思維。
案例導學-文件搜索:
需求:
- 從電腦某一路徑下,搜索出某個文件名稱并輸出絕對路徑。
分析:
- 先定位出的應該是一級文件對象
- 遍歷全部一級文件對象,判斷是否是文件
- 如果是文件,判斷是否是自己想要的
- 如果是文件夾,需要繼續(xù)遞歸進去重復上述過程
示例代碼:
public class RecursionDemo5 { public static void main(String[] args) { findFile("demo2.txt", new File("/Users/chenyq/Documents/file_test")); } /** * @param name 搜索的文件名 * @param dir 搜索的目錄 * @return */ public static void findFile(String name, File dir) { // 判斷目錄是否為空 if (dir != null && dir.isDirectory()) { // 獲取目錄下的一級文件數組 File[] files = dir.listFiles(); // 判斷數組是否有內容 if (files != null && files.length > 0) { // 不為空則遍歷數組 for (File file : files) { // 判斷是文件還是文件夾 if (file.isFile()) { // 判斷當前文件是否是要查找的文件 if (file.getName().contains(name)) { System.out.println("文件路徑是: " + file.getAbsolutePath()); return; } } else { // 遞歸查找子目錄 findFile(name, file); } } } } else { System.out.println("請輸入正確的目錄!"); } } }
到此這篇關于Java方法遞歸的形式和常見遞歸算法-方法遞歸結合File類查找文件的文章就介紹到這了,更多相關Java方法遞歸和算法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
Java Class.forName()用法和newInstance()方法原理解析
這篇文章主要介紹了Java Class.forName()用法和newInstance()方法原理解析,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-08-08Java報錯:Error:java:?程序包org.springframework.boot不存在解決辦法
建完springboot項目時,點擊啟動,有可能會報錯,下面這篇文章主要給大家介紹了關于Java報錯:Error:java:?程序包org.springframework.boot不存在的解決辦法,需要的朋友可以參考下2024-02-02IDEA調試源碼小技巧之辨別抽象類或接口多種實現類的正確路徑
這篇文章主要介紹了IDEA調試源碼小技巧之辨別抽象類或接口多種實現類的正確路徑,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-01-01SpringBoot整合Log4j2實現自定義日志打印失效的原因及解決
本文給大家介紹了關于SpringBoot項目整合Log4j2實現自定義日志打印失效原因及解決辦法,主要的原因是因為SpringBoot的logback包的存在,文中通過圖文給大家了詳細解決方法,需要的朋友可以參考下2024-01-01Java設計模式之狀態(tài)模式State Pattern詳解
這篇文章主要介紹了Java設計模式之狀態(tài)模式State Pattern,狀態(tài)模式允許一個對象在其內部狀態(tài)改變的時候改變其行為。這個對象看上去就像是改變了它的類一樣2022-11-11