Placeholder Image

字幕列表 影片播放

  • 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.

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

  • Start with the base case.

    從基礎條件開始說起

  • 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

為了瞭解遞迴,你必須

字幕與單字

單字即點即查 點擊單字可以查詢單字解釋