Recursion
Java for AP CS A Lesson 15 2:02 English narration · English + 中文 subtitles burned in
Chapters
Transcript
A recursive method is one that calls itself, and every single one has exactly two parts.
递归方法就是会调用自己的方法， 而每一个递归方法都恰好有两个部分。
The base case is the question it can answer directly, with no further calls — here, factorial of one is one.
基准情形是它能直接回答、不需要再往下调用的那个问题—— 这里是：1 的阶乘是 1。
The recursive case calls itself with a smaller argument, and builds its answer out of that.
递归情形则用一个"更小的"参数调用它自己， 再用那个结果把自己的答案搭出来。
Smaller is the load-bearing word.
"更小"是这里最吃劲的那个词。
Now watch what actually happens.
现在看看实际发生了什么。
Factorial of four cannot finish, because it calls fact of three first.
4 的阶乘算不完，因为它得先去调用 fact(3)。
That one cannot finish either, and calls fact of two.
那一个也算不完，于是调用 fact(2)。
And so on.
如此往下。
The calls pile up, each one stuck waiting for the one below it, until the base case finally answers with a one.
调用一层层堆起来，每一层都卡在那里等下面那一层， 直到基准情形终于给出一个 1。
Nothing has been multiplied yet.
到这时为止，一次乘法都还没做过。
And now the other half.
现在是另一半。
The base case hands one back.
基准情形交还了一个 1。
Factorial of two can finally do its multiplication: two times one is two.
于是 fact(2) 终于能做它那次乘法：2 乘 1 等于 2。
That goes back up, and three times two is six.
这个值再往上交，3 乘 2 等于 6。
And finally four times six is twenty-four.
最后 4 乘 6 等于 24。
Nothing was computed on the way down — every multiplication happens on the way back.
往下走的时候什么都没算—— 每一次乘法都发生在往回走的路上。
Take the base case away and look what happens.
把基准情形拿掉，看会发生什么。
This method calls itself with n minus one for ever — it goes straight past zero into negative numbers.
这个方法会永远用 n 减 1 调用自己—— 它一路越过 0，走进负数里去。
The calls keep piling up, nothing ever answers, and Java eventually runs out of room and throws a StackOverflowError.
调用不停地堆积，永远没有人给出答案， Java 最终把空间用光，抛出 StackOverflowError。
That error almost always means a missing or unreachable base case.
这个错误几乎总是意味着： 基准情形漏了，或者永远够不着。
Four things to take with you.
带走四点。
One: a base case is the one it answers directly.
第一：基准情形是它能直接回答的那一个。
Two: the recursive case calls itself with a smaller argument.
第二：递归情形用一个更小的参数调用自己。
Three: the calls pile up, then hand values back down.
第三：调用先一层层堆起来，然后把值一层层交回去。
Four: no base case gives a StackOverflowError.
第四：没有基准情形就会 StackOverflowError。
Now write some recursion in the tasks below.
现在去下面的题里写几个递归。