ZAMYLA：為了了解 遞歸，你必須 先了解遞歸。 在程序設計方法有遞歸 你有自我指涉 的定義。 遞歸數據結構，例如， 是數據結構 包括自己 它們的定義。 但是今天，我們要集中 在遞歸函數。 

回想一下，函數需要的投入， 參數，並返回一個值作為其 表示為輸出 此圖在這裡。 我們想想盒子作為身體 的功能，包含該組 該解釋的說明 輸入和提供輸出。 以身體內部一探究竟 該功能可以顯示來電 其它功能。 就拿這個簡單的函數foo，即 採用單個字符串作為輸入，並 打印多少個字母 該字符串了。 該函數strlen函數，字符串長度， 被調用時，它的輸出是 所需調用的printf。 

現在，是什麼讓一個遞歸函數 特別的是，它調用自身。 我們可以代表這個遞歸 這個橙色箭頭打電話 循環返回到自身。 但是，只有再次執行本身會 再拍遞歸調用，並 其它一個又一個。 但是遞歸函數 不可能是無限的。 他們必須以某種方式結束，或者你 程序將一直運行下去。 

因此，我們需要找到一種方法來打破 出了遞歸調用的。 我們稱之為基本情況。 當滿足基本情況的條件， 該函數返回而不進行 另一個遞歸調用。 藉此功能，喜，一個void函數 接受一個int n作為輸入。 基本情況是第一位的。 如果n小於零，打印和再見 返回對於所有其他情況下， 功能將打印喜和執行 遞歸調用。 另一個函數調用喜 一個遞減的輸入值。 

現在，即使我們打印嗨， 函數將不會終止，直到我們 返回它的返回類型， 在這種情況下無效。 因此，對每一個n比基本情況外， 這個函數喜將返回喜 的n減1。 由於該功能是無效的，雖然，我們 這裡將沒有明確的返回類型。 我們只需要執行該函數。 因此調用喜（3）將打印和喜 執行喜（2）執行喜（1）1 它執行喜（0），其中所述 基本情況的條件得到滿足。 因此喜（0）打印再見和回報。 

確定。 所以，現在我們了解的基本知識 遞歸函數，它們需要 至少一種鹼的情況下，以及一個 遞歸調用，讓我們進入到一個 更有意義的例子。 一個不只是返回 無效不管。 

讓我們來看看階乘 最常用於操作 概率計算。 的n的階乘是每一個的產品 比正整數 和等於n。 所以階乘五是5倍，4倍 3次2次1，得到120。 四階乘是4倍3倍 2次1給24。 而同樣的規則也適用 到任何正整數。 

那麼我們如何可以寫一個遞歸 函數，計算階乘 一個數字？ 好了，我們就需要確定雙方的 基本情況和遞歸調用。 遞歸調用是相同的 對於除基地所有情況 情況下，這意味著我們將不得不 找到一個模式，這將賦予我們 期望的結果。 

對於這個例子，看看如何5的階乘 涉及乘以4×3×2×1 而這非常相同的乘法 這裡被發現，該 定義4的階乘。 所以我們看到，5的階乘是 僅5倍4的階乘。 現在沒有這種模式適用 到4的階乘呢？ 是。 我們看到，4的階乘包含 乘法3次2次1，則 同樣的定義為3的階乘。 所以4因子等於4倍3 階乘，等等等等我們 圖案堅持，直到1階乘，這 通過定義等於1。 

有沒有其他積極 整數離開了。 所以，我們有圖案 我們的遞歸調用。 的n的階乘等於n倍 n的階乘減去1。 而我們的基本情況？ 這將只是我們的定義 1階乘。 

所以，現在我們可以繼續寫作 為函數的代碼。 對於基本情況，我們將有 條件n等於等於1，其中 我們將返回1。 然後移動到遞歸調用， 我們將返回n倍 n個階乘減1。 

現在讓我們來測試這個我們。 讓我們嘗試階乘4。 根據我們的功能是相等的 到4倍階乘（3）。 階乘（3）等於 3次階乘（2）。 階乘（2）等於2倍 階乘（1），它返回1。 階乘（2）現在返回2次1，2。 階乘（3）現在可以返回 3次2，6。 最後，階乘（4） 返回4次6，24。 

如果你遇到任何困難 用遞歸調用，假裝 該功能的工作原理了。 我的意思是，你應該 相信你的遞歸調用返回 正確的價值觀。 舉例來說，如果我知道， 階乘（5）等於5倍 階乘（4），我要相信 階乘（4）會給我24。 把它看成是一個變量，如果你 會，因為如果你已經定義 階乘（4）。 因此，對於任何階乘（n）時，它的 n的產物和 以前的階乘。 而這之前的階乘 通過調用獲得 n個階乘減1。 

現在，看看你是否可以實現 遞歸函數自己。 加載你的終端，或run.cs50.net， 寫一個函數sum 接受一個整數n，並返回 所有連續的正和 整數n到1。 我已經寫了一些款項 值，以幫助您我們。 首先，弄清楚 基本情況的條件。 然後，看總和（5）。 你可以在條件表達出來 另一個總和？ 現在，大約總和（4）？ 你怎麼能表達總和（4） 在另一個總和條款？ 

一旦你有了總和（5）和金額（4） 以其他款項的條款，請參閱 如果你能找出一個 圖案總和（N）。 如果沒有，請嘗試其他一些數字 並表達他們的款項 條款的另一個號碼。 通過識別模式的離散 數字，你對你的方式來 識別模式對任意n。 

遞歸是一個非常強大的工具， 所以當然它不是局限於 數學函數。 遞歸可以非常有效地使用 當樹木，例如處理。 檢查出的樹木短的 更徹底的審查，但現在 記得，二叉搜索樹，在 特別地，由節點時，每個 一個值，兩個節點的指針。 通常，這是由表示 有一條線指向父節點 給左子節點和一個 右邊的子節點。 二進制搜索的結構 樹很適合 以遞歸搜索。 遞歸調用或者通過在 左或右節點，但更 那樹短。 

說你要執行一個操作 二叉樹的每一個節點。 你將如何著手呢？ 好吧，你可以寫一個遞歸 函數來執行該操作 父節點上，使遞歸 調用相同的功能， 通過在左側和 右子節點。 例如，這個函數foo，即 改變一個給定的節點的值和 所有的孩子1。 的空節點的原因基本情況 函數返回，表明 有沒有任何節點 留在該子樹。 

讓我們通過它。 首先家長是13。 我們將該值更改為1，然後調用 我們在左邊的功能以及 如權利。 該函數foo，被稱為左 子樹的第一個，因此左節點 將被重新分配給1和foo會 被稱為該節點的子節點， 第一左，然後右側 等等，等等。 並告訴他們，分支機構不具有 任何更多的孩子因此同樣的過程 將繼續為兒童權利 直到整棵樹的節點 重新分配到1。 

正如你所看到的，你不局限於 到只有一個遞歸調用。 正如許多如將完成這項工作。 如果你有一棵樹，每個 節點有三個孩子， 左，中，右？ 你會如何編輯富？ 好了，簡單。 只需添加另一個遞歸調用和 通過在中間節點指針。 

遞歸是非常強大的，而不是 提到優雅，但它可以是一個 難以理解的概念在第一，所以要 耐心，慢慢來。 從基礎案例。 它通常是最容易識別， 然後就可以正常工作 向後從那裡。 你知道你需要達到你的 基本情況，這樣有可能 給你一些提示。 嘗試在表達一種特定的情況下， 其他情況下，還是在子集。 

感謝收看這短暫的。 最起碼，現在你可以 這樣理解的笑話。 我的名字是Zamyla，這是CS50。 

藉此功能，喜，一 空函數，它接受 一個int n作為輸入。 基本情況是第一位的。 如果n小於0時，打印 “再見”和回報。