递归：概念、实现与应用

# 递归：概念、实现与应用 ## 1. 递归定义 递归定义是指一个定义是根据自身来定义的。最常见的例子就是阶乘函数。非负整数 $n$ 的阶乘（写作 $n!$）定义如下： - $0! = 1$ - $n! = n \times (n - 1)!$，$n > 0$ 例如，计算 $3!$： - 因为 $3 > 0$，所以 $3! = 3 \times 2!$ - 因为 $2 > 0$，所以 $2! = 2 \times 1!$，则 $3! = 3 \times 2 \times 1!$ - 因为 $1 > 0$，所以 $1! = 1 \times 0!$，则 $3! = 3 \times 2 \times 1 \times 0!$ - 又因为 $0! = 1$，所以 $3! = 3 \times 2 \times 1 \times 1 = 6$ 用编程符号重写阶乘定义为： ```java fact(0) = 1 fact(n) = n * fact(n - 1), n > 0 ``` 递归函数的定义由两部分组成： - **基本情况**：为特定参数给出函数的值，也称为锚点、结束情况或终止情况，它能使递归最终终止。 - **递归（或一般）情况**：函数根据自身来定义。 下面是非数学的递归定义示例： - **祖先定义**：$a$ 是 $b$ 的祖先，如果 (1) $a$ 是 $b$ 的父母，或者 (2) $a$ 是 $c$ 的祖先且 $c$ 是 $b$ 的父母。其中 (1) 是基本情况，(2) 是递归情况。 - **LAME 缩写**：LAME 代表 LAME, Another MP3 Encoder，但它不是真正的递归定义，因为没有基本情况。 ## 2. 在 Java 中编写递归函数 ### 2.1 阶乘函数示例 ```java public static int fact(int n) { if (n < 0) return 0; if (n == 0) return 1; return n * fact(n - 1); } ``` 调用 `int n = fact(3);` 的执行步骤如下： 1. 将 3 复制到临时位置并传递给 `fact` 函数，$n$ 的值变为 3。 2. 执行到最后一条语句，`fact` 尝试返回 $3 \times fact(2)$，但需要先计算 $fact(2)$。 3. 将 2 复制到临时位置并传递给 `fact` 函数，$n$ 的值变为 2，同时保存之前 $n$ 的值。 4. 每次函数调用自身时，将参数（和局部变量，如果有的话）存储在运行时栈上，为每个调用创建新的局部变量。 5. 当 $n$ 为 2 时，`fact` 尝试返回 $2 \times fact(1)$，需要先计算 $fact(1)$。 6. 当 $n$ 为 1 时，`fact` 尝试返回 $1 \times fact(0)$，需要先计算 $fact(0)$。 7. 此时运行时栈包含参数 3、2 和 1，$fact(0)$ 返回 1。 8. 计算 $1 \times fact(0)$，$fact(1)$ 返回 1。 9. 计算 $2 \times fact(1)$，$fact(2)$ 返回 2。 10. 计算 $3 \times fact(2)$，$fact(3)$ 返回 6。 不过，递归版本的阶乘函数效率不高，更高效的函数如下： ```java public static int fact(int n) { int f = 1; while (n > 0) { f = f * n; --n; } return f; } ``` ### 2.2 最大公约数（HCF）函数示例 最大公约数的递归定义如下： - $hcf(m, n)$ 为： - 如果 $n = 0$，则 $hcf(m, n) = m$ - 如果 $n > 0$，则 $hcf(m, n) = hcf(n, m \% n)$ 例如，计算 $hcf(70, 42)$： $hcf(70, 42) = hcf(42, 70 \% 42) = hcf(42, 28) = hcf(28, 42 \% 28) = hcf(28, 14) = hcf(14, 28 \% 14) = hcf(14, 0) = 14$ 递归的 Java 函数实现： ```java public static int hcf(int m, int n) { if (n == 0) return m; return hcf(n, m % n); } ``` 迭代版本的函数（使用欧几里得算法）： ```java public static int hcf(int m, int n) { int r; while (n > 0) { r = m % n; m = n; n = r; } return m; } ``` ### 2.3 斐波那契数列函数示例 斐波那契数列的前两个数定义为 1 和 1，每个新数是前两个数之和。递归定义第 $n$ 个斐波那契数 $F(n)$ 如下： - $F(0) = F(1) = 1$ - $F(n) = F(n - 1) + F(n - 2)$，$n > 1$ Java 函数实现： ```java public static int fib(int n) { if (n == 0 || n == 1) return 1; return fib(n - 1) + fib(n - 2); } ``` 不过，这个函数效率不高，例如计算 $F(5)$ 会有大量的函数调用和加法运算。 ## 3. 使用递归将十进制数转换为二进制 要将十进制数 $n$ 转换为二进制，可以按以下步骤进行： - 打印 $n / 2$ 的二进制表示 - 打印 $n \% 2$ Java 函数实现： ```java public static void decToBin(int n) { if (n > 0) { decToBin(n / 2); System.out.printf("%d", n % 2); } } ``` 调用 `decToBin(13)` 的执行过程如下： 1. 第一次调用，$n$ 为 13 2. 调用 `decToBin(6)`，将 13 压入运行时栈，$n$ 变为 6 3. 调用 `decToBin(3)`，将 6 压入运行时栈，$n$ 变为 3 4. 调用 `decToBin(1)`，将 3 压入运行时栈，$n$ 变为 1 5. 调用 `decToBin(0)`，将 1 压入运行时栈，$n$ 变为 0 6. 此时栈包含 13、6、3、1 7. 因为 $n = 0$，函数立即返回，目前没有输出 8. `decToBin(0)` 返回后，栈顶的 1 恢复为 $n$ 的值 9. 打印 $1 \% 2$，即 1 10. `decToBin(1)` 返回，栈顶的 3 恢复为 $n$ 的值 11. 打印 $3 \% 2$，即 1 12. `decToBin(3)` 返回，栈顶的 6 恢复为 $n$ 的值 13. 打印 $6 \% 2$，即 0 14. `decToBin(6)` 返回，栈顶的 13 恢复为 $n$ 的值 15. 打印 $13 \% 2$，即 1 16. `decToBin(13)` 返回，输出 1101 递归函数的一个重要特性是，当函数调用自身时，当前参数（和局部变量，如果有的话）会被压入栈中，使用新的参数和局部变量执行函数。执行完成后，参数（和局部变量，如果有的话）从栈中弹出，继续执行递归调用后的语句。 例如，对于以下函数和调用 `test(4, 9)`： ```java public static void test(int m, int n) { char ch; // ... test(m + 1, n - 1); System.out.printf("%d %d", m, n); // ... } ``` 执行过程如下： 1. 将 $m$、$n$ 和 $ch$ 的值压入栈中 2. `test` 以 $m = 5