Java中的方法递归
目录
一、方法递归的形式
1、什么是方法递归？
2、递归的形式
3、方法递归存在的问题？
4、递归的形式（demo）（直接递归与间接递归的代码展示）
二、方法递归的应用、执行流程、递归算法的三个核心要素
1、需求
2、分析
3、在内存中的执行流程
4、代码
5、实现结果
6、递归算法三要素
四、方法递归的经典案例
案例一：
1、需求
2、分析
3、代码
4、结果
案例二：
1、需求
2、分析
3、代码
4、结果
五、其他形式的方法递归案例
案例一
1、需求
2、分析
3、代码
案例二
一、方法递归的形式
1、什么是方法递归？
递归做为一种算法在程序设计语言中广泛应用。
方法调用自身的形式称为方法递归 （recursion）。
2、递归的形式
直接递归：方法自己调用自己。
间接递归：方法调用其他方法，其他方法又回调方法自己。
3、方法递归存在的问题？
递归如果没有控制好终止，会出现递归死循环，导致栈内存溢出现象。
4、递归的形式（demo）（直接递归与间接递归的代码展示）
public static void main(String[] args) {test2();}public static void test(){System.out.println("==========test被执行=============");test(); //方法递归 直接递归}public static void test2(){System.out.println("==========test2被执行=============");test3(); //方法递归 间接递归}public static void test3(){System.out.println("==========test3被执行=============");test2();}二、方法递归的应用、执行流程、递归算法的三个核心要素
1、需求
计算1-n的阶乘的结果，使用递归思想解决，我们先从数学思维上理解递归的应用和核心点。
2、分析
2.1、假如我们认为存在一个公式是 f(n) = 1*2*3*4*5*6*7*…(n-1)*n;
2.2、那么公式等价形式就是： f(n) = f(n-1) *n
2.3、如果求的是 1-5的阶乘 的结果，我们手工应该应该如何应用上述公式计算。
2.4、f(5) = f(4) * 5
f(4) = f(3) * 4
f(3) = f(2) * 3
f(2) = f(1) * 2
f(1) = 1
3、在内存中的执行流程
1、
2、
3、
4、
5、
6、
7、
8、
4、代码
public static void main(String[] args) {System.out.println(f(5));}public static int f(int n){if (n == 1){return 1;}else {return f(n-1) * n;}}5、实现结果
6、递归算法三要素
6.1、递归的公式： f(n) = f(n-1) * n;
6.2、递归的终结点：f(1)
6.3、递归的方向必须走向终结点：
f(5) = f(4) * 5
f(4) = f(3) * 4
f(3) = f(2) * 3
f(2) = f(1) * 2
f(1) = 1
四、方法递归的经典案例
案例一：
1、需求
计算1-n的和的结果，使用递归思想解决！！！
2、分析
1、假如我们认为存在一个公式是 f(n) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + …(n-1) + n;
2、那么公式等价形式就是： f(n) = f(n-1) + n
3、递归的终结点：f(1) = 1
4、如果求的是 1-5的和 的结果，应该如何计算。
5、 f(5) = f(4) + 5
f(4) = f(3) + 4
f(3) = f(2) + 3
f(2) = f(1) + 2
f(1) = 1
3、代码
public static void main(String[] args) {System.out.println(f(5));}public static int f(int n){if (n == 1){return 1;}else {return f(n-1) + n;}}4、结果
案例二：
1、需求
猴子第一天摘下若干桃子，当即吃了一半，觉得好不过瘾，于是又多吃了一个 第二天又吃了前天剩余桃子数量的一半，觉得好不过瘾，于是又多吃了一个 以后每天都是吃前天剩余桃子数量的一半，觉得好不过瘾，又多吃了一个 等到第10天的时候发现桃子只有1个了。请问猴子第一天摘了多少个桃子？
2、分析
2.1、整体来看，每一天都是做同一个事件，典型的规律化问题，考虑递归三要素：
2.2、递归公式：
2.3、递归终结点：
2.4、递归方向：
3、代码
public static void main(String[] args) {System.out.println(f(1));}public static int f(int n){if (n == 10){return 1;}else {return 2*f(n+1) + 2;}}4、结果
五、其他形式的方法递归案例
案例一
1、需求
文件搜索、从C:盘中，搜索出某个文件名称并输出绝对路径。
2、分析
先定位出的应该是一级文件对象
遍历全部一级文件对象，判断是否是文件
如果是文件，判断是否是自己想要的
如果是文件夹，需要继续递归进去重复上述过程
3、代码
public static void main(String[] args) {//2、传入目录 和 文件名称searchFile(new File("E:/"),"FoxitPDFReader.exe");}//1、搜索某个目录下的全部文件，找到我们想要的文件。/*** 1、搜索某个文件目录下的全部文件，找到我们想要的文件* @param dir 被搜索的源文件* @param fileName 被搜索的文件名称*/public static void searchFile(File dir,String fileName){//3、判断dir是否是目录if (dir != null && dir.isDirectory()){//可以找了//4、提取当前目录下的一级文件对象File[] files = dir.listFiles(); //null []//5、判断是否存在一级文件对象，存在才可以遍历if (files != null && files.length > 0){for (File file : files) {//6、判断当前遍历的一级文件对象是文件 还是目录if (file.isFile()){//判断是不是我们要找的，是把其路径输出即可if (file.getName().contains(fileName)){System.out.println("找到了:"+file.getAbsolutePath());//启动它
// try {
// Runtime r = Runtime.getRuntime();
// r.exec(file.getAbsolutePath());
// } catch (IOException e) {
// e.printStackTrace();
// }}}else {//是文件夹，继续递归查找searchFile(file,fileName);}}}}else {System.out.println("对不起，当前搜索的位置不是文件夹！");}}案例二
1、需求
啤酒2元1瓶，4个盖子可以换一瓶，2个空瓶可以换一瓶， 请问10元钱可以喝多少瓶酒，剩余多少空瓶和盖子。
2、答案
15瓶 3盖子 1瓶子
3、代码
public class RecursionDemo06 {//定义一个静态的成员变量用于存储可以买的酒的数量public static int totalNumber;//总数量public static int lastBottleNumber;//记录每次剩余的瓶子的个数public static int lastCoverNumber;//记录每次剩余的盖子的个数public static void main(String[] args) {//1、拿钱买酒buy(10);System.out.println("总数量："+ totalNumber);System.out.println("剩余瓶子个数："+lastBottleNumber);System.out.println("剩余盖子个数："+ lastCoverNumber);}public static void buy(int money){//2、看可以立马买多少瓶int buyNumber = money/2; //5totalNumber += buyNumber;//3、把盖子 和 瓶子换算成钱//统计本轮总的盖子数 和瓶子数int bottleNumber = lastBottleNumber + buyNumber;int coverNumber = lastCoverNumber + buyNumber;//统计换算成钱int allmoney = 0;//瓶子换钱if (bottleNumber >= 2){allmoney += (bottleNumber/2)*2;}lastBottleNumber = bottleNumber % 2;//盖子换钱if (coverNumber >= 4){allmoney += (coverNumber/4)*2;}lastCoverNumber = coverNumber % 4;if (allmoney >= 2){buy(allmoney);}}
}4、结果
