猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将第一 天剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半后又多吃一个。到第 10天早上想再吃时，发现只剩下一个桃子了。

猴子吃桃

问题描述

猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将第一 天剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半后又多吃一个。到第 10天早上想再吃时，发现只剩下一个桃子了。

求猴子第一天共摘了多少个桃子。

设计思路

第1天的桃子数是第2天的桃子数加1后的2倍，第2天的桃子数是第3天的桃子数加1后的2 倍，……，一般地，第k天的桃子数是第k+1天的桃子数加1后的2倍。 设第k天的桃子数是t(k)，则有递推关系t(k) = (t(k + 1) + 1) * 2，且初始条件为：t(10) = 1。

根据递推关系和初始条件，t(10) → t(9) → t(8) → t(7) → t(6) → t(5) → t(4) → t(3) → t(2) → t(1)。

上面的递推关系可看做在一个函数体的内部又调用了该函数。上面的初始条件可看做递归结束条件（递归出口）。

Swift 3.0 代码实现

猴子吃桃（思路一：递推）

func eatPeaches1 () -> Int {
    var t = [Int](repeating: 0, count: 11)
    t[10] = 1
    
    var k = 9
    while k >= 1 {
        t[k] = (t[k + 1] + 1) * 2
        k -= 1
    }
    
    return t[1]
}

eatPeaches1()

猴子吃桃（思路二：递归）

func eatPeaches2 (day: Int) -> Int {
    if day == 10 {
        return 1
    } else {
        return (eatPeaches2(day: day + 1) + 1) * 2
    }
}

eatPeaches2(day: 1)

算法理解

递推：已知第10天桃子数为1，且容易得到接连两天的桃子数满足的表达式：后一天桃子数加1再乘以2为前一天的桃子数。所以，可以由第10天的推出第9天的桃子数，第9天的推出第8天的桃子数。依此类推，一直到第1天的桃子数。得出解。

var k = 9
while k >= 1 {
    t[k] = (t[k + 1] + 1) * 2
    k -= 1
}

第1次循环：第9天的桃子数=第10天的桃子数（已知为1）加1 再乘以2。利用数组下标，把第9天的桃子数存入数组。

第2次循环：k在第1次循环减了1变为8，得 第8天的桃子数=第9天的桃子数（由第1次循环求出并存入了数组）加1 再乘以2

最终，由后往前，推出第1天的桃子数。

递归：调用 eatPeaches2(day: 1) ，进入程序后，先走else分支，第2天桃子数为：(eatPeaches2(day: 2) + 1) * 2。第2天桃子数为：(eatPeaches2(day: 3) + 1) * 2。

设，该表达式为 第k天桃子数F(k) = (F(k+1)+1) * 2 。

递归总结：由 第1天桃子数=第2天桃子数加1再乘以2，不断调用函数本身，用后一天的桃子数表达式来计算前一天的桃子数（不断把当前天替换为后一天的表达，直到替换到“出口”第10天，得到一步一步的算式），最后，到达递归出口的第10天，带入第10天的值，根据得出的最后的式子计算出第1天的桃子数。

递归的关键：不断调用本身，用函数表达式替换未知量，每次替换，都新加入一次计算，直到替换到“递归出口”的已知量，此时，得到了一步一步替换后得的算式，再一口气计算出来。简言之，就是不断替换未知量，直到所有量已知。

递归的延伸

递归的概念：如果在一个函数的函数体内部又调用了该函数，那么该函数就是递归函数。递归函数包含了一种隐式的循环，因此，递归函数必须有一个明确的递归结束条件（递归出口）。

计算n的阶乘（非递归函数）

func calcuFact_NonRecur(n: Int) -> Int? {
    if n < 0 {
        return nil
    } else if n == 0 {
        return 1
    } else {
        var result = 1
        for index in 1...n {
            result *= index
        }
        return result
    }
}
calcuFact_NonRecur(n: -3)
calcuFact_NonRecur(n: 0)
calcuFact_NonRecur(n: 5)

计算n的阶乘（递归函数）

func calcuFact_Recur(n: Int) -> Int? {
    if n < 0 {
        return nil
    } else if n == 0 || n == 1 {
        return 1
    } else {
        return n * calcuFact_Recur(n: n - 1)!
    }
}
calcuFact_Recur(n: -3)
calcuFact_Recur(n: 0)
calcuFact_Recur(n: 1)
/*
5! = 5 * 4! = 5 * 4 * 3! = 5 * 4 * 3 * 2! = 5 * 4 * 3 * 2 * 1! = 5 * 4 * 3 * 2 * 1 = 120
 */
calcuFact_Recur(n: 5)

斐波那契（Fibonacci）数列：

F0 = 0，F1 = 1，Fn = F(n - 1) + F(n - 2) (n >= 2, n属于正整数)

func calcuFibonacci(n: Int) -> Int? {
    if n < 0 {
        return nil
    } else if n == 0 {
        return 0
    } else if n == 1 {
        return 1
    } else {
        return calcuFibonacci(n: n - 1)! + calcuFibonacci(n: n - 2)!
    }
}

calcuFibonacci(n: -3)
calcuFibonacci(n: 0)
calcuFibonacci(n: 1)
/*
F6 = F5 + F4 = F4 + F3 + F3 + F2 = F3 + F2 + F2 + F1 + F2 + F1 + F1 + F0 = F2 + F2 + F1 + F0 + F1 + F0 + F1 + F1 + F0 + F1 + F1 + F0 = F1 + F0 + F1 + F0 + F1 + F0 + F1 + F0 + F1 + F1 + F0 + F1 + F1 + F0 = 1 + 0 + 1 + 0 + 1 + 0 + 1 + 0 + 1 + 1 + 0 + 1 + 1 + 0 = 8
 */
calcuFibonacci(n: 6)