Recursion · 递归
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| Recursion/rɪˈkɜːʃn/ | 递归 | dì guī |
| base case/beɪs keɪs/ | 基准情形 | jī zhǔn qíng xíng |
| recursive case/rɪˈkɜːsɪv keɪs/ | 递归情形 | dì guī qíng xíng |
| unwind/ʌnˈwaɪnd/ | 回退 | huí tuì |
A method that calls itself
- Recursion 递归 is when a method calls itself to solve a smaller version of the same problem.
- Every recursion needs two parts: a base case 基准情形 and a recursive case 递归情形.
- The base case stops the recursion — a small input the method answers directly.
- The recursive case calls the method again on a smaller input.
调用自己的方法
- 递归是一个方法调用自己，去解决同一问题的更小版本。
- 每个递归都需要两部分：一个基准情形和一个递归情形。
- 基准情形停止递归——一个方法直接给出答案的小输入。
- 递归情形在更小的输入上再次调用该方法。
The base case
- Without a base case, a method calls itself forever — a
StackOverflowError. - The base case handles the smallest input without another call.
- Example:
factorial(0)returns1directly — no more calls. - Always check: does every path eventually reach the base case?
基准情形
- 没有基准情形，方法会永远调用自己——一个
StackOverflowError。 - 基准情形不再调用就处理最小的输入。
- 例子：
factorial(0)直接返回1——不再调用。 - 总要检查：每条路径最终都会到达基准情形吗？
The recursive case
- The recursive case does a little work, then calls itself on a smaller input.
factorial(n)returnsn * factorial(n - 1)— the input shrinks by one each call.- Each call waits for the smaller call to return before finishing.
- The calls stack up, hit the base case, then unwind 回退 back to the top.
递归情形
- 递归情形做一点工作，然后在更小的输入上调用自己。
factorial(n)返回n * factorial(n - 1)——输入每次调用缩小一。- 每个调用在完成前等待更小的调用返回。
- 调用层层堆起，触到基准情形，然后回退到顶层。
How the calls stack
factorial(3)→3 * factorial(2)→3 * (2 * factorial(1))→3 * (2 * (1 * factorial(0))).factorial(0)returns1; then the stack unwinds:1, 1, 2, 6.- Each call keeps its own copy of the parameters until it returns.
- Tracing a recursion means following the calls down, then the returns up.
调用如何堆叠
factorial(3)→3 * factorial(2)→3 * (2 * factorial(1))→3 * (2 * (1 * factorial(0)))。factorial(0)返回1；然后栈回退：1, 1, 2, 6。- 每个调用在返回前保留自己那份参数副本。
- 追踪递归就是向下跟着调用，再向上跟着返回。
Every recursion needs a base case that stops it — and each recursive call must move TOWARD that base case (a smaller input). Miss the base case, or call on the same or a larger input, and the method recurses forever until a StackOverflowError. Trace by following calls down to the base case, then the returns back up.
**每个递归都需要一个停止它的基准情形——而且每次递归调用都必须朝那个基准情形靠近（一个更小的输入）。**漏掉基准情形，或在相同或更大的输入上调用，方法就会永远递归，直到 StackOverflowError。追踪时向下跟到基准情形，再向上跟着返回。
sum(n) = 1 + 2 + … + n by recursion:
- Base case:
if (n == 0) return 0; - Recursive case:
return n + sum(n - 1); sum(3)→3 + sum(2)→3 + (2 + sum(1))→ … →6.
用递归求 sum(n) = 1 + 2 + … + n：
- 基准情形：
if (n == 0) return 0; - 递归情形：
return n + sum(n - 1); sum(3)→3 + sum(2)→3 + (2 + sum(1))→ … →6。
Recursion is a method calling itself on a smaller input. It needs a base case (stops directly, no more calls) and a recursive case (does a little work, then recurses on a smaller input). Calls stack down to the base case, then unwind back up. Miss the base case and you get a StackOverflowError.
递归是一个方法在更小的输入上调用自己。它需要一个基准情形（不再调用、直接停止）和一个递归情形（做一点工作，然后在更小的输入上递归）。调用向下堆到基准情形，再回退向上。漏掉基准情形就会得到 StackOverflowError。
factorial(3) unwinds from the base case up · factorial(3) 从基准情形向上展开
fact(0) returns 1 (base case); each parent multiplies: 1, 1, 2, 6. · fact(0) 返回 1（基准情形）；每个父节点相乘：1, 1, 2, 6。
A recursive method is one that... · 递归方法是一种……
Recursion = a method calling itself. · 递归 = 方法调用自己。
The base case is... · 基准情形是……
The base case stops the recursion. · 基准情形停止递归。
A recursion with no reachable base case causes... · 一个没有可到达基准情形的递归会导致……
It recurses forever until the stack overflows. · 它永远递归，直到栈溢出。
The recursive case must call itself on... · 递归情形必须在……上调用自己。
Each call must shrink toward the base case. · 每次调用都必须朝基准情形缩小。
If factorial(0)=1 and factorial(n)=nfactorial(n-1), what is factorial(3)? · 若 factorial(0)=1 且 factorial(n)=nfactorial(n-1)，factorial(3) 是多少？
3 * 2 * 1 * 1 = 6. · 3 * 2 * 1 * 1 = 6。
Each recursive call keeps its own copy of its parameters until it returns. · 每次递归调用在返回前保留自己那份参数副本。
Calls stack independently, then unwind. · 调用各自独立堆叠，然后回退。