>> [音樂播放]
>> 道格·勞埃德：你可能認為， 代碼只是用來完成任務。
你寫出來。
它做一些事情。
這幾乎是它。
>> 你編譯它。
運行該程序。
你是好去。
>> 但是，不管你信不信，如果 你的代碼很長一段時間，
你居然不妨來看看 代碼東西是美麗的。
它解決了在一個問題 一個非常有趣的方式，
或有只是一些真正 整齊的有關它的樣子。
你可能會笑 我，但這是事實。
和遞歸是一種方式 排序得到這個想法
美麗的，優雅的外觀的代碼。
它解決的方式的問題， 很有意思，很容易想像，
而令人驚訝的短。
>> 該方法遞歸作品 是，遞歸函數
被定義為一個函數調用 本身作為其執行的一部分。
這似乎有些奇怪， 我們會看到一點點
關於如何工作的時刻。
但同樣，這些 遞歸程序
會是如此優雅 因為他們會
解決這個問題，而無需 擁有所有這些功能
還是這些長循環。
你會看到，這些遞歸 程序要看看這麼短。
他們真的會做 你的代碼看起來很多更漂亮。
>> 我給你舉個例子 這怎麼看
遞歸過程可能被定義。
所以，如果你熟悉這個 從數學課很多年前，
有被稱為東西 階乘功能，這通常是
表示為一個感嘆號，這 是指對所有的正整數。
和的方式使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只 2倍的1的階乘？
我的意思是，1的階乘是1。
那麼，為什麼我們不能只是說， 自2階乘是2倍1，
它實際上只是2倍 1階乘？
>> 然後擴展這一想法， 是不是3的階乘
短短3倍2的階乘？
和4的階乘的4倍 3，等等的階乘？
事實上，階乘 任何數量可以只
如果我們表達一種 攜帶這一點，直到永遠。
那種我們可以概括 階乘問題
因為它的n倍 階乘ñ減1。
它的n倍的產物 所有的數字比我少。
>> 這樣的想法，這 問題的概括，
允許我們遞歸 定義階乘函數。
當你定義一個函數 遞歸，有
兩件事情，需要成為它的一部分。
你需要有一種叫 基本情況，其中，當你觸發它，
將停止遞歸過程。
>> 否則，一個函數調用 itself--你可能imagine--
可以永遠持續下去。
函數調用函數 調用函數調用
該函數調用的函數。
如果你沒有辦法 停止它，你的程序
將得到有效卡住 在無限循環。
它會崩潰，最終， 因為它會耗盡內存。
但是，這是題外話。
>> 我們必須要阻止一些其他的方式 除了我們的程序崩潰的事情，
因為一個程序崩潰是 也許不漂亮或優雅。
因此，我們稱之為基本情況。
這是一個簡單的解決方案 到停止的問題
遞歸過程的發生。
所以這是的一部分 遞歸函數。
>> 第二部分是遞歸情況下。
而這正是遞歸 將實際發生。
這是其中 功能調用自身。
>> 它不會調用自身完全相同 以同樣的方式，它被稱為。
這將是一個輕微的變化 這使得該問題是
試圖解決一個很小的有點小。
但一般通過降壓 的解決本體溶液的
到不同的呼叫的路線。
>> 這些長相 像基本情況嗎？
這些看起來像一個 最簡單的解決問題的方法？
我們有一大堆的階乘的， 我們可以繼續
去on-- 6，7，8，9，10，等等。
>> 但這些貌似之一 良好的情況下是基本情況。
這是一個非常簡單的解決方案。
我們並沒有做什麼特別的事情。
>> 1的階乘是只有1。
我們沒有做任何 乘法可言。
好像如果我們要 嘗試和解決這個問題，
我們需要停止 遞歸的地方，
我們可能要停止 它，當我們得到1。
我們不希望在這之前停止。
>> 因此，如果我們定義 我們的階乘函數，
這裡有一個骨架 我們如何做到這一點。
我們需要在這兩個things--堵塞 基本情況和遞歸情況下。
什麼是基本情況？
如果n等於1，返回1--這是 要解決一個非常簡單的問題。
>> 1的階乘是1。
這不是1次東西。
這只是1。
這是一個非常簡單的事實。
因此，可以是我們的基本情況。
如果獲得通過1到這個 功能，我們就返回1。
>> 什麼是遞歸 情況大概是什麼樣子？
對於每一個其他數 除了1，什麼模式？
那麼，如果我們正在做 n的階乘，
的n是n次的階乘減1。
>> 如果我們採取的3階乘， 它是3負1 3倍的階乘，
或2。
所以，如果我們不 看著1，否則
返回n倍 階乘ñ減1。
這是非常簡單的。
>> 並且為了稍微具有 更清潔和更優雅的代碼，
知道，如果我們有單行循環 或單行條件分支，
我們可以擺脫所有的 他們周圍的花括號。
因此，我們可以鞏固這種此。
這具有完全相同的 功能這一點。
>> 我只是收走了大 牙套，因為只有一行
裡面的那些條件分支。
因此，這些行為相同。
如果n等於1，則返回1。
否則返回n次 Ñ​​減去1的階乘。
因此，我們正在做的問題較小。
如果n開出5，我們要 返回的4 5倍的階乘。
我們會在一分鐘內看到，當我們談論 關於另一個視頻通話stack--
我們談論了哪裡 致電stack--我們將學習
關於到底為什麼這個過程的工作。
>> 但5階乘時說： 返回階乘的5倍4，和4
會說，好了，好了，回報 4倍3的階乘。
正如你所看到的，我們是 那種接近1。
我們越來越近 接近這一基本情況。
>> 一旦我們打的基本情況， 以前的所有功能
有他們在尋找答案。
2階乘是說回歸 2倍的1的階乘。
那麼，1返回1階乘。
因此呼籲階乘 2可以返回2次1，
並給出了回階乘 3，這是等待該結果。
>> 然後它可以計算 其結果，3次2是6，
並給它回到4的階乘。
再次，我們有一個 視頻的調用堆棧
其中這被示出一個小 不是我在說什麼，現在更多。
但是，這是它。
這僅僅是解決 計算一個數的階乘。
>> 它只有四行代碼。
這很酷，不是嗎？
這是一種性感。
>> 如此一般，但不 總是，遞歸函數
可以替代在一個循環 非遞歸函數。
所以在這裡，並排，是迭代 版本階乘功能。
這兩種計算 同樣的事情。
>> 他們都計算n的階乘。
版本在左邊 使用遞歸來做到這一點。
該版本在右側 使用迭代來做到這一點。
>> 而通知，我們要聲明 一個變量的整數產品。
然後我們循環。
只要n是大於0，我們 保持該產品用n乘以
和遞減ñ直到 我們計算該產品。
所以這兩個函數，再次， 做同樣的事情。
但他們不這樣做的 方式完全相同。
>> 現在，有可能 有一個以上的基
情況下或多於一個的 遞歸情況下，根據
在你的函數試圖做的。
您不必僅僅局限於 單個基案或單個遞歸
案例。
的東西這麼一個例子 有多個基例
可能是this--的 斐波那契數列。
>> 您可能還記得 小學生時代
該斐波那契序列定義 像this--的第一個元素是0。
第二個要素是1。
這兩項都只是定義。
>> 然後每隔一個元素被定義 當n減去1和n減去2的總和。
因此第三元件 將0加1是1。
然後將第四元件 將第二個元素，1，
加所述第三元件，1。
這將是2。
等等等等。
>> 所以在這種情況下，我們有兩個基例。
如果n等於1，則返回0。
如果n等於2，則返回1。
否則，正的回報斐波那契 減1加N減2的斐波那契數。
>> 所以這是多個基地的情況。
那麼多個遞歸情況？
那麼，有什麼東西 叫考拉茲猜想。
我不會說， 你知道那是什麼，
因為它實際上是我們最後的 問題對於該特定視頻。
而這是我們的運動 一起工作的。
>> 因此，這裡的什麼 在Collat​​z猜想is--
它適用於每一個正整數。
它推測，它的 總是可能得到回
1，如果你遵循這些步驟。
如果n為1，停止。
我們得回到1，如果n為1。
>> 否則，通過這個 過程中再次n個除以2。
看看你能回到1。
否則，如果n是奇數，經過 這個過程再次3N加1，
或3 n次加1。
所以在這裡，我們有一個基本情況。
如果n等於1，停止。
我們沒有做任何更多的遞歸。
>> 但是，我們有兩個遞歸的情況下。
如果n為偶數，我們做一遞歸 情況下，調用n乘2分。
如果n是奇數，我們做了不同的 遞歸的情況下，3 n次加1。
>> 這樣一來，目標這個視頻 花一秒鐘，暫停視頻，
並嘗試寫 遞歸函數在Collat​​z
你傳遞一個值n，其中和 它計算多少步它
才能到達1，如果你從n個開始 你遵循這些台階之上。
如果n是1，它採取0的步驟。
否則，它會 走一步加然而，
它需要在任N多的步驟 除以2，如果n是偶數，或3n的加1
如果n是奇數。
>> 現在，我已經把在屏幕上點擊這裡 一對夫婦測試你的東西，
你一對夫婦的測試用例，看 什麼這些不同在Collat​​z號碼，
而且插圖 的步驟
需要通過這樣你就可以走了 那種看到這個過程在行動。
因此，如果n是等於 1，N的在Collat​​z為0。
你不必做 什麼要回1。
你已經在那裡了。
>> 如果n是2，它需要 一個步驟去1。
你開始2。
井，2是不等於1。
因此，這將是一步到位 加上然而，許多步驟是
需要n個除以2。
>> 2除以2為1。
因此，需要一步加然而， 許多步驟需要1。
1採取零步驟。
>> 3，你可以看到，有 相當多的步驟，參與。
你從3。
然後你去 10，5，16，8,4，2，1。
這需要七個步驟要回1。
正如你所看到的，有一個 其他幾個測試用例在這裡
來測試你的程序。
如此反复，暫停視頻。
我會去跳回到我們 什麼樣的實際過程是在這裡，
這是什麼猜想。
>> 看看你能不能找出 如何界定的n在Collat​​z
因此，它計算多少 步驟才能到達1。
所以希望，你已經暫停視頻 你不只是在等我
給你答案在這裡。
但如果你是，那麼， 這裡的答案呢。
>> 所以這裡有一個可能的定義 的在Collat​​z功能。
如果n是我們的基礎case-- 等於1，我們返回0。
它沒有採取任何 步驟要回1。
>> 否則，我們有兩個遞歸cases-- 一個用於偶數，一個用於奇。
我測試連號的方式 是檢查是否N模2等於0。
這基本上是，再次， 問這個問題，
如果你還記得什麼國防部is--如果我 除以n乘2有沒有餘數？
這將是一個偶數。
>> 所以，如果n模2等於0 測試是這樣一個偶數。
如果是的話，我想回到1， 因為這絕對是
走一步加在Collat​​z 不管數字是我的一半。
否則，我想返回1 在Collat​​z加3 n次加1。
這是其他 遞歸步驟我們
可以採取的計算 Collat​​z--的步數
它需要找回 到1給出一個數字。
所以希望，這個例子 給你一點點
的遞歸過程的味道。
我們希望，你覺得代碼是 小實施更漂亮，如果
在一個優雅的，遞歸的方式。
但即使沒有，遞歸是一種 真正強大的工具，不過。
所以這是絕對的東西 圍繞讓你的頭，
因為你能夠創建 使用遞歸很酷方案
否則可能是複雜的寫 如果您使用的是循環和迭代。
我是道格·勞埃德。
這是CS50。