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

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

一.递归概述

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

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

  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)!

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

代码:

package Java_study;
/**
 * 
 * @author 只是甲
 * @date   2021-07-01
 * @remark 递归求阶乘
 *
 */
public class recursion1 {
	public static void main(String[] args) {
		System.out.println(recursion(5));
	}
	
	/**
	 * @remark   求一个数的阶乘
	 * @param    n
	 * @return   n的阶乘结果n!
	 */
	public static int recursion(int n) {
		//必须要有出口
		if (n == 1) {
			return 1;
		} else {
			return n * recursion(n - 1);
		}
	}

}

测试记录:

120

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

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

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

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

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

代码:

package Java_study;

/**
 * 
 * @author  只是甲
 * @date    2021-07-01
 * @remark  递归求斐波那契列数
 *
 */
public class recursion2 {
	public static void main(String[] args) {
		System.out.println(method(1, 19));//开始1对兔子,19个月后共有6765对兔子
	}
	
	/**
	 * @remark month个月后 init个数量对兔子会发展成为多少对兔子数
	 * @param init 初始兔子数量
	 * @param month 月份
	 * @return 结果兔子数量
	 */
	public static int method(int init, int month) {
		//必须要有出口
		//如果是第一个月,只有一对兔子
		if (month == 1) {
			return init;
		} else if (month == 2) {
			return init * 2;
		} else {
			return method(init, month - 2) + method(init, month - 1);
		}
	}

}

测试记录:

6765

参考:

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

相关文章