[音樂播放] 

道格·勞埃德：你可能認為， 代碼只是用來完成任務。 你寫出來。 它做一些事情。 這幾乎是它。 

你編譯它。 運行該程序。 你是好去。 

但是，不管你信不信，如果 你的代碼很長一段時間， 你居然不妨來看看 代碼東西是美麗的。 它解決了在一個問題 一個非常有趣的方式， 或有只是一些真正 整齊的有關它的樣子。 你可能會笑 我，但這是事實。 和遞歸是一種方式 排序得到這個想法 美麗的，優雅的外觀的代碼。 它解決的方式的問題， 很有意思，很容易想像， 而令人驚訝的短。 

該方法遞歸作品 是，遞歸函數 被定義為一個函數調用 本身作為其執行的一部分。 這似乎有些奇怪， 我們會看到一點點 關於如何工作的時刻。 但同樣，這些 遞歸程序 會是如此優雅 因為他們會 解決這個問題，而無需 擁有所有這些功能 還是這些長循環。 你會看到，這些遞歸 程序要看看這麼短。 他們真的會做 你的代碼看起來很多更漂亮。 

我給你舉個例子 這怎麼看 遞歸過程可能被定義。 所以，如果你熟悉這個 從數學課很多年前， 有被稱為東西 階乘功能，這通常是 表示為一個感嘆號，這 是指對所有的正整數。 和的方式使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。