>> 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時，打印 “再見”和回報。