3 遞歸

3.1 遞歸<函數(shù)>

// MARK: 3.1 遞歸
/*
 階乘
 */
func factorial(_ parameter: Int) -> Int {
    // 基線條件
    guard parameter > 1 else {
        print("Base Case \(parameter)")
        return parameter
    }
    print(parameter)
    // 遞歸條件
   return parameter * factorial(parameter - 1)
}

print("Final result is : \(factorial(3))")

3.2 基線條件和遞歸條件

// MARK: - 3.2 基線條件和遞歸條件
// FIXME: 1. 遞歸條件是指函數(shù)調(diào)用自己.
// FIXME: 2. 基線條件則是指函數(shù)不再調(diào)用自己, 從而避免形成無限循環(huán).

// MARK: - 3.3.1 棧<調(diào)用棧>
// FIXME: 棧: 是一種簡單的數(shù)據(jù)結(jié)構(gòu).
// FIXME: e.g.
func greet(_ name: String) -> Void {
    // 2. 為hello函數(shù)分配內(nèi)存并壓入棧
    hello(name)
    // 3. hello執(zhí)行完成, 將hello函數(shù)從棧中彈出, 并釋放內(nèi)存
    // 4. 為bye函數(shù)分配內(nèi)存并壓入棧
    bye(name)
    // 5. bye函數(shù)執(zhí)行完成, 將hello函數(shù)從棧中彈出(移除), 并釋放內(nèi)存
}

private func hello(_ name: String) {
    print("Hello \(name)!")
}

private func bye(_ name: String) {
    print("bye, \(name)~")
}

// 1. 此時(shí)為greet函數(shù)分配內(nèi)存并壓入調(diào)用棧, 并加參數(shù)'Jim"存儲(chǔ)到內(nèi)存中
greet("Jim")
// 6. greet函數(shù)執(zhí)行完成, 將其從棧中彈出, 并釋放

3.3 遞歸調(diào)用棧

// MARK: - 3.3.2 遞歸調(diào)用棧
// TODO: 本小節(jié), 拿3.1中的 factorial 函數(shù)說明
// FIXME: 1. 當(dāng)調(diào)用  factorial(3)時(shí), 此時(shí)的函數(shù)調(diào)用棧

/*
 內(nèi)部執(zhí)行順序如下:
 factorial(3)
 3 * factorial(2)
 3 * (2 * factorial(1))
 3 * (2 * 1)
 3 * 2
 6
 
 // FIXME: 上述過程的長度可以看做是內(nèi)存的峰值曲線.
 
 解釋: 調(diào)用3時(shí), 3內(nèi)調(diào)用2, 3等待2完成; 2內(nèi)調(diào)用1, 2等待1完成; 1內(nèi)調(diào)用0,    1等待0完成. 當(dāng)調(diào)用到0時(shí), 0滿足了基線條件, 此時(shí) factorial(0)執(zhí)行完成, 從棧中彈出, 并釋放內(nèi)存; 接著 factorial(1)的執(zhí)行完成, 從棧中彈出并釋放內(nèi)存; 接著依次類推到棧底 factorial(3)的執(zhí)行完成, 從棧中彈出并釋放內(nèi)存.
 */

// FIXME: PS: 當(dāng)使用遞歸時(shí), 每一次遞歸都棧都需要分配內(nèi)存, 如果調(diào)用棧過長或無限循環(huán),  將占用大量的內(nèi)存或內(nèi)存不夠的情況.

// TODO: 如果遇到上述情景, 你有兩種選擇. 1) 重寫代碼, 轉(zhuǎn)而使用循環(huán). 2) 使用尾遞歸<這是一個(gè)高級(jí)遞歸, 內(nèi)存的使用是恒量的, 但是部分語言不支持尾遞歸優(yōu)化, C 可以.>.