Placeholder Image

字幕表 動画を再生する

  • In order to understand recursion, you must

    >> ZAMYLA:理解するために 再帰は、以下を行う必要があり

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


  • 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


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


  • 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


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


  • 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


  • 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


  • the function works already.

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

  • 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


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


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

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

  • Load up your terminal, or, 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


  • 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


  • 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

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

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

    どのようにして和を表現することができます(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.


  • 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


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


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

    我々は、値を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.

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

In order to understand recursion, you must

>> ZAMYLA:理解するために 再帰は、以下を行う必要があり


ワンタップで英和辞典検索 単語をクリックすると、意味が表示されます