Recursion
Python for A-Level CS Lesson 9 2:11 English narration · English + 中文 subtitles burned in
Chapters
Transcript
Recursion is a function that calls itself, and every recursive function has exactly two parts.
递归就是一个会调用自己的函数， 而每一个递归函数都恰好有两部分。
The base case is the smallest version of the problem, and it is answered outright, with no further call.
终止条件是这个问题最小的那个版本，它被直接回答，不再往下调用。
The recursive case solves the same problem one step smaller and uses that answer.
递归情形解决的是同一个问题、小一步的版本，并使用那个答案。
Factorial is the standard example: n factorial is n times the factorial of n minus one, and nought factorial is one.
阶乘是标准例子： n 的阶乘等于 n 乘以 (n-1) 的阶乘，而 0 的阶乘是 1。
Now the part this course has to cover: how the computer actually runs it.
现在说这门课必须讲到的部分：计算机到底是怎么执行它的。
Each call that is waiting for an inner one gets paused, and the paused calls pile up on something called the call stack.
每一个正在等待内层调用的调用都会被挂起， 而这些被挂起的调用会堆叠在一个叫"调用栈"的东西上。
Three calls waiting, and then the fourth reaches the base case and answers without calling anything.
三个调用在等，然后第四个抵达终止条件， 不再调用任何东西，直接给出答案。
And notice what that stack is: the same last in, first out structure from lesson four.
再注意这个栈是什么： 正是第 4 课里那个后进先出的结构。
Then the answers travel back up, and this is where the arithmetic happens.
然后答案开始往回走，而算术就发生在这里。
The base case hands back one.
终止条件交回 1。
The call above multiplies by one and hands back one.
它上面那层乘以 1，交回 1。
The next multiplies by two.
再上一层乘以 2。
The last multiplies by three and gives back six.
最上面那层乘以 3，交回 6。
Nothing at all was multiplied on the way down — which is precisely why each call had to wait rather than finish.
往下走的过程中一次乘法都没有发生—— 这正是为什么每个调用只能等着，而不能先做完。
The third task recurses to build a list rather than a number, and it reads exactly as it sounds: the list up to n is everything before it, with n on the end.
第三道题用递归构建的是一个列表，而不是一个数字， 而它读起来就是它字面的意思： 到 n 为止的列表，就是"它之前的一切"，末尾再加上 n。
Expand it once and you can see the answer assembling on the way back.
把它展开一次，你就能看到答案在回程中被拼装起来。
The base case returns an empty list — the value that adds nothing, just as nought was for a sum.
终止条件返回一个空列表—— 那个"加了等于没加"的值，就像求和时的 0 一样。
Four things to take with you.
带走四点。
One: write the base case first — it is the stop.
第一：先写终止条件——它就是那个"停"。
Two: the recursive case must shrink the problem.
第二：递归情形必须让问题变小。
Three: each waiting call sits on the call stack.
第三：每一个等待中的调用都待在调用栈上。
Four: with no base case, that stack overflows, which is a different failure from an ordinary infinite loop.
第四：没有终止条件，那个栈就会溢出， 这和普通的死循环是两种不同的失败。
Now do the three tasks.
现在去做那三道题。