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

私たちは、体のように箱を考えるよ のセットを含む関数、

prints how many letters that string has.

解釈の指示 入力及び出力を提供する。

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

体の内部を詳しく見てとる この関数はへの呼び出しを明らかにしなかった

required for the call to printf.

他の機能にも。

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

この単純な関数を取る、fooという、その 入力として1つの文字列を受け取り、

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

文字列の長さの関数はstrlen、、 その出力である、と呼ばれている

another and another.

printfのへの呼び出しのために必要。

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.

しかし、再帰関数 無限にすることはできません。

The base case comes first.

彼らは何とか終わらなければならない、あるいは、あなたの プログラムは永遠に実行されます。

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

>> だから我々は破る方法を見つける必要がある 再帰呼び出しが不足しています。

function will print hi and execute the recursive call.

私たちは、基本ケース、これを呼び出します。

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

ベースケース条件が満たされたときに、 この関数はせずに返します

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

別の再帰呼び出し。

return its return type, in this case void.

HI、void関数をこの関数を取る すなわち、入力としてint型のnを取ります。

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

ベースケースは最初に来る。

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

nが0未満である場合、印刷してバイバイ その他の場合のお返し、

We'll just execute the function.

この関数はハイテク印刷して実行されます 再帰呼び出し。

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

を持つ関数こんにちはへの別の呼び出し デクリメント入力値。

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

>> 今、我々はハイ印刷にもかかわらず、 この関数は、私たちまで終了しません

So hi(0) prints bye and returns.

その戻り値の型を返す、 この場合のボイド中。

OK.

したがって、すべてのNベースケース以外では、 この関数こんにちはこんにちは戻ります

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

Nのマイナス1。

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.

だから、（3）のHiが出力されますこんにちは呼び出し、 ハイ（2）、（1）1ハイを実行する実行

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

ハイを実行する（0）ここで、 ベースケース条件が満たされている。

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

だから、ハワイ（0）BYE出力し、リターン。

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

>> [OK]をクリックします。

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

だから今我々は基本を理解していること 彼らが必要とする再帰関数、

And the same rule applies to any positive integer.

少なくとも1つのベースケースだけでなく、 再帰呼び出し、のはに移りましょう

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

nの階乗は、すべての製品である 未満の正の整数

And that very same multiplication is found here, the

そしてnに等しい。

definition of 4 factorial.

そう階乗5は5倍4倍である 3回2回1 120を得た。

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

四階乗は4回3回です 2回1 24を得た。

Now does this pattern apply to 4 factorial as well?

同じルールが適用されます 任意の正の整数に。

Yes

>> では、どのように再帰的に書くかもしれません 階乗を計算する関数

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

数の？

very same definition as 3 factorial.

まあ、我々は両方を識別する必要があります ベースケースと再帰呼び出し。

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

再帰呼び出しは同じになります ベースを除くすべてのケースについて

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

我々はする必要がありますことを意味した場合、 私たちに与えるパターンを見つける私たちの

There's no other positive integers left.

望ましい結果。

So we have the pattern for our recursive call.

>> この例では、どのように5の階乗を参照してください。 1によって2で3で4を乗じ関与

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

そして、それは非常に同じ乗算 、ここで発見された

And our base case?

4の階乗の定義。

That'll just be our definition of 1 factorial.

だから我々は5の階乗であることがわかり ただ5回4階乗。

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

今、このパターンが適用されません 階乗4にも同様に？

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

はい。

we'll return 1.

私たちは、4の階乗が含まれていることを参照してください。 乗算3回2回1、

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

3階乗として非常に同じ定義。

factorial of n minus 1.

そう4階乗は4倍に等しい3 階乗などなど我々の

Now let's test this our.

パターンは、1階乗までこだわった 定義により1に等しい。

Let's try factorial 4.

>> 他の正はありません 整数は残しました。

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

だから我々はのためのパターンを持っている 私たちの再帰呼び出し。

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

nの階乗をn倍に等しい nの階乗マイナス1。

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

そして、我々のベースケース？

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

それはちょうど我々の定義になるでしょう 1階乗の。

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

>> だから今、私たちは、書面に進むことができます 関数のコード。

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

基本ケースのために、我々は持っているだろう 条件nが1に等しいと、等しい

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

我々は1が返されます。

the function works already.

そして、再帰呼び出しに移動し、 我々は、n回戻ります

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

nの階乗マイナス1。

the right values.

>> それでは、私たちのこれをテストしてみましょう。

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

それでは階乗4を試してみましょう。

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

私達の機能ごとにそれは等しいです 4回階乗（3）。

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

階乗は（3）に等しい 3回の階乗（2）。

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

階乗は（2）2倍に等しい 1を返し階乗（1）、。

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

階乗は（2）現在、2回1、2を返します。

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

階乗は（3）今戻ることができます 3回2、6。

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

そして最後に、階乗（4） 4回6、24を返します。

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

>> あなたはどんな困難に遭遇している場合 再帰呼び出しで、それをふり

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

正しい値。

Can you express it in terms of another sum?

例えば、私が知っている場合、その 階乗（5）は、5倍に等しい

Now, what about sum(4)?

階乗（4）、私はそれを信頼するつもりだ 階乗は（4）私に24を与える。

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

もしあれば、変数として考えて 、あるかのようにすでに定義されます

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

階乗（4）。

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

したがって、すべての階乗（N）のために、それはだ 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.

そして、この前の階乗 呼び出すことによって得られる

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

nの階乗マイナス1。

mathematical functions.

>> あなたが実装できるかどうか、今、参照してください。 再帰的な自分を機能します。

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

ご使用の端末をロード、またはrun.cs50.net、 と関数の合計を送る

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

すなわち整数nを受け取り、返し すべての連続した​​正の合計

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

nは1の整数。

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.

次に、（5）の和を見てください。

The structure of a binary search tree lends itself well

あなたは用語でそれを表現することができます 別の合計の？

to a recursive search.

今、何を（4）の和はどうでしょうか？

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

どのようにして和を表現することができます（4） 別の合計の面で？

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

>> あなたは合計を取得したら（5）と和（4） 他の和で表さ参照

How might you go about that?

あなたが特定できる場合 和するためのパターン（N）。

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

離散的なパターンを識別することにより、 数字は、あなたがにあなたの方法にもしている

all of its children to 1.

任意のnのパターンを識別する。

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.

のために木に短いをチェックしてください より徹底した見直しが、今の

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

で、その二分探索木をリコール 特に、各ノードで構成されている

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

値と2ノードポインタと。

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

通常、これは次式で表される。 一行のポインティングを有する親ノード

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

左の子ノードと1に 右の子ノードへ。

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.

再帰検索する。

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?

さて、あなたは再帰を書くことができます 演算を実行する関数

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

たとえば、この機能、fooという、その 指定されたノードの値を変更し、

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

1にそのすべての子。

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.

最初の親は13です。

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

我々は、値を1に変更して、呼び出し 私たちの左の機能だけでなく、

Thanks for watching this short.

右のように。

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

関数fooが、左側に呼び出された 最初の部分木なので、左ノード

My name is Zamyla, and this is cs50.

1とfooに再割り当てされます そのノードの子で呼び出される、

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

最初の左と右、 などなど。

The base case comes first.

そして枝が持っていないことを伝える 同じプロセスので、任意のより多くの子供

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

右の子供たちのために継続します ツリー全体のノードがあるまで、