## 递归 * 函数调用自身 * 递归需要边界条件，递归前进段，递归返回段 * 凡是可以通过递归实现的都可以通过循环实现 ## 示例 ### 阶乘 ~~~ 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