Recursion: base case and recursive case · 递归:基本情形与递归情形
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · 此页面需较新浏览器（支持 SharedArrayBuffer）。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
English
A method that calls itself
- Recursion is when a method calls itself to solve a smaller piece of the same problem.
- On the AP CSA exam you mostly trace recursion (follow the calls by hand). Writing small recursive methods helps you trace well.
- Every recursive method needs two parts: a base case and a recursive case.
中文
一个调用自己的方法
- 递归(recursion)就是一个方法调用它自己,来解决同一个问题的更小一块。
- 在 AP CSA 考试中,你主要是追踪递归(用手跟着一步步走)。会写一些小的递归方法能帮你追踪得更好。
- 每个递归方法都需要两个部分:一个基本情形(base case)和一个递归情形(recursive case)。
English
Base case and recursive case
- Base case: the simplest input, where you return an answer without calling yourself. This stops the recursion.
- Recursive case: you call the same method with a smaller input, then build the answer.
- Without a base case, the method calls forever and crashes (a stack overflow).
中文
基本情形和递归情形
- 基本情形(base case):最简单的输入,在这里你不再调用自己就直接返回答案。它让递归停下来。
- 递归情形(recursive case):你用一个更小的输入再调用同一个方法,然后拼出答案。
- 如果没有基本情形,这个方法就会一直调用下去并崩溃(叫作栈溢出 stack overflow)。
English
Example: factorial
factorial(n)meansn * (n-1) * ... * 1. For examplefactorial(4) = 24.- Base case:
factorial(1)is1. - Recursive case:
factorial(n)isn * factorial(n - 1).
中文
例子:阶乘
factorial(n)表示n * (n-1) * ... * 1。例如factorial(4) = 24。- 基本情形:
factorial(1)是1。 - 递归情形:
factorial(n)是n * factorial(n - 1)。
public class Recursion {
public static int factorial(int n) {
if (n <= 1) { // base case
return 1;
}
return n * factorial(n - 1); // recursive case
}
}
English
How the calls unwind
- Each call waits for the smaller call to finish. Then it multiplies and returns.
- Trace
factorial(3). Calls go down, then answers come back up.
中文
这些调用是怎么展开的
- 每个调用都等待那个更小的调用先完成。然后它做乘法并返回。
- 追踪
factorial(3)。调用一路往下走,答案再一路往上返回。
factorial(3) = 3 * factorial(2) <- waits
factorial(2) = 2 * factorial(1) <- waits
factorial(1) = 1 <- base case, returns 1
factorial(2) = 2 * 1 = 2 <- returns 2
factorial(3) = 3 * 2 = 6 <- returns 6
English
Example: sum to n
sumTo(n)adds1 + 2 + ... + n. For examplesumTo(4) = 10.- Base case:
sumTo(0)is0(nothing to add). - Recursive case:
sumTo(n)isn + sumTo(n - 1).
中文
例子:求和到 n
sumTo(n)把1 + 2 + ... + n加起来。例如sumTo(4) = 10。- 基本情形:
sumTo(0)是0(没有东西要加)。 - 递归情形:
sumTo(n)是n + sumTo(n - 1)。
public class Recursion {
public static int sumTo(int n) {
if (n <= 0) { // base case
return 0;
}
return n + sumTo(n - 1); // recursive case
}
}
English
Recursion over an array
- We can also recurse with an index that moves toward the end.
- Base case: when the index is past the last spot, return
0. - Recursive case: add
a[i]to the sum of the rest,arraySum(a, i + 1).
中文
在数组上递归
- 我们也可以用一个下标(index)来递归,让它朝末尾移动。
- 基本情形:当下标越过最后一个位置时,返回
0。 - 递归情形:把
a[i]加上剩下部分的和,也就是arraySum(a, i + 1)。
English
- To sum the whole array you start at index
0:arraySum(a, 0). - Each call handles one value and trusts the next call for the rest.
中文
public class Recursion {
public static int arraySum(int[] a, int i) {
if (i >= a.length) { // base case: past the end
return 0;
}
return a[i] + arraySum(a, i + 1);
}
}
- 要对整个数组求和,你从下标
0开始:arraySum(a, 0)。 - 每个调用只处理一个值,剩下的就交给下一个调用。
English
Common mistakes
- Recursion needs a base case, or it throws StackOverflowError.
- Each call must move closer to the base case.
中文
常见错误
- 递归需要基准情形,否则抛出 StackOverflowError。
- 每次调用都要更靠近基准情形。
English
Now you try
- Each task gives you a method skeleton with a TODO. Write the base case and the recursive case.
- A hidden Harness calls your method with several values and checks the result.
- Press Run to compile, then Check answer.
中文
现在轮到你
- 每个任务给你一个带 TODO 的方法骨架。请写出基本情形和递归情形。
- 一个隐藏的 Harness 会用多个值调用你的方法并检查结果。
- 按运行来编译,然后按检查答案。
Explore · 探索
Recursion: base + recursive case · 递归:基线 + 递归情形
Calls split until a base case, then answers return up. · 调用不断拆分直到基线情形,然后答案往上返回。
Complete factorial(int n) so it returns n * (n-1) * ... * 1 using recursion. Use a base case for n <= 1. The checker tests several values. · 用递归完成 factorial(int n),让它返回 n * (n-1) * ... * 1。当 n <= 1 时用基本情形。检查器会测试多个值。
Click Run to see the output here. · 点击“运行”查看此处输出。
Complete sumTo(int n) so it returns 1 + 2 + ... + n using recursion. Use a base case for n <= 0. The checker tests several values. · 用递归完成 sumTo(int n),让它返回 1 + 2 + ... + n。当 n <= 0 时用基本情形。检查器会测试多个值。
Click Run to see the output here. · 点击“运行”查看此处输出。
Complete arraySum(int[] a, int i) so it returns the sum of a[i] to the end, using recursion. Base case: when i is past the last spot, return 0. The checker tests several arrays. · 用递归完成 arraySum(int[] a, int i),让它返回从 a[i] 到末尾的和。基本情形:当 i 越过最后一个位置时,返回 0。检查器会测试多个数组。
Click Run to see the output here. · 点击“运行”查看此处输出。