Recursion: base case and recursive case · 递归:终止条件与递归情形
A function that calls itself
- Recursion is when a function calls itself to solve a smaller version of the same problem.
- It needs two parts: a base case that stops, and a recursive case that shrinks the problem.
- Without a base case, it would call itself forever and crash.
会调用自己的函数
- 递归是指一个函数调用它自己,来解决同一个问题的更小版本。
- 它需要两个部分:一个能停下来的终止条件,和一个让问题变小的递归情形。
- 没有终止条件,它就会永远调用自己然后崩溃。
The base case
- The base case is the smallest problem you can answer directly, with no more calls.
- For factorial,
0!and1!are both1— that is the base case. - Always handle the base case first, so the recursion has somewhere to stop.
终止条件
- 终止条件是你能直接回答、不需要再调用的最小问题。
- 对阶乘来说,
0!和1!都是1—— 这就是终止条件。 - 总是先处理终止条件,这样递归才有地方停下来。
The recursive case
- The recursive case solves the problem using the answer to a smaller one.
n! = n × (n - 1)!, sofactorial(n)returnsn * factorial(n - 1).- Each call must move closer to the base case, or it will never stop.
递归情形
- 递归情形用一个更小问题的答案来解决当前问题。
n! = n × (n - 1)!,所以factorial(n)返回n * factorial(n - 1)。- 每次调用都必须更接近终止条件,否则它永远不会停。
#include <stdio.h>
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
int main(void) {
printf("%d\n", factorial(5)); // 120
return 0;
}
Recursion over an array
- You can recurse along an array by passing an index that moves forward each call.
- The base case is "the index has reached the end" (return
0for a sum). - The recursive case is
a[i] + sum(a, i + 1, n)— this item plus the sum of the rest.
在数组上递归
- 你可以沿着数组递归,办法是传入一个每次调用都向前移动的下标。
- 终止条件是“下标到达末尾”(求和时返回
0)。 - 递归情形是
a[i] + sum(a, i + 1, n)—— 当前这个元素,加上其余部分的和。
Common mistakes
- Recursion needs a base case, or the call stack overflows.
- Each call must move closer to the base case.
常见错误
- 递归需要基准情形,否则调用栈会溢出。
- 每次调用都要更靠近基准情形。
Now you try
- Write the base case first, then the recursive case that calls itself on a smaller input.
- Keep test values small so the numbers stay inside an
int. - Do not write a
main— the checker provides one.
现在轮到你了
- 先写终止条件,再写在更小输入上调用自己的递归情形。
- 测试值保持小一些,让数字留在
int范围内。 - 不要自己写
main—— 检查器会提供。
Recursion returns up · 递归往上返回
Calls split to a base case, then values return up. · 调用拆分到基线情形,然后值往上返回。
Complete int factorial(int n) using recursion: return 1 for n <= 1 (the base case), otherwise n * factorial(n - 1). Do not · 不 write a main. · 用递归完成 int factorial(int n):当 n <= 1 时返回 1(终止条件),否则返回 n * factorial(n - 1)。不要写 main。
Click Run to see the output here. · 点击“运行”查看此处输出。
Complete int power(int base, int exp) using recursion (assume exp >= 0): base to the power 0 is 1, otherwise base * power(base, exp - 1). Do not · 不 write a main. · 用递归完成 int power(int base, int exp)(假设 exp >= 0):base 的 0 次方是 1,否则是 base * power(base, exp - 1)。不要写 main。
Click Run to see the output here. · 点击“运行”查看此处输出。
Complete int array_sum(const int a[], int i, int n) using recursion: it returns the sum of a[i] up to a[n-1]. Base case: i >= n returns · 返回值 0. Do not · 不 write a main. · 用递归完成 int array_sum(const int a[], int i, int n):返回从 a[i] 到 a[n-1] 的和。终止条件:i >= n 时返回 0。不要写 main。
Click Run to see the output here. · 点击“运行”查看此处输出。