[音楽再生] DOUG LLOYD：あなたはおそらくだと思います コー​​ドだけでタスクを実行するために使用されます。 あなたはそれを書き出します。 それは何かを。 それはかなりそれです。 あなたはそれをコンパイルします。 あなたがプログラムを実行します。 あなたが行ってもいいです。 しかし、それを信じるかどうか、もし あなたは、長い時間のためにコード化 あなたが実際に見に来るかもしれません 美しいものとしてコード。 これは、問題を解決します 非常に興味深い方法、 または実際に何かあります それは見え方についてきちんとしました。 あなたは笑っ可能性があります 私に、それは本当です。 そして、再帰が一つの方法であります ソートのこのアイデアを得るために 美しい、エレガントに見えるのコード。 その方法で問題を解決します 興味深い、視覚化しやすいです、 そして、驚くほど短いです。 方法再帰作品 再帰関数は、あります 呼び出す関数として定義されています 自身の実行の一部として。 それは少し奇妙に思えるかもしれません、 私たちは少し表示されます これは瞬間にどのように機能するかについて。 やはり、これらの 再帰的な手順があります そうエレガントになるだろう 彼らが行っているので、 せずにこの問題を解決するために すべてのこれらの他の機能を有します またはこれらの長いループ。 あなたはこれらの再帰的なことがわかります 手順は非常に短い見に行くされています。 そして、彼らは本当にするつもりされています あなたのコードは、多くのより美しく見えます。 私はあなたの例をあげます この方法を確認します 再帰的な手順が定義されるかもしれません。 ですから、この精通している場合 何年も前に数学の授業から、 呼ばれるものがあります 通常、階乗関数 感嘆符、と表記します すべての正の整数の上に定義されています。 そして、道のn 階乗を計算します あなたはすべてを掛けています より少ない数 あるいはnに等しいですtogether-- すべての整数未満 または一緒のnに等しいです。 だから5階乗は5回です 4回3回2回1。 そして、4の階乗は4倍です 3回2回1というように。 あなたのアイデアを得ます。 プログラマとして、私たちにはありません nは、感嘆符を使用します。 だから我々は階乗を定義します n個の事実として機能します。 そして、我々は作成するために階乗を使用します 問題の再帰的なソリューションを提供します。 そして、私はあなたが見つけるかもしれないと思います それは多くはより視覚的だと 反復より魅力的 このバージョンの、どの 我々はまた、現時点で見てみましょう。 だからここのカップルです facts--しゃれintended-- 約factorial-- 階乗関数。 私が言ったように1の階乗は、1です。 2の階乗は2回1です。 3の階乗は3です ように回2回1、と。 我々はすでに4と5について話しました。 しかし、これを見て、これは真実ではないのですか？ ちょうど2の階乗されていません 1の2倍の階乗？ 私が意味する、1の階乗は1です。 では、なぜ私たちはそれを言うことができません、 2の階乗は2回1であることから、 それは実際には2倍です 1の階乗？ そして、そのアイデアを拡張 3の階乗ではありません わずか3回2の階乗？ そして、4の階乗は4倍です ように3の階乗、と？ 実際には、階乗 することができます任意の数だけ 我々種類あれば表現すること 永遠にこれを実施しています。 私たちは、この種の一般化することができます 階乗問題 それだとしてn回 nの階乗マイナス1。 これは、n回の製品です すべての数値は私よりも少ないです。 このアイデアは、この 問題の一般化、 私たちは、再帰的にすることができます 階乗関数を定義します。 あなたは、関数を定義する場合 再帰的に、あります それの一部である必要がある2つの事。 あなたはと呼ばれるものを持っている必要があります あなたがそれをトリガー、基本ケース、 再帰的な処理を停止します。 呼び出しそれ以外の場合は、機能 あなたがimagine--かもしれないとしてitself-- 永遠に行くことができます。 関数は、関数を呼び出します 関数呼び出しを呼び出します 関数は、関数を呼び出します。 あなたが方法を持っていない場合 、あなたのプログラムを、それを停止します 効果的にスタックされます 無限ループで。 それは、最終的にクラッシュします それはメモリが不足しますので。 しかし、それは的外れです。 私たちは停止するいくつかの他の方法を持っている必要があります 私たちのプログラムがクラッシュ以外のもの、 クラッシュしたプログラムですので、 おそらく美しいかエレガントではありません。 そして、私たちはこのベースケースと呼びます。 これは簡単な解決策であります 停止問題に 発生から再帰的処理。 だから、の一部です 再帰関数。 第二部は、再帰的なケースです。 そして、これはどこに再帰です 実際に行われます。 これは、ここで 関数が自分自身を呼び出します。 それはまさにで自分自身を呼び出しません それが呼ばれたのと同じ方法。 それはわずかな変化になるだろう それはそれはだ問題を作ります ちょっぴり小さい解決しようとしています。 しかし、それは一般的にバックを渡します 溶液の大部分を解決します ラインの下の別の呼び出しに。 これらのルックスのどちら ここでは基本ケースのような？ どのようなこれらのルックスの一つ 問題の最も簡単な解決法は？ 我々は階乗の束を持って、 我々は続けることができます 6、7、8、9、10 on--行く、など。 しかし、これらのようなルックスの1 良い場合は、基本ケースのように。 これは非常にシンプルなソリューションです。 私たちは、何か特別なことをする必要はありません。 1の階乗は、ちょうど1です。 我々は、いずれかを行う必要はありません 乗算ですべて。 私たちが行っているかのように思えます 試してみて、この問題を解決するために、 私たちは停止する必要があります どこかに再帰、 我々は、おそらく停止したいです それ私達は1を取得。 私たちは、その前に停止する必要はありません。 我々が定義しているのであれば 私たちの階乗関数、 ここでのスケルトンです どのように我々はそれを行う可能性があります。 私たちは、これらの2 things--をプラグインする必要があります ベースケースと再帰的なケース。 ベースケースは何ですか？ nが1に等しい場合、戻り1--ことです 本当に簡単な問題は解決します。 1の階乗は1です。 これは、1回のものではありません。 それはちょうど1です。 それは非常に簡単事実です。 そしてそうそれは私たちのベースケースであることができます。 我々はこの中に1を渡される場合 この関数は、私たちは1を返します。 再帰は何ですか 場合は、おそらくのように見えますか？ 他のすべての番号について 1以外にも、パターンは何ですか？ さて、私たちは取っている場合 nの階乗、 それはだn回nの階乗マイナス1。 私たちは3の階乗を取っている場合は、 それは、3マイナス1の3倍の階乗です または2。 そして、私たちはいないのであれば それ以外の場合は、1を見て リターンn回 nの階乗マイナス1。 それはかなり簡単です。 そして少し持っていることのために よりクリーンでエレガントなコード、 我々はシングルラインループを持っている場合ことを知っています または単一行の条件分岐、 我々はすべてを取り除くことができます 彼らの周りの中括弧。 だから我々はこれにこれを統合することができます。 これはまったく同じを持っています このような機能。 私は巻き毛を離れて取っています ブレース、一つだけの行がありますので、 これらの条件分岐の内部。 したがって、これらは同じように動作します。 nが1に等しい場合、1を返します。 そうでない場合はn回を返します nの階乗マイナス1。 だから我々はより小さな問題を作っています。 nが5のようにして起動した場合、我々はするつもりです 4の5倍の階乗を返します。 そして、我々は我々が話すとき分で表示されます コー​​ルに関するstack--別のビデオで ここで、我々はについて話します 私たちは学びますstack--呼び出します まさにこのプロセスが機能する理由について。 しかし、5の階乗は言いながら、 4の階乗5回を返し、4 言おうとしている、[OK]を、よく、リターン 4回3の階乗。 あなたが見ることができるようにと、私たちはしています ソートの1に近づいて。 私たちは近づいていると そのベースケースに近いです。 そして、我々はベースケースをヒットしたら、 以前のすべての機能 彼らが探していた答えを持っています。 2の階乗は、リターンを言っていました 1の2倍の階乗。 まあ、1を返します1の階乗。 階乗のためだからコール 2の2倍の1を返すことができ、 との階乗にそれをお返し その結果を待っている3、。 そして、それは計算することができます その結果、3回2は、6です および4の階乗に戻ってそれを与えます。 そして再び、私たちは持っています 呼び出しスタック上のビデオ これは、少し例示されている場所 私が今言っている以上のもの。 しかし、これはそれです。 これだけでは、を解決します 数値の階乗を計算します。 これは、コードの唯一の4行です。 それは右、かなりクールですか！ それはセクシーなのようなものです。 一般的にはそうではなく、 常に、再帰関数 ループを置き換えることができます 非再帰関数。 そこでここでは、並んでは、反復的です 階乗関数のバージョン。 これらの計算の両方 まったく同じこと。 彼らは両方のnの階乗を計算します。 左のバージョン それを行うには再帰を使用しています。 右のバージョン それを行うための反復を使用しています。 予告、我々は宣言する必要が 可変整数製品。 そして、我々のループ。 あれば、nは、我々0より大きいとして nでその製品を乗じておきます そして、なるまでのnをデクリメント 我々は製品を計算します。 だから、この2つの機能、再び、 全く同じことを行います。 しかし、彼らは、それをしません まったく同じ方法。 さて、それはすることが可能です 複数のベースを持っています 場合か、複数の 再帰的な場合、依存 あなたの関数がやろうとしているものに。 あなたは必ずしもだけに限定されるものではありません 単一塩基の場合、または単一の再帰 ケース。 何かのですから、例えば 複数のベースケースと this--かもしれません フィボナッチ数列。 あなたはから思い出して 小学校時代 フィボナッチ数列は、定義されていること this--のように最初の要素は0です。 2番目の要素は1です。 それらの両方は、単に定義です。 その後、他のすべての要素が定義されています nはマイナス1とnマイナス2の和として。 だから、第三元素 0プラス1であるだろう。 そして、4番目の要素 二番目の要素、1になり、 第三元素、1を加えました。 そして、それは2になります。 などなどのように。 したがって、この場合には、我々は、2つのベースケースを有します。 nが1に等しい場合、0を返します。 nが2に等しい場合、1を返します。 それ以外の場合は、n個のフィボナッチを返します マイナス1プラスNマイナス2のフィボナッチ。 だから、複数のベースケースです。 何複数の再帰的なケースについてはどうですか？ まあ、何かがあります コラッツ予想と呼ばれます。 私が言うつもりはありません、 あなたはそれが何であるかを知っています、 それは実際に私たちの最後のだから この特定のビデオのための問題。 そして、それは私たちの運動です 一緒に動作するように。 だからここに何がありますか コラッツの問題is-- それは、すべての正の整数に適用されます。 そして、それはそれだと推測 取り戻すことが常に可能 1に次の手順を実行する場合。 nが1である場合、停止。 nが1であれば私たちは、1に戻って持っています。 それ以外の場合、この通過します プロセス再びN 2で割りました。 あなたは1に戻って得ることができるかどうかを確認します。 nが奇数の場合それ以外の場合は、通過 3Nプラス1に再びこのプロセス、 または3回Nプラス1。 そこでここでは、単一のベースケースを持っています。 nが1に等しい場合、停止します。 私たちはそれ以上の再帰を行っていません。 しかし、我々は、二つの再帰的な例があります。 nが偶数の場合、我々は1再帰を行います 場合、呼び出しN 2で割りました。 nが奇数の場合、我々は別の操作を行います 3回Nプラス1の再帰ケース。 だから、このビデオの目標はあります 秒を取るために、ビデオを一時停止、 これを試してみて、書き込み 再帰関数コラッツ ここであなたは、値nに渡し、 それはどのように多くのステップを計算し あなたはn個から起動した場合1に取得するのにかかります あなたは上記のこれらの手順をフォローアップ。 nが1である場合、0のステップをとります。 それ以外の場合は、になるだろう しかし、一歩プラスを取ります それはどちらかのnを取る多くのステップ nが偶数の場合は2で割った、または3Nプラス1 nが奇数の場合。 今、私はここで画面上に置かれています あなたのためのテスト物事のカップル、 あなたのためのテストケースのカップル、参照するには これらの様々なコラッツ番号が何でありますか、 また、イラスト そのステップの そうすることができますを経てする必要があります ソートのアクションで、このプロセスを参照してください。 nが等しい場合にそう 図1は、n個のこのCollat​​zは0です。 あなたが行う必要はありません 何が1に戻って取得します。 あなたは既にそこにいます。 nが2である場合、かかります 1に到達する一歩。 あなたは2で始まります。 まあ、2は1に等しくありません。 だから、一歩になるだろう プラスしかし多くのステップを 2で割ったn個になります。 2で割った2は1です。 だから、しかし一歩を取るプラス それは1にかかる多くのステップ。 図1は、ゼロの手順を実行します。 あなたが見ることができるように3のために、あります かなりの数のステップが関与します。 あなたは3から行きます。 そして、あなたがに行きます 10、5、16、8、4、2、1。 これは、1に戻って取得するために7つのステップを取ります。 あなたが見ることができるように、あります ここではカップル他のテストケース あなたのプログラムをテストします。 だからもう一度、ビデオを一時停止します。 そして、私はここでバックジャンプ行きますよ 実際のプロセスがここにあるもの、 この予想は何ですか。 あなたが把握することができます参照してください n個のコラッツを定義する方法 何それを計算するように 手順は1に取得するのにかかります。 だからうまくいけば、あなたがビデオを一時停止しています あなたは私を待っているのではありません ここにあなたの答えを得ました。 しかし、あなたがしている場合は、よく、 ここでの答えは、とにかくです。 そこでここでは可能な定義です このCollat​​z関数の。 nがある場合は私たちのベースはcase-- 1に等しい、我々は0を返します。 これは、いずれかを取ることはありません ステップ1に戻って取得します。 それ以外の場合は、2つの再帰的cases--を持っています 偶数用と奇数のための1つ。 私が偶数のテスト方法 n個のMOD 2が0に等しいかどうかを確認することです。 これは、再度、基本的に 質問をして、 あなたは何のmod is--を思い出した場合であれば、私 2で割るnは、そこには余りないのですか？ それが偶数になります。 だから、n個のMOD 2は0に等しい場合 テストでは、これは偶数です。 もしそうなら、私は1を返すようにしたいです、 これは間違いであるため、 一歩プラスのコラッツを取ります どんな数私の半分です。 そうでなければ、私は1を返すようにしたいです プラスコラッツの3倍のNプラス1。 それは他のでした 再帰的ステップ、我々 計算するために取ることができます ステップ数Collat​​z-- それが戻って取得するのにかかります 1に番号を与えられました。 だからうまくいけば、この例 あなたに少しを与えました 再帰的手続きの味の。 うまくいけば、あなたはコードがあると思います もう少し美しく実装されていれば エレガントな、再帰的な方法です。 でもない場合でも、再帰があります それにもかかわらず、実際に強力なツール。 そしてそれは間違いなく何か 周りにあなたの頭を取得するには、 あなたが作成することができますので、 再帰を使用してかなりクールプログラム それは、そうでなければ書くことは複雑かもしれません あなたはループや反復を使用している場合。 私はダグロイドです。 これはCS50です。