Recursion
C Programming Lesson 14 2:29 English narration · English + 中文 subtitles burned in
Chapters
Transcript
A recursive function is one that calls itself, and every single one has the same two parts.
递归函数就是会调用自己的函数，而每一个都有同样的两部分。
The base case: the smallest version of the problem, which you can answer straight away without calling anything.
终止条件：问题最小的那个版本， 你可以直接回答，不需要再调用任何东西。
For factorial that is one, whose factorial is one.
对阶乘来说，那就是 1，1 的阶乘是 1。
And the recursive case: the same problem, one step smaller, plus whatever this level adds.
还有递归情形：同一个问题，小一步， 再加上这一层要做的事。
Leave the base case out and it calls itself forever, until the program runs out of stack and dies.
不写终止条件，它就会永远调用自己， 直到程序把栈用光、崩掉为止。
Follow factorial of three.
跟着 3 的阶乘走一遍。
It cannot answer yet, because it needs the answer to a smaller one first, so it calls a smaller one — factorial of two — and waits.
它现在还答不上来，因为它得先要到一个更小问题的答案， 于是它去调用更小的那个——2 的阶乘——然后等着。
Factorial of two does the same and waits too.
2 的阶乘也一样，也在等。
Note what is NOT happening: no multiplying at all.
注意此刻“没有”发生的事：一次乘法都还没做。
Three calls are now open, each one still waiting on the one below it.
现在有三个调用同时开着，每一个都还在等它下面那个。
This continues until it reaches the base case, which answers one without calling anything.
这样一直往下，直到抵达终止条件， 它不调用任何东西，直接回答 1。
Now the answers travel back up, and this is where the work actually happens.
现在答案开始往回走，而真正的计算就发生在这里。
The deepest call hands back one.
最深的那个调用交回 1。
The level above it was waiting for exactly that, multiplies by two, and hands back two.
它上面那一层正是在等这个，乘以 2，交回 2。
The level above that multiplies by three and gives back six.
再上面那一层乘以 3，交回 6。
Every multiplication happened on the way up, which is precisely why each call had to wait rather than finish.
每一次乘法都发生在往回走的路上， 这正是为什么每个调用只能等着，而不能先做完。
The lesson's third task recurses along an array, which sounds harder and is not.
课程里的第三道题是沿着数组递归，听起来更难，其实不是。
The extra parameter is an index, and each call moves it forward by one.
多出来的那个参数是一个下标，每次调用把它往前推一格。
The recursive case reads exactly as it sounds: this item plus the rest.
递归情形读起来就是它字面的意思：这个元素，加上剩下的部分。
And the base case is the index reaching the end, where the function returns zero — the right choice, because zero is the value that adds nothing to a sum.
而终止条件是下标走到了末尾，这时函数返回 0—— 这个选择是对的，因为在求和里，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, or you never reach that stop.
第二：递归情形必须让问题变小，否则你永远到不了那个“停”。
Three: the answers are built on the way back up, not on the way down.
第三：答案是在往回走的路上构建的，不是在往下走的路上。
Four: no base case means the stack overflows and the program crashes.
第四：没有终止条件就会栈溢出，程序崩溃。
Now do the three tasks, and keep the test numbers small so they fit in an int.
现在去做那三道题，测试的数字保持小一点，让它们装得进一个 int。