软件网站开发平台,开发软件的工具,html菜鸟教程视频,wordpress注册邮件接收不到邮件递归方法调用 #xff1a;方法自己调用自己的现象就称为递归。 递归的分类 : 直接递归、间接递归。 直接递归#xff1a;方法自身调用自己 public void methodA (){ methodA (); } 间接递归#xff1a;可以理解为A()方法调用B()方法#xff0c;B()方法调用C()方法方法自己调用自己的现象就称为递归。 递归的分类 : 直接递归、间接递归。 直接递归方法自身调用自己 public void methodA (){ methodA (); } 间接递归可以理解为A()方法调用B()方法B()方法调用C()方法C()方法调用A()方法。 public static void A (){ B (); } public static void B (){ C (); } public static void C (){ A (); } 说明 递归方法包含了一种 隐式的循环 。 递归方法会 重复执行 某段代码但这种重复执行无须循环控制。 递归一定要向 已知方向 递归否则这种递归就变成了无穷递归停不下来类似于 死循环 。最终 发生 栈内存溢出 。 举例1计算1 ~ n的和 public class RecursionDemo { public static void main ( String [] args ) { RecursionDemo demo new RecursionDemo (); // 计算 1~num 的和使用递归完成 int num 5 ; // 调用求和的方法 int sum demo . getSum ( num ); // 输出结果 System . out . println ( sum ); } /* 通过递归算法实现 . 参数列表 :int 返回值类型 : int */ public int getSum ( int num ) { /* num 为 1 时 , 方法返回 1, 相当于是方法的出口 ,num 总有是 1 的情况 */ if ( num 1 ){ return 1 ; } /* num 不为 1 时 , 方法返回 num (num-1) 的累和 递归调用 getSum 方法 */ return num getSum ( num - 1 ); } } 代码执行图解 代码解释 /*
* 当程序执行时它会按照以下流程进行1. main 方法被调用。
2. 一个 RecursionDemo 类的对象 demo 被创建。
3. n 被赋值为 5。
4. 调用 demo.getSum(n) 方法其中 n 的值为 5。
5. 进入 getSum 方法。
6. n 的值不为 1因此程序执行 return n getSum(n - 1);其中 n - 1 的值为 4。
7. 程序递归调用 getSum 方法将参数值 4 传递给它。
8. 再次进入 getSum 方法。
9. n 的值不为 1因此程序执行 return n getSum(n - 1);其中 n - 1 的值为 3。
10. 程序递归调用 getSum 方法将参数值 3 传递给它。
11. 再次进入 getSum 方法。
12. n 的值不为 1因此程序执行 return n getSum(n - 1);其中 n - 1 的值为 2。
13. 程序递归调用 getSum 方法将参数值 2 传递给它。
14. 再次进入 getSum 方法。
15. n 的值不为 1因此程序执行 return n getSum(n - 1);其中 n - 1 的值为 1。
16. 程序递归调用 getSum 方法将参数值 1 传递给它。
17. 再次进入 getSum 方法。
18. n 的值为 1因此程序直接返回 1。
19. 回到上一层递归调用将返回的值 1 加上当前层的 n 的值为 2得到结果 3返回给上一层。
20. 继续返回上一层递归调用将返回的值 3 加上当前层的 n 的值为 3得到结果 6返回给上一层。
21. 继续返回上一层递归调用将返回的值 6 加上当前层的 n 的值为 4得到结果 10返回给上一层。
22. 继续返回上一层递归调用将返回的值 10 加上当前层的 n 的值为 5得到结果 15返回给上一层。
23. 回到 main 方法将返回的结果 15 赋值给 sum 变量。
24. System.out.println(sum); 将结果打印到控制台上。所以程序的输出结果为 15。
*
*
*
* */
} 举例2递归方法计算n! public int multiply ( int num ){ if ( num 1 ){ return 1 ; } else { return num * multiply ( num - 1 ); } } public int f ( int num ){ if ( num 0 ){ return 1 ; } else if ( num 1 ){ return 4 ; } else { return 2 * f ( num - 1 ) f ( num - 2 ); } } 举例3已知有一个数列f(0) 1f(1) 4f(n2)2*f(n1) f(n)其中n是大于0的整数求f(10)的值。 public int func ( int num ){ if ( num 20 ){ return 1 ; } else if ( num 21 ){ return 4 ; } else { return func ( num 2 ) - 2 * func ( num 1 ); } } 举例4计算斐波那契数列Fibonacci的第n个值 斐波那契数列满足如下规律 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 ,.... 即从第三个数开始一个数等于前两个数之和。假设 f(n) 代表斐波那契数列的第 n 个值那么 f(n) 满足 f(n) f(n-2) f(n-1); // 使用递归的写法 int f ( int n ) { // 计算斐波那契数列第 n 个值是多少 if ( n 1 ) { // 负数是返回特殊值 1 表示不计算负数情况 return 1 ; } if ( n 1 || n 2 ) { return 1 ; } return f ( n - 2 ) f ( n - 1 ); } // 不用递归 int fValue ( int n ) { // 计算斐波那契数列第 n 个值是多少 if ( n 1 ) { // 负数是返回特殊值 1 表示不计算负数情况 return 1 ; } if ( n 1 || n 2 ) { return 1 ; } // 从第三个数开始 等于 前两个整数相加 int beforeBefore 1 ; // 相当于 n1 时的值 int before 1 ; // 相当于 n2 时的值 int current beforeBefore before ; // 相当于 n3 的值 // 再完后 for ( int i 4 ; i n ; i ) { beforeBefore before ; before current ; current beforeBefore before ; /* 假设 i4 beforeBefore before; // 相当于 n2 时的值 before current; // 相当于 n3 的值 current beforeBefore before; // 相当于 n 4 的值 假设 i5 beforeBefore before; // 相当于 n3 的值 before current; // 相当于 n 4 的值 current beforeBefore before; // 相当于 n 5 的值 .... */ } return current ; } 举例5面试题 宋老师我今天去百度面试遇到一个一个双重递归调用的问题我琢磨了一下完全不知道为什 么。打断点了也还是没看懂为什么程序会那样走。您有空可以看一下求指教。 private int count 0 ; public int recursion ( int k ) { count ; System . out . println ( count1: count k: k ); if ( k 0 ) { return 0 ; } return recursion ( k - 1 ) recursion ( k - 2 ); //287 //return recursion(k - 1);//11 //return recursion(k - 1) recursion(k - 1);//2047 } 剖析 最后说两句 1. 递归调用会占用大量的系统堆栈内存耗用多在递归调用层次多时速度要比循环 慢的 多 所以在使用递归时要慎重。 2. 在要求高性能的情况下尽量避免使用递归递归调用既花时间又 耗内存 。考虑使用循环迭 代。
