文章目录
- 递归
- 编写递归函数
- 递归的工作原理
- 常见的递归应用场景
- 递归注意点
递归
递归是一种解决问题的方法,其中一个函数调用自身以解决较小的实例,直到达到基本情况(停止条件),然后开始返回结果。递归可以让我们更容易地解决复杂的问题,因为它允许我们将问题分解成更小的子问题。
在递归中,通常有两个关键要素:
- 递归调用: 函数在自身内部进行调用。
- 停止条件: 函数必须有一种方式来结束递归,否则它将无限循环下去。
编写递归函数
public class RecursionExample {public static int factorial(int n) {// 停止条件:当n等于0或1时,阶乘为1。if (n == 0 || n == 1) {return 1;} else {// 递归调用:计算n * (n-1)的阶乘。return n * factorial(n - 1);}}public static void main(String[] args) {int n = 5;int result = factorial(n);System.out.println("Factorial of " + n + " is " + result); // Factorial of 5 is 120}
}
public class RecursionTest {public static void main(String[] args) {RecursionTest test = new RecursionTest();// test.method1(); // 内存溢出System.out.println(test.getSum(100));}/*** 计算1-100之间所有自然数的和*/public int getSum(int n) {if (n == 1) {return 1;} else {return n + getSum(n - 1);}}public void method1() {System.out.println("method1() begin");method1();System.out.println("method1() end");}}
递归的工作原理
当一个递归函数被调用时,它将问题分解成较小的子问题,然后继续调用自身来解决这些子问题。每个子问题都会再次分解,直到达到停止条件。然后,递归函数开始返回结果,将结果合并以解决原始问题。
在递归调用中,每个函数调用都有自己的局部变量和执行上下文,这些信息在递归的不同层次之间传递。
常见的递归应用场景
递归在许多计算机科学和编程问题中都有广泛的应用。以下是一些常见的递归应用场景:
- 阶乘计算: 如上所示,计算一个整数的阶乘是一个经典的递归问题。
- 斐波那契数列: 斐波那契数列是一个递归问题,其中每个数字是前两个数字的和。
- 二叉树遍历: 遍历二叉树(前序、中序、后序)通常使用递归来实现。
- 汉诺塔问题: 汉诺塔是一个经典的递归问题,涉及将一堆盘子从一个杆移动到另一个杆,只能使用一个中间杆,且大盘子不能放在小盘子上面。
- 组合与排列: 计算组合和排列的问题通常可以使用递归来解决。
- 图遍历: 在图数据结构中,深度优先搜索(DFS)和广度优先搜索(BFS)通常使用递归或队列来实现。
递归注意点
- 递归调用会占用大量的系统堆栈,内存耗用多,在递归调用层次多
时速度要比循环慢的多,所以在使用递归时要慎重。 - 在要求高性能的情况下尽量避免使用递归,递归调用既花时间又耗
内存。考虑使用循环迭代