【Java -- 算法】递归

本文介绍了递归算法的 Java 代码实现，所有代码均可通过 菜鸟工具在线编译器 直接运行，因此打算整理一下分享给大家。

定义

在数学与计算机科学中，递归(Recursion)是指在函数的定义中使用函数自身的方法。

递归的三要素：

• 明确递归终止条件
• 给出递归终止时的处理办法
• 提取重复的逻辑，缩小问题规模

递归的应用场景：

1. 问题的定义是按递归定义的（Fibonacci函数，阶乘，…）；
2. 问题的解法是递归的（有些问题只能使用递归方法来解决，例如，汉诺塔问题，…）；
3. 数据结构是递归的（链表、树等的操作，包括树的遍历，树的深度，…）。

实例

1. 九九乘法表

public class Main {
	public static void main(String[] args) {
		method(9);
	}
	
	private static void method(int i) {
        if (i == 1) {  
            System.out.println("1*1=1 "); 
        } else {  
            method(i - 1); 
            for (int j = 1; j  0) {
            if(n == 1){    // 递归终止条件
                return first;       // 简单情景
            }else if(n == 2){            // 递归终止条件
                return second;      // 简单情景
            }else if (n == 3) {         // 递归终止条件
                return first + second;      // 简单情景
            }
            return fibonacci(second, first + second, n - 1);  // 相同重复逻辑，缩小问题规模
        }
        return -1;
    }

}

输出结果：

4. 杨辉三角

public class Main {
	public static void main(String[] args) {
        int length = 10;    // 打印的行数
    
        for (int i = 1; i