**遞歸函數** 在上一章嵌套函數拆分之后，我們在函數內部調用了外部其他函數。如果一個函數在內部調用自身本身，那么這個函數就被稱為遞歸函數。 遞歸函數定義簡單，邏輯清晰。理論上，所有的遞歸函數都可以改寫成循環結構。 在數學上我們求階乘 ~~~ n! = n * (n-1) * ...*3*2*1 ~~~ 我們用函數 myFact(n) 表示 ~~~ myFact(n) = n! = n * (n-1) * ...*3*2*1 = n * (n-1)! = n * myFact(n-1) ~~~ 我們知道 1! 階乘是 1 ，0! 階乘也是 1，所以當 n = 1 與 0 時，就需要進行特殊處理了 函數如下 ~~~ #!/usr/bin/env python3 # -*- coding:utf-8 -*- def myFact(n): if not isinstance(n,int) : return '%s is error type' % n if n < 0 : return 'parameter is not less than 0' if n < 2 : return 1 return n * myFact(n-1) print(myFact('123')) #第一次調用 print(myFact(-1)) #第二次調用 print(myFact(0)) #第三次調用 print(myFact(5)) #第四次調用 ~~~ 調用結果 ~~~ 123 is error type #第一次調用結果 parameter is not less than 0 #第二次調用結果 1 #第三次調用結果 120 #第四次調用結果 ~~~ 遞歸特性 1. 必須有一個明確的結束條件。 2. 遞歸每深入一層，問題規模相比上次遞歸都應有所減少。 3. 遞歸效率不高，程序中能不用遞歸就不用。 **遞歸函數需要注意防止棧溢出。** 什么叫棧：又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。 棧，我們可以通俗理解為水桶，只能從一端進出水，"先進后出" 原則。 圖片示意  在計算機中，函數調用是通過棧（stack）這種數據結構實現的，在調用一個函數的時候棧就會加一層，在函數返回的時候，棧就會減一層。由于棧的大小不是無限的，所以，如果遞歸調用的次數過多，就會導致棧溢出。 當調用并打印 print(myFact(999))，就出現了棧溢出 ~~~ airvip@airvip:/mnt/e/workspace/pylearn$ ./test.py Traceback (most recent call last): File "./test.py", line 18, in <module> print(myFact(999)) ... File "./test.py", line 12, in myFact return n * myFact(n-1) File "./test.py", line 8, in myFact if n < 0 : RecursionError: maximum recursion depth exceeded in comparison ~~~ 那如何解決因多次調用造成的棧溢出呢？ 我們可以通過 **尾遞歸** 進行優化，實際上尾遞歸和循環的效果是一樣的，所以，把循環看成是一種特殊的尾遞歸函數也是可以的。 尾遞歸：在函數返回的時候，只是調用自己本身，并且 return 語句不能包含表達式。這樣編譯器或者解釋器就可以把尾遞歸做優化，使遞歸本身無論調用多少次，都只占用一個棧幀，不會出現棧溢出的情況。 上面的 myFact(n) 函數由于 return n * myFact(n-1) 引入了乘法表達式，所以就不是尾遞歸了。要改成尾遞歸方式，主要是要把每一步的乘積傳入到遞歸函數中 ~~~ #!/usr/bin/env python3 # -*- coding:utf-8 -*- def fact(n): if not isinstance(n,int) : return '%s is error type' % n if n < 0 : return 'parameter is not less than 0' return fact_iter( n) def fact_iter(count,res=1): if count < 2: return res return fact_iter(count - 1,res * count,) ~~~ 可以看到，return fact_iter(res * count, count - 1) 返回的是遞歸函數本身，每個參數在函數調用前就會被計算，不影響函數調用。 fact(5) 對應的 fact_iter(5, 1) 的調用如下： ~~~ 第一次調用 ： fact_iter(5,1) 第二次調用 ： fact_iter(4,5) 第三次調用 ： fact_iter(3,20) 第四次調用 ： fact_iter(2,60) 第五次調用 ： fact_iter(1,120) 第六次調用 ：120 ~~~ 尾遞歸調用時，如果做了優化，棧不會增長，因此，無論多少次調用也不會導致棧溢出。 遺憾的是，大多數編程語言沒有針對尾遞歸做優化，Python解釋器也沒有做優化，所以，即使把上面的 fact(n) 函數改成尾遞歸方式，也會導致棧溢出。 有一個針對尾遞歸優化的裝飾器 (decorator),大家可以參考下 ~~~ #!/usr/bin/env python2.4 # This program shows off a python decorator( # which implements tail call optimization. It # does this by throwing an exception if it is # it's own grandparent, and catching such # exceptions to recall the stack. import sys class TailRecurseException: def __init__(self, args, kwargs): self.args = args self.kwargs = kwargs def tail_call_optimized(g): """ This function decorates a function with tail call optimization. It does this by throwing an exception if it is it's own grandparent, and catching such exceptions to fake the tail call optimization. This function fails if the decorated function recurses in a non-tail context. """ def func(*args, **kwargs): f = sys._getframe() if f.f_back and f.f_back.f_back \ and f.f_back.f_back.f_code == f.f_code: raise TailRecurseException(args, kwargs) else: while 1: try: return g(*args, **kwargs) except TailRecurseException, e: args = e.args kwargs = e.kwargs func.__doc__ = g.__doc__ return func @tail_call_optimized def factorial(n, acc=1): "calculate a factorial" if n == 0: return acc return factorial(n-1, n*acc) print factorial(10000) # prints a big, big number, # but doesn't hit the recursion limit. @tail_call_optimized def fib(i, current = 0, next = 1): if i == 0: return current else: return fib(i - 1, next, current + next) print fib(10000) # also prints a big number, # but doesn't hit the recursion limit. ~~~