Java基础系列26-常用api之递归

x33g5p2x  于2021-12-18 转载在 其他  
字(1.4k)|赞(0)|评价(0)|浏览(465)

一.递归概述

概念:指在当前方法内调用自己的这种现象。

递归的分类:递归分为两种,直接递归和间接递归。

  1. 直接递归称为方法自身调用自己
  2. 间接递归可以A方法调用B方法,B方法调用方法,C方法调用A方法。

注意事项:

  1. 递归一定要有条件限定,保证递归能够停止下来,否则会发生栈内存溢出。
  2. 在递归中虽然有限定条件,但是递归次数不能太多,否则也会发生栈内存溢出。
  3. 构造方法,禁止递归。

二.递归案例

2.1 递归方法求阶乘

需求:求5的阶乘
 5! = 5 * 4 * 3 * 2 * 1; //120
 5! = 5 * 4!; //120
  4! = 4 * 3!; //24
   3! = 3 * 2!; //6
    2! = 2 * 1!; //2
     1! = 1; //1
 n! = n * (n - 1)!

递归:把大问题拆成很多小问题,然后再把小问题拆成更多的小问题,
当我们把更多小问题解决了,小问题也解决了
随着小问题的解决,大问题也随之解决了

代码:

  1. package Java_study;
  2. /**
  3. *
  4. * @author 只是甲
  5. * @date 2021-07-01
  6. * @remark 递归求阶乘
  7. *
  8. */
  9. public class recursion1 {
  10. public static void main(String[] args) {
  11. System.out.println(recursion(5));
  12. }
  13. /**
  14. * @remark 求一个数的阶乘
  15. * @param n
  16. * @return n的阶乘结果n!
  17. */
  18. public static int recursion(int n) {
  19. //必须要有出口
  20. if (n == 1) {
  21. return 1;
  22. } else {
  23. return n * recursion(n - 1);
  24. }
  25. }
  26. }

测试记录:

  1. 120

2.2 递归方法求斐波那契列数

古典问题:
  有一对兔子,从出生后第2个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问第二十个月的兔子对数为多少?

1个月:1
2个月:2
3个月:3
4个月:5
5个月:8
6个月:13
7个月:21

规律:除了第一个月和第二月以外,其余每个月都是前两个月之和
斐波那契列数

如果不理解,可以参考图解:

代码:

  1. package Java_study;
  2. /**
  3. *
  4. * @author 只是甲
  5. * @date 2021-07-01
  6. * @remark 递归求斐波那契列数
  7. *
  8. */
  9. public class recursion2 {
  10. public static void main(String[] args) {
  11. System.out.println(method(1, 19));//开始1对兔子,19个月后共有6765对兔子
  12. }
  13. /**
  14. * @remark month个月后 init个数量对兔子会发展成为多少对兔子数
  15. * @param init 初始兔子数量
  16. * @param month 月份
  17. * @return 结果兔子数量
  18. */
  19. public static int method(int init, int month) {
  20. //必须要有出口
  21. //如果是第一个月,只有一对兔子
  22. if (month == 1) {
  23. return init;
  24. } else if (month == 2) {
  25. return init * 2;
  26. } else {
  27. return method(init, month - 2) + method(init, month - 1);
  28. }
  29. }
  30. }

测试记录:

  1. 6765

参考:

  1. https://blog.csdn.net/qq_43529621/article/details/115379095

相关文章