递归算法

概况

递归算法是一种通过在函数中调用自身来解决问题的方法。常用于解决需要重复执行相似操作的问题，例如树、图等数据结构的遍历，以及分治、动态规划等算法。

递归算法的基本思想是将大问题划分为一个或多个具有相同结构的子问题，并通过递归调用函数来解决这些子问题。每个子问题的解最终汇总起来，从而得到原始问题的解。

在实现递归算法时，需要定义递归的终止条件，也称为基本情况。当满足终止条件时，递归将不再进行，避免无限递归。否则，递归函数会继续调用自身，直到达到终止条件为止。

虽然递归算法可以简洁地解决某些问题，但它也可能导致性能问题。递归函数的调用过程中需要消耗额外的栈空间，如果递归层级过深，可能会导致栈溢出。因此，在使用递归算法时，需要谨慎设计，并确保递归层级不会过深。

步骤

递归算法通常包含以下步骤：

1. 定义基本情况：确定递归应该终止的条件。这是递归的停止点，防止无限递归。基本情况通常是一个简单的问题，可以直接求解，而不需要递归。

2. 将大问题拆分为子问题：将原始问题分解为一个或多个具有相同结构的子问题。这是递归算法的核心思想。

3. 提供递归调用：在函数中调用自身，以解决子问题。递归调用可以使用不同的输入参数，以便在每次递归调用中处理不同的子问题。

4. 合并子问题的解：获取每个子问题的结果，并将它们合并成原始问题的解。在递归的每一层中，需要将子问题的解合并到最终的解中。

5. 返回解：将最终的解返回给调用函数。

需要注意的是，递归算法在编写时需要注意递归层级的控制，确保不会因为递归层级过深而导致栈溢出的问题。此外，在设计递归算法时，应尽量避免重复计算相同的子问题，可以使用记忆化搜索或动态规划等方法进行优化。

代码示例

需求1：利用递归求1~100的和

需求2：利用递归求5的阶乘

例如：

package text.text02;

/*
递归算法：
    递归算法的基本思想是将大问题划分为一个或多个具有相同结构的子问题，并通过递归调用函数来解决这些子问题。每个子问题的解最终汇总起来，从而得到原始问题的解。
    
递归算法：(核心)
    1.找出口
    2.找规则

需求1：利用递归求1~100的和
    规律：1~100的和 = 100 + 1~99的和
         1~99的和 = 99 + 1~98的和
         1~98的和 = 98 + 1~97的和
         1~97的和 = 97 + 1~96的和
             ……………………
         1~3的和 = 3 + 1~2的和
         1~2的和 = 2 + 1~1的和
         1~1的和 = 1 （出口）
                
需求2：利用递归求5的阶乘
    5! = 5 * 4 * 3 * 2 * 1
    规律：5! = 5 * 4!
         4! = 4 * 3!
         3! = 3 * 2!
         2! = 2 * 1!
         1! = 1 (出口)
 */
public class text14A {
    public static void main(String[] args) {
        //调用getSum方法
        int sum = getSum(100);
        System.out.println("1~100的和为：" + sum);
        //调用factorial方法
        int num = factorial(5);
        System.out.println("5的阶乘为：" + num);
    }

    //定义递归方法求1~100的和
    public static int getSum(int number) {
        //出口：如果number=1，则返回方法
        if (number == 1) {
            return 1;
        }
        //如果number不等于1，则接着调用getSum方法
        else {
            int sum = number + getSum(number - 1);
            return sum;
        }
    }

    //定义递归方法求5的阶乘
    public static int factorial(int number) {
        //出口
        if (number == 1) {
            return number;
        }
        //如果number不等于1，则接着调用factorial方法
        else {
            int num = number * factorial(number - 1);
            return num;
        }
    }
}

输出结果

流程图解释：

对于 getSum() 方法：

          getSum(100)       
              ↓                 
     ┌─────┬─────┬─────┬─────┐ 
     ↓     ↓     ↓     ↓     ↓
  getSum(99) ...  getSum(2)  getSum(1)
    ↓         ↓         ↓
 getSum(98) ...  getSum(2)
    ↓         ↓         ↓
    ...       ...       ...
    ↓         ↓         ↓
 getSum(3)   getSum(2) getSum(1)
    ↓         ↓
 getSum(2)   getSum(1)
    ↓         ↓
 getSum(1)   Return 1

对于 factorial() 方法：

        factorial(5)
           ↓                 
     ┌─────┬─────┬─────┬─────┐ 
     ↓     ↓     ↓     ↓     ↓
  factorial(4) ...  factorial(2)  factorial(1)
    ↓         ↓         ↓
 factorial(3) ...  factorial(2)
    ↓         ↓         ↓
      ...       ...       ...
    ↓         ↓         ↓
 factorial(2)   factorial(1)
    ↓         ↓
factorial(1)  Return 1