字幕列表 影片播放

• In order to understand recursion, you must

為了瞭解遞迴，你必須

• first understand recursion.

先瞭解遞迴

• Having recursion in program design means that you have self-referential definitions.

在程式中有遞迴意味著程式裏有自我參考的定義

• Recursive data structures, for instance, are data structures that include themselves in their definitions.

具有遞迴形式的資料結構，指的是在定義裏就包含本身的資料結構

• But today, we're going to focus on recursive functions.

但目前我們打算專注在遞迴函式

• Recall that functions take inputs, arguments, and return a value as their output represented by this diagram here.

你應該還記得這張圖：函式需要輸入若干個參數，並傳回一個值作為輸出

• We'll think of the box as the body of the function,

我們將這個盒子想成是函式的本身

• containing the set of instructions that interpret the input and provide an output.

其中包含一組指令，用來詮釋從輸入到輸出之間所發生的事

• Taking a closer look inside the body of the function could reveal calls to other functions as well.

仔細看看函式本身，在裏面是如何呼叫其他的函式

• Take this simple function, foo, that takes a single string as input and

以這個名字叫作foo的函式為例，它需要一個字串作為輸入

• prints how many letters that string has.

然後印出這個字串裏有多少個字母（函式foo的功能為印出字串長度）

• The function strlen, for string length, is called, whose output is

我們用strlen函式計算字串的長度

• required for the call to printf.

然後再呼叫printf函式將字串的長度輸出

• Now, what makes a recursive function special is that it calls itself.

遞迴函式特別之處，就是它會呼叫自己

• We can represent this recursive call with this orange arrow looping back to itself.

在這裏我們用指向本身的橙色箭頭表示遞迴呼叫

• But executing itself again will only make another recursive call, and

遞迴呼叫引發另一次遞迴呼叫，這個過程會一而再、再而三地重覆

• another and another.

沒完沒了

• But recursive functions can't be infinite.

但是總不能這樣無窮無盡遞迴下去

• They have to end somehow, or your program will run forever.

肯定要有個方法來終止遞迴，不然程式會執行到天荒地老

• So we need to find a way to break out of the recursive calls.

我們得找出停止遞迴呼叫的方法

• We call this the base case.

就是基礎條件

• When the base case condition is met, the function returns without making another recursive call.

當滿足基礎條件的要求時，遞迴呼叫就終止了

• Take this function, hi, a void function that takes an int n as input.

以這個名字為hi的函式為例，它接受整數n作為參數

• The base case comes first.

首先驗證基底條件

• If n is less than zero, print bye and return For all other cases, the

如果n小於0，則函式印出bye之後就結束了。除此之外

• function will print hi and execute the recursive call.

函式在印出hi之後繼續遞迴呼叫

• Another call to the function hi with a decremented input value.

將參數n減去1之後再次呼叫hi函式

• Now, even though we print hi, the function won't terminate until we

即使函式在印出hi之後，仍然會繼續執行

• return its return type, in this case void.

在這個例子裏，函式回傳的型別為void

• So for every n other than the base case, this function hi will return hi of n minus 1.

除了滿足基礎條件的n值之外，函式會傳回將n值減1之後再次呼叫函式hi的結果

• Since this function is void though, we won't explicitly type return here.

由於這個函式的型別是void，它不會傳回任何值

• We'll just execute the function.

我們來執行這個函式

• So calling hi(3) will print hi and execute hi(2) which executes hi(1) one

呼叫hi(3)在印出hi之後，接著執行hi(2)，再接著執行hi(1)

• which executes hi(0), where the base case condition is met.

接下來在執行hi(0)的時候，基礎條件被滿足了

• So hi(0) prints bye and returns.

所以在hi(0)印出bye之後，遞迴過程就結束了

• OK.

太好了

• So now that we understand the basics of recursive functions, that they need

現在我們瞭解遞迴函式的概念了

• at least one base case as well as a recursive call, let's move on to a

在遞迴呼叫之外，至少要存在一個基礎條件。我們繼續

• more meaningful example.

更有意思的例子

• One that doesn't just return void no matter what.

一個不僅只是傳回void的函式

• Let's take a look at the factorial operation used most commonly in probability calculations.

我們來看看在機率計算中常會用到的階乘

• Factorial of n is the product of every positive integer less than and equal to n.

n階乘是所有小於或等於n的整數的乘積

• So factorial five is 5 times 4 times 3 times 2 times 1 to give 120.

所以5階乘是5x4x3x2x1=120

• Four factorial is 4 times 3 times 2 times 1 to give 24.

4階乘是4x3x2x1=24

• And the same rule applies to any positive integer.

同樣的規則可以套用到任意正整數

• So how might we write a recursive function that calculates the factorial of a number?

我們如何編寫計算某個整數階乘的遞迴函式呢？

• Well, we'll need to identify both the base case and the recursive call.

我們來釐清基礎條件和遞迴呼叫

• The recursive call will be the same for all cases except for the base

除了基礎條件之外，所有的遞迴呼叫長的一模一樣

• case, which means that we'll have to find a pattern that will give us our desired result.

意謂著我們得去找出求解的規律

• For this example, see how 5 factorial involves multiplying 4 by 3 by 2 by 1

以5階乘為例，它包含乘4、乘3、乘2、乘1等等的運算

• And that very same multiplication is found here, the

相同的運算也發生在

• definition of 4 factorial.

4階乘的定義上

• So we see that 5 factorial is just 5 times 4 factorial.

我們看到5階乘也不過就是5再乘上4階乘罷了

• Now does this pattern apply to 4 factorial as well?

同樣的概念如何套用到4階乘呢？

• Yes

是的

• We see that 4 factorial contains the multiplication 3 times 2 times 1, the

我們看到4階乘就是乘3、乘2、乘1

• very same definition as 3 factorial.

亦即乘於3階乘的定義

• So 4 factorial is equal to 4 times 3 factorial, and so on and so forth our

所以4階乘就是4再乘上3階乘，依此類推

• pattern sticks until 1 factorial, which by definition is equal to 1.

一直來到1階乘，根據定義，1階乘就是1

• There's no other positive integers left.

所有的正整數都處理完了

• So we have the pattern for our recursive call.

現在我們有了階乘的遞迴呼叫的規律了

• n factorial is equal to n times the factorial of n minus 1.

n階乘等於n乘上n減1階乘

• And our base case?

那麼基礎條件呢？

• That'll just be our definition of 1 factorial.

就是1階乘的定義

• So now we can move on to writing code for the function.

我們現在可以為這個函式編寫程式碼了

• For the base case, we'll have the condition n equals equals 1, where

當n值等於1的時候，基礎條件成立了

• we'll return 1.

函式回傳1

• Then moving onto the recursive call, we'll return n times the

否則就繼續執行遞迴呼叫，函式回傳n再乘於

• factorial of n minus 1.

n減去1的階乘

• Now let's test this our.

現在測試我們的成果

• Let's try factorial 4.

試試看4階乘

• Per our function it's equal to 4 times factorial(3).

在程式中，4階乘等於4乘上3階乘

• Factorial(3) is equal to 3 times factorial(2).

3階乘等於3乘上2階乘

• Factorial(2) is equal to 2 times factorial(1), which returns 1.

2階乘等於2乘上1階乘，1階乘就是1了

• Factorial(2) now returns 2 times 1, 2.

2階乘回傳2乘1，這得到2

• Factorial(3) can now return 3 times 2, 6.

3階乘回傳3乘2，這得到6

• And finally, factorial(4) returns 4 times 6, 24.

最後，4階乘回傳4乘6，這等於24

• If you're encountering any difficulty with the recursive call, pretend that

如果在遞迴呼叫時遇到任何因難，就想像

• the function works already.

函式是可以正常運作的

• What I mean by this is that you should trust your recursive calls to return

我的意思是：你一定要相信遞迴呼叫所傳回的

• the right values.

是正確的結果

• For instance, if I know that factorial(5) equals 5 times

以5階乘為例，它等於5乘上4階乘

• factorial(4), I'm going to trust that factorial(4) will give me 24.

我會相信函式factorial(4)將會傳回24

• Think of it as a variable, if you will, as if you already defined factorial(4).

就把factorial(4)想成是我們已經定義好的變數

• So for any factorial(n), it's the product of n and the previous factorial.

所以對於任一個 factorial(n)而言，它的值就是n和前一個階乘的積

• And this previous factorial is obtained by calling factorial of n minus 1.

而前一個階乘可以經由呼叫factorial(n-1)而得

• Now, see if you can implement a recursive function yourself.

現在來看看你能不能實作屬於自己的遞迴函式

• Load up your terminal, or run.cs50.net, and write a function sum

打開你的瀏覽器，在網址列鍵入run.cs50.net，寫一個求總和的函式

• that takes an integer n and returns the sum of all consecutive positive integers from n to 1.

這個函式計算1連加到n的總和

• I've written out the sums of some values to help you our.

我已經為你寫下若干數值的和

• First, figure out the base case condition.

首先要找出基礎條件

• Then, look at sum(5).

接著看看sum(5)

• Can you express it in terms of another sum?

你能不能用其他項目的和來表達sum(5)？

• Now, what about sum(4)?

那麼sum(4)呢？

• How can you express sum(4) in terms of another sum?

你如何其他項目的和來表達sum(4)呢？

• Once you have sum(5) and sum(4) expressed in terms of other sums, see

一旦你可以用其他項目的和來表達sum(5)及sum(4)

• if you can identify a pattern for sum(n).

看看你是否能找到計算sum(n)的通式

• If not, try a few other numbers and express their sums in terms of another numbers.

無果還是沒辦法的話，再嘗試其他的數值是不是能用另外的項目的和來表達

• By identifying patterns for discrete numbers, you're well on your way to identifying the pattern for any n.

嘗試過幾個數值之後，你應該可以順利找到解答任意整數n的通式

• Recursion's a really powerful tool, so of course it's not limited to

遞迴實在是太強大了，當然不限於

• mathematical functions.

數學函式

• Recursion can be used very effectively when dealing with trees for instance.

比如說遞迴可以非常有效率地處理樹的問題（樹是一種重要的資料結構）

• Check out the short on trees for a more thorough review, but for now

很快地看一下樹的結構

• recall that binary search trees, in particular, are made up of nodes, each

二元搜尋樹由節點組成

• with a value and two node pointers.

每個節點擁有自己的數值、和兩個指到其他節點的指標

• Usually, this is represented by the parent node having one line pointing

父節點會各以一條線，連接到

• to the left child node and one to the right child node.

左子樹和右子樹

• The structure of a binary search tree lends itself well

二元樹的結構使得它本身非常適合應用在

• to a recursive search.

遞迴搜尋

• The recursive call either passes in the left or the right node, but more of that in the tree short.

要嘛就是以遞迴呼的方式處理左子樹、不然就是以遞迴呼的方式處理右子樹

• Say you want to perform an operation on every single node in a binary tree.

假設你想對二元樹的每一個節點進行運算

• How might you go about that?

你會怎麼做呢？

• Well, you could write a recursive function that performs the operation

你可能寫一個遞迴函式來作到這件事

• on the parent node and makes a recursive call to the same function, passing in the left and right child nodes.

先對父節點運算，然後再分別對它的左子樹和右子樹進行遞迴呼叫

• For example, this function, foo, that changes the value of a given node and

以函式foo為例，它會將所指定的節點及

• all of its children to 1.

子樹上的所有節點的值設為1

• The base case of a null node causes the function to return, indicating

當遇到空節點時，基礎條件就成立了，這使得遞迴呼叫結束

• that there aren't any nodes left in that sub-tree.

這表示在這棵子樹上已經沒有其他的節點需要被處理

• Let's walk through it.

我們來演算一次

• The first parent is 13.

所給予的節點的值是13

• We change the value to 1, and then call our function on the left as well as the right.

我們把13改成1，然後分別為左子樹和右子樹呼叫函式

• The function, foo, is called on the left sub-tree first, so the left node

先為左子樹呼叫函式foo，於是左節點的值

• will be reassigned to 1 and foo will be called on that node's children,

被設定成1，接著再為這個節點的所有子樹呼叫函式foo

• first the left and then the right, and so on and so forth.

先是左子樹，再來是右子樹…依此類推

• And tell them that branches don't have any more children so the same process

當我們發現某個節點已經沒有任何子樹時，相同的過程

• will continue for the right children until the whole tree's nodes are reassigned to 1.

將套用到右子樹，一直到整棵樹所有的節點被設成1

• As you can see, you aren't limited to just one recursive call.

如你所見，遞迴呼叫的威力不限於此

• Just as many as will get the job done.

遞迴可以完成更多事

• What if you had a tree where each node had three children,

如果你有一棵三元樹呢？

• Left, middle, and right?

左子樹、中子樹、和右子樹？

• How would you edit foo?

你要怎麼修改函式foo？

• Well, simple.

這很簡單

• Just add another recursive call and pass in the middle node pointer.

只要對中子樹加入另一個遞迴呼叫就可以了

• Recursion is very powerful and not to mention elegant, but it can be a

遞迴十分強大、而且非常優雅，但它可能

• difficult concept at first, so be patient and take your time.

很難一開始就被理解，要有耐心，慢慢來

從基礎條件開始說起

• It's usually the easiest to identify, and then you can work

基礎條件通常很容易推導，你可以從這裏

• backwards from there.

倒著推導回去

• You know you need to reach your base case, so that might give you a few hints.

當你需要推導基礎條件時，這樣作或許可以帶來靈感

• Try to express one specific case in terms of other cases, or in sub-sets.

試試看使用其他的條件來表示此一特殊條件

• Thanks for watching this short.

謝謝觀賞

• At the very least, now you can understand jokes like this.

現在你起碼聽得懂像這樣的笑話

• My name is Zamyla, and this is cs50.

我是Zamyla，課程代號為cs50

• Take this function, hi, a void function that takes an int, n, as input.

以函式hi為例，這是型別為void的函式，它接收整數n為參數

• The base case comes first.

先來看看基礎條件

• If n is less than 0, print "bye" and return.

若n值小於0，則印出bye之後，函式就結束了

In order to understand recursion, you must

A2 初級 中文 美國腔 呼叫 節點 條件 基礎 整數 等於

遞歸 (Recursion)

• 169 15
Jjli Li 發佈於 2021 年 01 月 14 日