递归算法

2023-07-16 05:48| 来源: 网络整理| 查看: 265

声明：根据观看【北京尚学堂高淇】视频整理！

递归算法

递归的基本思想就是“自己调用自己”。递归算法可以决解决复杂问题，如：斐波那契数列的计算、汉诺塔、快排等问题

【实例测试递归】

public class TestRecursion { static void a() { System.out.println("a"); a(); //调用自身方法 } public static void main(String[] args) { a(); } }

【执行结果】递归算法

说明：上诉的a方法中，a不断循环往复的调用自身的方法，不断输出a，当方法还没结束还在继续调用自身的方法，不断的开辟空间，程序一旦被a占满则会发生异常。所以递归算法要有递归体和递归头，见下例。

定义递归头：什么时候不调用自身的方法，若无递归头会进入死循环递归体：什么时候需要调用自身方法

【实例测试递归头和递归体】

public class TestRecursion { //int i = 0;编译错误，在静态方法中调用，参数要为静态。 static int i = 0; static void a() { System.out.println("a"); i++; //递归体（什么时候需要调用自身的方法） if(i return; //结束方法 } } public static void main(String[] args) { a(); } }

【执行结果】

打印了10个a

注意： return除了可以返回值外，还可以结束方法

自主练习：求10的阶乘

//递归算法实现5的阶乘 public class TestRecursion { public static long factorial(int n) { if(n == 1) { //递归头 return 1; }else { //递归体 return n*factorial(n-1); //n！= n*(n-1)! } } public static void main(String[] args) { System.out.println("5的阶乘：" + factorial(5)); } }

【执行结果】

5的阶乘：120

【分析图】递归分析图

自主练习：使用递归打印目录树

import java.io.File; /** * 测试利用递归打印目录树 * @author 懒惰的小黑 * */ public class TestRecursionFile { static void getFile(File f) { System.out.println(f.getName()); //通过递归打印指定目录下的所有文件夹和文件 //递归体 if(f.isDirectory()) { //判断当前File对象是否是目录 File[] files = f.listFiles(); //把路径的所有文件和文件夹存放在File数组上（可查看listFiles源码） for(File temp:files) { getFile(temp); //调用自身方法 } } } public static void main(String[] args) { File f = new File("D:\\学习\\java"); getFile(f); //第一次调默认为0，再调用时+1 } }

【执行结果】

打印File对象目录下的所有文件夹和文件

说明：判断File对象f是否是目录，通过遍历递归获取每一层File对象目录下的所有文件夹和文件（其实存放在File数组中）。

注意：递归调用会占用大量的堆栈内存，内存消耗多，比循环语句慢的多，所以使用递归要看具体情况分析！

【本文地址】

公司简介

联系我们