Python函數(shù)編程——遞歸

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

用循環(huán)實現(xiàn)：

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

輸出：

          
            50
25
12
6
3
1
0
          
        

如果用函數(shù)，如何實現(xiàn)呢？

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

在函數(shù)內(nèi)部，可以調(diào)用其他函數(shù)。如果一個函數(shù)在內(nèi)部調(diào)用自已本身，這個函數(shù)就叫做遞歸函數(shù)。上面我們寫的這個代碼就是遞歸。

遞歸的執(zhí)行過程

          
            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
          
        

為什么輸出結(jié)果會是這樣？

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

遞歸特性：

1、必須有一個明確的結(jié)束條件。

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

3、遞歸效率不高，遞歸層次過多會導(dǎo)致棧溢出（在計算機中，函數(shù)調(diào)用是通過棧（stack）這種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的，每當進入一個函數(shù)調(diào)用，棧就會加一層棧幀，每當函數(shù)返回，棧就會減一層棧幀。由于棧的大小不是無限的，所以，遞歸調(diào)用的次數(shù)過多，會導(dǎo)致棧溢出）。

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