Java——递归_java 递归

一、递归介绍

1、什么是递归

递归在Java编程中是指一个方法调用自身的编程技巧。

    public static void foo() {
		//...
		foo();//方法调用自身
		//...
	}

2、递归用于什么场景

递归是一种常见的算法设计方法，特别适用于解决那些可以分解为相似子问题的问题。常见的递归问题包括阶乘计算、斐波那契数列、树和图的遍历等。

3、递归包含部分

一个递归方法通常由两部分组成：

1. 基准情况（Base Case）：递归过程中终止递归的条件。如果没有基准情况，递归将进入无限循环。
2. 递归步骤（Recursive Step）：将问题分解为一个或多个子问题，并调用自身处理这些子问题。

4、递归的优点和缺点

优点：

• 代码简洁：递归可以使代码更简洁和易读，特别是对于那些自然递归的问题（如树遍历）。
• 自然性：某些问题（如组合数学中的问题）自然适合递归解决。

缺点：

• 性能问题：递归可能导致较大的栈消耗，特别是在递归深度较深时，可能引发栈溢出错误（StackOverflowError）。
• 复杂性：对于某些问题，递归可能导致重复计算，效率较低；需要进行优化（如使用记忆化或动态规划）。

二、递归详细解释

1、递归详细解释

下面我们用以下例子来介绍递归：

public class Test {
	public static void test(int n) {
		if(n > 0) {
			test(n - 1);
		}
		System.out.println(n);
	}
	public static void main(String[] args) {
		test(2);
	}
}

首先是主函数调用 test 方法，传入的参数是 2。这时就会开辟一个 test 函数栈帧，这里的参数 n 值为 2。

然后这里的 test 函数开始依次执行它的方法体的语句，首先就是判断 n > 0，如果 n > 0 为真就调用 test(2 - 1)，可以发现这里 n > 0 为真，所以接着调用 test(2 - 1)，即调用 test(1)， 然后就是开辟下一个 test 函数的栈帧，这里的参数为 1。

然后这里的 test 函数还是要开始依次执行它的方法体的语句，首先还是判断 n > 0，如果 n > 0 为真就调用 test(1 - 1)，可以发现这里 n > 0 为真，所以接着调用 test(1 - 1)，即调用 test(0)， 然后就是开辟下一个 test 函数的栈帧，这里的参数为 0。

然后这个参数为 0 的 test 方法还是依次执行方法体的语句，这次 n > 0 为假，所以不再调用 test 方法，执行后面的语句 System.out.println(n); 显示这时 n 的值，我们将在左下角显示。

在这个语句执行完毕后，这个参数为 0 的 test 方法就完成了调用，这个方法就会返回，

然后这个函数栈帧就会被销毁：

然后上面的函数返回就到了参数为 1 的 test 方法方法体内，接下来还会接着执行后面未执行的语句 System.out.println(n); 会打印这时 n 的值，为 1。

在执行过这个语句后，参数为 1 的 test 方法就完成了调用，它也将返回，然后栈帧被销毁。然后就返回到参数为 2 的 test 方法方法体内，接着执行未执行的语句，打印这时的 n 的值，打印 2。

在执行完成这个语句后，参数为 2 的 test 方法也会返回，然后它的栈帧也会被销毁。

最终 main 函数也返回，最终程序结束。

最终的运行结果为：

这张图中的粉色箭头就代表递进，蓝色箭头就代表归来，所以合称递归。

2、递归求阶乘

一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。自然数n的阶乘写作n!。

例如：

5! = 5 * 4 * 3 * 2 * 1 = 120

下面为具体代码：

public class Test {
	public static int factorial(int n) {
		if(n == 1) {
			return 1;
		} else {
			return n * factorial(n - 1);
		}
	}
	public static void main(String[] args) {
		System.out.println("5! = " + factorial(5));
	}
}

运行结果：

下面我们详细解释一下：

显然，阶乘是可以一点点将较为复杂的问题转换为一个个较基础的问题的。

可以发现这个递归方法求阶乘就是将数字依次递减一，当数字减到 1 时，函数归来，从 1 依次乘到这个数字，最终得到阶乘的结果。

3、递归注意事项

我们可以看到递归会在栈区开辟很多空间，如果递归没有结束条件，就会一直开辟空间，最终会造成栈溢出（Stack Overflow），导致程序崩溃。

所以递归一定要有结束条件，二且要不断逼近结束条件。

三、递归使用实例

1、使用递归求斐波那契数列

斐波那契数列（Fibonacci sequence）是一个著名的数列，其定义基于以下递推关系：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

这一数列由意大利数学家莱昂纳多·斐波那契（Leonardo Fibonacci）在研究兔子的繁殖问题时引入，因此也被称为“兔子数列”。

其数值为：1、1、2、3、5、8、13、21、34……

下面为具体代码：

public class Test {
	public static int fibonacci(int n) {
		if(n == 0) {
			return 0;
		} else if(n == 1) {
			return 1;
		}else {
			return (fibonacci(n - 2) + fibonacci(n - 1));
		}
	}
	public static void main(String[] args) {
		for(int i = 1; i <= 10; i++) {
			System.out.println("第" + i + "项为 " + fibonacci(i));
		}
	}
}

运行结果：

下面为图解，用以 4 为参数调用 fibonacci 方法为例：

2、用递归解决猴子吃桃子

猴子每天吃一半数目的桃子，再吃一个桃子，已知第十天还没有吃，就只剩下一个桃子了。求第一天有几个桃子。

这里的规律就是前一天的桃子是后一天的桃子数加一再乘二。

public class Test {
	//day为还剩1个桃子的天数，n是要求有几个桃子的天数
	public static int foo(int day,int n) {
		if(n == day) {
			return 1;
		}
		return (foo(day,n + 1) + 1) * 2;
	}
	public static void main(String[] args) {
		System.out.println(foo(10,1));//第10天还有1个桃子，要求第1天有几个桃子
	}
}

运行结果：

下面为具体图解：

3、汉诺塔

1. 目标：将所有圆盘从源柱（源杆，通常称为A）移动到目标柱（目标杆，通常称为C），并遵守以下规则。
2. 圆盘：有
   声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/运维做开发/article/detail/797557