递归 (Recursion) — AP Computer Science A CS A 学习指南

适合谁：AP Computer Science A 参加 AP Computer Science A 的考生。

覆盖内容：基准用例与递归用例、递归调用追踪、递归与迭代的差异、递归实现二分查找、阶乘与斐波那契数列等常见递归问题、考试避坑指南、真题风格练习题。

前置知识：基础 Java 或任何其他过程式语言编程。

关于练习题：下文「练习题」一节的所有题目均为我们按 AP Computer Science A 风格编写的原创题目 (original problems)，仅用于教学。它们不是 College Board 真题的复制，措辞、数值或语境可能不同。请把它们当作练手用；评分细则请对照 College Board 官方 mark scheme。

1. 什么是递归？

递归是一种方法在定义中调用自身的编程技巧，核心逻辑是将一个复杂的大问题，拆分为多个结构完全相同、规模更小的子问题，通过求解子问题最终得到原问题的答案。 在AP CS A考纲中，递归属于Unit 10的核心考点，选择题占2-3题，FRQ偶尔会出现1小问递归实现，占总分的5%-8%。你不需要用递归写完整的FRQ大题，但必须掌握递归逻辑的阅读、追踪和纠错能力。

2. 基准用例与递归用例 (Base case and recursive case)

任何合法的递归方法都必须包含两类逻辑：

• 基准用例（base case）：不需要再继续调用自身、可以直接返回结果的边界条件，作用是终止递归链，避免无限递归。
• 递归用例（recursive case）：将当前问题拆分为更小的同类型子问题，调用自身求解的逻辑。

我们以判断回文字符串的递归实现为例：

public boolean isPalindrome(String s) {
 // 基准用例：长度为0或1的字符串一定是回文
 if (s.length() <= 1) return true;
 // 递归用例：首尾字符相等时，判断去掉首尾的子串是否为回文
 if (s.charAt(0) == s.charAt(s.length()-1)) {
 return isPalindrome(s.substring(1, s.length()-1));
 }
 return false;
}

考官常考的考点是：如果缺少基准用例，程序运行时会触发栈溢出错误（StackOverflowError），直接崩溃。

3. 递归调用追踪 (Tracing recursive calls)

递归调用的底层依赖JVM的**调用栈（call stack）**实现：每触发一次递归调用，就会将当前方法的状态压入栈顶，直到遇到基准用例后，再从栈顶依次弹出调用、返回结果。 你可以用逐层展开的方式追踪递归返回值，我们以factorial(3)的计算为例：

1. 第一层：调用factorial(3)，未触发基准用例，等待factorial(2)的返回结果
2. 第二层：调用factorial(2)，未触发基准用例，等待factorial(1)的返回结果
3. 第三层：调用factorial(1)，触发基准用例返回1
4. 第二层得到结果：$2\times 1=2$，返回给第一层
5. 第一层得到结果：$3\times 2=6$，最终返回值为6

AP考试中90%的递归选择题都是调用追踪题，你只需要按顺序展开每一层调用，就不会丢分。

4. 递归与迭代对比 (Recursion vs iteration)

所有递归能实现的逻辑，都可以用迭代（iteration）（for/while循环）实现，两者的核心差异如下：

以计算1到n的和为例，递归实现：

public int sum(int n) {
 if (n == 1) return 1; // 基准用例
 return n + sum(n-1);
}

等价迭代实现：

public int sum(int n) {
 int res = 0;
 for (int i=1; i<=n; i++) res +=i;
 return res;
}

5. 递归搜索：二分查找 (Recursive search — binary search)

**二分查找（binary search）**是递归的典型应用场景，前提是数组已经按升序/降序排列，核心逻辑是每次排除一半的搜索范围，时间复杂度仅为$O(\log n)$。 递归实现二分查找的逻辑如下：

1. 基准用例1：如果左边界left > 右边界right，说明目标值不存在，返回-1
2. 计算中间索引mid = (left + right) / 2
3. 基准用例2：如果arr[mid] == target，返回mid
4. 递归用例1：如果arr[mid] > target，说明目标值在左半区，递归搜索[left, mid-1]
5. 递归用例2：如果arr[mid] < target，说明目标值在右半区，递归搜索[mid+1, right]

比如在有序数组[2,5,7,9,12]中查找7：第一次mid=2，arr[2]==7直接返回2，仅需要1次比较。

6. 常见递归问题：阶乘、斐波那契 (Common recursion problems — factorial, Fibonacci)

6.1 阶乘（factorial）

n的阶乘定义为$n!=1\times 2\times 3\times ...\times n$，递归公式为： $$ n! = \begin{cases} 1 & n \leq 1 \ n \times (n-1)! & n > 1 \end{cases} $$ 递归实现的时间复杂度为$O(n)$，空间复杂度为$O(n)$。

6.2 斐波那契数列（Fibonacci sequence）

斐波那契数列的定义是前两项为0和1，后续每一项等于前两项之和，递归公式为： $$ F(n) = \begin{cases} 0 & n = 0 \ 1 & n = 1 \ F(n-1) + F(n-2) & n \geq 2 \end{cases} $$ 注意：递归实现斐波那契存在大量重复计算，时间复杂度高达$O(2^n)$，这是选择题高频考点。

7. 常见陷阱 (Common Pitfalls)

1. 错误做法：递归方法没有写基准用例，运行时触发StackOverflowError。

• 原因：误以为递归可以无限拆分子问题，忘记终止条件。
• 正确做法：写递归方法时首先定义基准用例，写完先用n=0、n=1等边界值测试。

2. 错误做法：基准用例设置错误，比如阶乘的基准用例写为if(n==0) return 0，导致所有结果都为0。

• 原因：记错常见递归问题的边界值。
• 正确做法：牢记阶乘、斐波那契、二分查找等常考场景的基准用例，代入小值验证结果。

3. 错误做法：递归调用的参数范围没有缩小，比如二分查找时右边界传mid而不是mid-1，导致死循环。

• 原因：没有注意到mid位置的元素已经被排除在后续搜索范围之外。
• 正确做法：每次递归调用的参数范围必须比上一次小，确保最终能触发基准用例。

4. 错误做法：忘记处理递归调用的返回值，比如斐波那契只调用F(n-1)直接返回，遗漏F(n-2)。

• 原因：误以为调用递归方法就会自动合并结果。
• 正确做法：每次递归调用的结果要按问题逻辑组合后，再返回给上层调用。

8. 练习题 (AP Computer Science A 风格)

题1（选择题）

给定以下Java方法，调用f(3)的返回值是多少？

public int f(int n) {
 if (n <= 1) return 2;
 return f(n-1) + f(n-2);
}

解答： 逐层展开调用：

• $f(3)=f(2)+f(1)$
• $f(2)=f(1)+f(0)=2+2=4$
• 代入得$f(3)=4+2=6$ 最终返回值为6。

题2（代码题）

用递归实现一个方法，输入正整数n，返回n的位数（比如输入123返回3）。 解答： 基准用例：当n小于10时，位数为1；递归用例：位数等于1加上n除以10的结果的位数。

public int countDigit(int n) {
 if (n <10) return 1;
 return 1 + countDigit(n/10);
}

题3（改错题）

以下递归方法用于计算1到n的和，运行时会触发StackOverflowError，请找出错误并修改。

public int sum(int n) {
 return n + sum(n-1);
}

解答： 错误原因：缺少基准用例，递归无限运行触发栈溢出。修改方案是添加基准用例：

public int sum(int n) {
 if (n == 1) return 1; // 新增基准用例
 return n + sum(n-1);
}

9. 速查表 (Quick Reference Cheatsheet)

10. 接下来怎么学

递归是AP CS A的基础算法逻辑，后续Unit 10的归并排序、分治类算法都依赖递归实现，掌握递归追踪能力是搞定所有算法类选择题的前提。你可以多做官方真题中的递归选择题，熟悉考官的出题套路。 如果你在递归练习题、真题演练中遇到任何疑问，都可以随时到小欧提交问题，我们会为你提供定制化的解题指导与知识点补全。