【数据结构与算法】之递归详解

艾伦耶格尔

发布于 2025-08-28 15:23:15

13500

代码可运行

运行总次数：0

代码可运行

递归，这个看似神秘的编程技巧，就像一面面巧妙放置的镜子，能够以一种优雅而高效的方式解决许多复杂问题。理解递归就像打开了一扇通往全新编程世界的大门，让你能够写出更加简洁、易懂且富有创造力的代码。本文主要介绍递归的基本使用，均采用Java语言。

一、递归的概念

想象一下，你正在剥一个洋葱，一层一层地剥开，直到露出最里面的核心。递归就像剥洋葱，将一个复杂的问题分解成多个相同但规模更小的子问题，逐层解决，最终合并得到整个问题的答案。

书面解释：递归是一种解决计算问题的方法，其中解决方案取决于同一类问题的更小子集

二、递归的两大支柱

递归的奥秘在于它精妙的结构，由两个关键要素构成：

递归基例（Base Case）: 就像多米诺骨牌的第一块，递归基例是递归的终止条件，防止程序陷入无限循环的深渊。也就是递归出口，什么时候该停止。
递归步骤（Recursive Step）: 递归步骤将问题分解成更小的子问题，并通过调用自身来解决这些子问题。每个子问题都遵循相同的逻辑，最终回归到基例，递归结束。

需要注意的是：

深入到最里层叫做递
从最里层出来叫做归
在递的过程中，外层函数内的局部变量（以及方法参数）并未消失，归的时候还可以用到

三、Java 代码实战

让我们通过几个经典的例子，来感受递归的魅力：

1. 阶乘计算：

a.阶乘的定义 n!= 1⋅2⋅3⋯(n-2)⋅(n-1)⋅n，其中 n 为自然数， 0! = 1

b.递推关系：

代码实现：

public class RecursionDemo1 {

  public static int factorial(int n) {
    // 递归基例：0 的阶乘是 1
    if (n == 0) {
      return 1;
    } else {
      // 递归步骤：n! = n * (n-1)!
      return n * factorial(n - 1);
    }
  }
}

在这个例子中，factorial(0) == 1 是基例，而 factorial(n) == n * factorial(n - 1) 是递归步骤，将计算 n! 的问题分解成计算 (n-1)! 的子问题。

拆解理解：换一种方式更加深入理解

private static int fac(int n) {
    if (n == 1) {
        return 1;
    }
    return n * fac(n - 1);
}

拆解伪代码如下，假设 n 初始值为 3，可以清楚的看到问题规模在不断缩小，知道到达了递归出口之后，大问题才得以解决，并开始层层返回。

fac(int n = 3) { // 解决不了,递
    return 3 * fac(int n = 2) { // 解决不了,继续递
        return 2 * fac(int n = 1) {
            if (n == 1) { // 可以解决, 开始归
                return 1;
            }
        }
    }
}

2.反向打印字符串：

用递归反向打印字符串，n 为字符在整个字符串 str 中的索引位置

递：n 从 0 开始，每次 n + 1，一直递到 n == str.length() - 1
归：从 n == str.length() 开始归，从归打印，自然是逆序的

递推关系：

代码实现：

public static void reversePrint(String str, int index) {
    if (index == str.length()) {
        return;
    }
    reversePrint(str, index + 1);
    System.out.println(str.charAt(index));
}

拆解理解：拆解伪代码如下，假设字符串为 "abc"

void reversePrint(String str, int index = 0) {
    void reversePrint(String str, int index = 1) {
        void reversePrint(String str, int index = 2) {
            void reversePrint(String str, int index = 3) { 
                if (index == str.length()) {
                    return; // 开始归
                }
            }
            System.out.println(str.charAt(index)); // 打印 c
        }
        System.out.println(str.charAt(index)); // 打印 b
    }
    System.out.println(str.charAt(index)); // 打印 a
}

3. 斐波那契数列：

代码实现：

public class RecursionDemo2 {

  public static int fibonacci(int n) {
    // 递归基例：第 1 个和第 2 个斐波那契数都是 1
    if (n == 1 || n == 2) {
      return 1;
    } else {
      // 递归步骤：F(n) = F(n-1) + F(n-2)
      return fibonacci(n - 1) + fibonacci(n - 2);
    }
  }
}

数列中值的分布为：

1 1 2 3 5 8 13 21 34...

斐波那契数列的定义是：前两个数是 1，从第三个数开始，每个数都是前两个数之和。递归步骤完美地体现了这一定义。

4. 汉诺塔问题：

汉诺塔问题是递归的经典应用，用递归解决起来简洁优雅。

汉诺塔由来：传说中，在古印度，大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

代码实现：

public class RecursionDemo3 {

  public static void moveDisks(int n, char source, char destination, char auxiliary) {
    // 递归基例：只剩一个盘子时，直接移动
    if (n == 1) {
      System.out.println("将盘子 " + n + " 从 " + source + " 移动到 " + destination);
    } else {
      // 递归步骤：
      // 1. 将 n-1 个盘子从 source 移动到 auxiliary
      moveDisks(n - 1, source, auxiliary, destination);
      // 2. 将最大的盘子从 source 移动到 destination
      System.out.println("将盘子 " + n + " 从 " + source + " 移动到 " + destination);
      // 3. 将 n-1 个盘子从 auxiliary 移动到 destination
      moveDisks(n - 1, auxiliary, destination, source);
    }
  }
}