## 遞歸 * 函數調用自身 * 遞歸需要邊界條件，遞歸前進段，遞歸返回段 * 凡是可以通過遞歸實現的都可以通過循環實現 ## 示例 ### 階乘 ~~~ def fact(n): return n*fact(n-1) if n > 1 else 1 print fact(10) ~~~ ### 菲波那切數列 [參考][1] ~~~ def fibo(n): """ 根據輸入的數字計算出斐波那契數列的第n個，從0 開始 :return: """ fibo_d[n] = fibo(n-1) + fibo(n-2) if n > 1 else n return fibo_d[n] print fibo(500) ~~~ 升級版，引入緩存 ~~~ def fibo(n, cache): """ 根據輸入的數字計算出斐波那契數列的第n個，從0 開始 :return: """ if cache is None: cache = {} if n in cache: return cache[n] else: fibo_d[n] = fibo(n-1, cache) + fibo(n-2, cache) if n > 1 else n return cache[n] print fibo(500) ~~~ [1]:https://coding.net/u/echohiyang/p/algorithm/git/blob/master/fib.py