文章目录

• • 方法递归
  • • 方法递归的形式
    • 递归常见的算法
    • 非规律递归案例

方法递归

方法递归的形式

什么是方法递归?

方法直接调用自己或者间接调用自己的形式称为方法递归（ 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();
}

递归存在的问题?

递归如果没有控制好终止，会出现递归死循环，导致栈内存溢出现象。

递归常见的算法

递归案例导学-计算1-n的阶乘:

需求：

• 计算1-n的阶乘的结果，使用递归思想解决，我们先从数学思维上理解递归的流程和核心点。

分析:

• 把一个复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。

• 假如我们认为存在一个公式是 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天的时候发现桃子只有1个了。

需求：

• 请问猴子第一天摘了多少个桃子？

分析:

• 整体来看，每一天都是做同一个事件，典型的规律化问题，考虑递归三要素：

• 递归公式(例如第一天桃子的总数用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;
    }
}

非规律递归案例

在上述的案例中递归算法都是针对存在规律化的递归问题。

有很多问题是非规律化的递归问题，比如文件搜索。如何解决？

• 非规律化递归问题自己看着办，需要流程化的编程思维。

案例导学-文件搜索:

需求:

• 从电脑某一路径下，搜索出某个文件名称并输出绝对路径。

分析:

• 先定位出的应该是一级文件对象
• 遍历全部一级文件对象，判断是否是文件
• 如果是文件，判断是否是自己想要的
• 如果是文件夹，需要继续递归进去重复上述过程

示例代码:

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("请输入正确的目录!");
        }
    }
}