遞迴法 fact(n) = n!

"""
遞迴法
階乘 n! = 1 x 2 x 3 x ... x n
用函數fact(n)表示，可以看出：
fact(1) = 1
fact(n) = n!
           = 1 x 2 x 3 x ... x (n-1) x n
           = (n-1)! x n
           = fact(n-1) x n
於是，fact(n)用遞迴的方式寫出來就是：
"""

def fact(n):
    if n==1:
        print("fact(1)=1")        
        return 1
    print ("fact(",n, ")=", n ,"* fact(",n-1,")")
    return n * fact(n - 1)

print(fact(5))

=========== == RESTART: F:/Python_APSC/b039-1.py ==== =======

fact( 5 )= 5 * fact( 4 )

fact( 4 )= 4 * fact( 3 )

fact( 3 )= 3 * fact( 2 )

fact( 2 )= 2 * fact( 1 )

fact(1)=1

120

>>> 




fact(100000)

  File "F:/Python_APSC/b039-1.py", line 18, in fact
    return n * fact(n - 1)
  File "F:/Python_APSC/b039-1.py", line 18, in fact

    return n * fact(n - 1)

使用遞迴函數需要注意防止棧溢出。在電腦中，函式呼叫是通過棧（stack）這種資料結構實現的，每當進入一個函式呼叫，棧就會加一層棧幀，每當函數返回，棧就會減一層棧幀。由於棧的大小不是無限的，所以，遞迴呼叫的次數過多，會導致棧溢出。可以試試fact(1000)：

1 2 3 4 5 6 7

>>> fact(1000) Traceback (most recent call last):   File "<stdin>", line 1, in <module>   File "<stdin>", line 4, in fact   ...   File "<stdin>", line 4, in fact RuntimeError: maximum recursion depth exceeded

　　

解決遞迴呼叫棧溢出的方法是通過尾遞迴優化

尾遞迴是指，在函數返回的時候，調用自身本身，並且，return語句不能包含運算式。這樣，編譯器或者解譯器就可以把尾遞迴做優化，使遞迴本身無論調用多少次，都只佔用一個棧幀，不會出現棧溢出的情況。

如：

1 def factorial(n, acc=1):

2   "calculate a factorial"

3   if n == 0:

4     return acc

5   return factorial(n-1, n*acc)

函數返回時只調用了它本身 factorial(n-1, n*acc)