| English | 释义 | 拼音 |
|---|---|---|
| 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ì |
调用自己的方法
- 递归是一个方法调用自己,去解决同一问题的更小版本。
- 每个递归都需要两部分:一个基准情形和一个递归情形。
- 基准情形停止递归——一个方法直接给出答案的小输入。
- 递归情形在更小的输入上再次调用该方法。
基准情形
- 没有基准情形,方法会永远调用自己——一个
StackOverflowError。 - 基准情形不再调用就处理最小的输入。
- 例子:
factorial(0)直接返回1——不再调用。 - 总要检查:每条路径最终都会到达基准情形吗?

归并排序对每一半递归调用自身,然后合并已排序的两半
递归情形
- 递归情形做一点工作,然后在更小的输入上调用自己。
factorial(n)返回n * factorial(n - 1)——输入每次调用缩小一。- 每个调用在完成前等待更小的调用返回。
- 调用层层堆起,触到基准情形,然后回退到顶层。
调用如何堆叠
factorial(3)→3 * factorial(2)→3 * (2 * factorial(1))→3 * (2 * (1 * factorial(0))).factorial(0)返回1;然后栈回退:1, 1, 2, 6。- 每个调用在返回前保留自己那份参数副本。
- 追踪递归就是向下跟着调用,再向上跟着返回。
**每个递归都需要一个停止它的基准情形——而且每次递归调用都必须朝那个基准情形靠近(一个更小的输入)。**漏掉基准情形,或在相同或更大的输入上调用,方法就会永远递归,直到 StackOverflowError。追踪时向下跟到基准情形,再向上跟着返回。
用递归求 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.
递归是一个方法在更小的输入上调用自己。它需要一个基准情形(不再调用、直接停止)和一个递归情形(做一点工作,然后在更小的输入上递归)。调用向下堆到基准情形,再回退向上。漏掉基准情形就会得到 StackOverflowError。
factorial(3) unwinds from the base case up
fact(0) returns 1 (base case); each parent multiplies: 1, 1, 2, 6.
A recursive method is one that...
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Recursion = a method calling itself.
The base case is...
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
The base case stops the recursion.
A recursion with no reachable base case causes...
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
It recurses forever until the stack overflows.
The recursive case must call itself on...
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Each call must shrink toward the base case.
If factorial(0)=1 and factorial(n)=n*factorial(n-1), what is factorial(3)?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
3 * 2 * 1 * 1 = 6.
Each recursive call keeps its own copy of its parameters until it returns.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Calls stack independently, then unwind.