Python函數編程——遞歸

求100不斷除以2直到商為0為止，打印每次除的商

用循環實現：

          
            n = 100
while n > 0:
    n = int(n/2)
    print(n)
          
        

輸出：

          
            50
25
12
6
3
1
0
          
        

如果用函數，如何實現呢？

          
            def calc(n):
    n = int(n/2)
    print(n)
    if n > 0:
        calc(n)    # 調用自己
calc(100)
          
        

在函數內部，可以調用其他函數。如果一個函數在內部調用自已本身，這個函數就叫做遞歸函數。上面我們寫的這個代碼就是遞歸。

遞歸的執行過程

          
            def calc(n):
    n = int(n/2)
    print(n)
    if n > 0:
         calc(n)
    print(n) 
calc(10)
          
        

輸出：

          
            5

2

1

0

0

1

2

5
          
        

為什么輸出結果會是這樣？

如上圖所示，函數在每進入下一層的時候，當前層的函數并未結束，它必須等它調用的下一層函數執行結束返回后才能繼續往下走。 所以最下面的那句print(n)會等最里層的函數執行時才會執行，然后不斷往外退層，所以會出現0、1、2、5的效果。

遞歸特性：

1、必須有一個明確的結束條件。

2、每次進入更深一層遞歸時，問題規模相比上次遞歸都應有所減少。

3、遞歸效率不高，遞歸層次過多會導致棧溢出（在計算機中，函數調用是通過棧（stack）這種數據結構實現的，每當進入一個函數調用，棧就會加一層棧幀，每當函數返回，棧就會減一層棧幀。由于棧的大小不是無限的，所以，遞歸調用的次數過多，會導致棧溢出）。

遞歸在特定場景下還是挺有用的，以后學的一些算法就得用到遞歸，比如堆排、快排等。