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之後，函式就結束了