Java方法遞歸的形式和常見遞歸算法(方法遞歸結合File類查找文件)

更新時間：2023年02月28日 14:52:52 作者：學全棧的灌湯包

方法遞歸方法直接調用自己或者間接調用自己的形式稱為方法遞歸（ recursion）,遞歸做為一種算法在程序設計語言中廣泛應用,這篇文章主要介紹了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ù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: