遞歸函數

什麼是遞歸函數

如果一個函數，可以自己調用自己，那麼這個函數就是一個遞歸函數。

遞歸，遞就是去，歸就是回，遞歸就是一去一回的過程。

遞歸函數的條件

一般來說，遞歸需要邊界條件，整個遞歸的結構中要有遞歸前進段和遞歸返回段。當邊界條件不滿足，遞歸前進，反之遞歸返回。就是說遞歸函數一定需要有邊界條件來控制遞歸函數的前進和返回。

定義一個簡單的遞歸函數

# 定義一個函數
def recursion(num):
	
    print(num)
	if num == 0:
		return 'ok'
	
    # 這個函數在自己的作用域中調用自己，這個函數就是一個遞歸函數
	recursion(num-1)


recursion(10)
"""
結果：
10
9
8
7
6
5
4
3
2
1
0
"""

代碼解析

我們執行這個函數，參數給了一個10，但是這個函數執行的過程中，又調用了自己，所以現在這個函數就會進入先執行第二次調用自己的過程中，第一次的調用就暫時的阻斷了；

第二次調用的時候，num-1，參數就變成了9，繼續執行，然後就又執行到了調用自己的代碼中，現在就會執行第三次調用的過程中，第二次的調用也阻斷了；

這就是 遞 的過程；

…………

第十一次調用的時候，num-1，層層的嵌套，參數就變成了0，就符合了作用域中的if num == 0的條件判斷式，第十一次的調用就沒有再執行到了調用自己的代碼，而是徹徹底底的執行完成了 ，然後代碼的執行就又回到了第十次的函數調用中。

第十次的函數調用阻斷的時候是執行到了recursion(num-1)，但是這一行代碼執行完了，也就是第十一次調用執行完了，並且後面也沒有任何代碼，所以第十次調用也結束了，然後就回到了第九次調用；然後第八次；再就是第七次，一直到第一次結束，整個函數的執行就結束了；

這就是 歸 的過程。

記憶體棧區堆區

棧區空間就是我們常說的棧，棧是一個有去有回，先進後出後出的空間，就像我們上面的例子中講的，我們最先執行的是函數的第一次調用，但是第一次調用卻是最後執行釋放掉的，而第十一次調用是最後調用，最先執行釋放掉的，這就是先進後出。與棧空間概念相違背的是隊列空間，隊列空間是一個有去有回，先進先出的空間，就像我們平時排隊一樣，先排隊的會比後來的人先買到票，之後我們學習併發的時候，我們會詳細的講述隊列的概念。

單獨的講棧堆就是一種數據結構，棧是先進後出的一種數據結構，堆是排序後的一種樹狀數據結構。

棧區堆區是記憶體空間，棧區就是按照先進後出的數據結構，無論創建或銷毀都是自動為數據分配記憶體，釋放記憶體，這是系統自動創建的；堆區就是按照排序後的樹狀數據結構，可優先取出必要的數據，無論創建或者銷毀都是手動分配記憶體，釋放記憶體，這是編程工作者手動編程出來的。

運行程式時在記憶體中執行，會因為數據類型的不同而在記憶體的不同區域運行，因不同語言對記憶體劃分的機制不一，當大體來說，有如下四大區域：

1. 棧區：分配局部變數空間；
2. 堆區：是用於手動分配程式員申請的記憶體空間；
3. 靜態區：又稱之為全局棧區，分配靜態變數，全局變數空間；
4. 代碼區：又稱之為只讀區、常量區，分配常量和程式代碼空間；

上面的棧區、讀取、靜態區、代碼區都只是記憶體中的一段空間。

死遞歸

所以我們在使用遞歸函數的時候要註意，遞歸函數調用的過程就是一個開闢棧和釋放棧的過程，調用的時候開闢棧空間，結束的時候釋放棧空間，所以說，如果開闢的空間不結束就會一直存在，就會一直占用記憶體空間，但是棧空間是一個先進後出的空間，如果新開啟的空間不釋放掉，之前的空間也不會釋放掉的，那麼如果我們開闢的空間很多很多，但是又釋放不掉，那麼我們弱小的記憶體是否有足夠的空間容納得下這麼多的棧呢？如果容納不下，那麼我們的電腦就會爆炸，所以我們在使用遞歸的時候要註意避免這種情況。尤其是死遞歸。

每次調用函數時，在記憶體宗都會單獨開闢一個空間，配合函數運行，這個空間叫做棧幀空間。

1、遞歸是一去一回的過程，調用函數時，會開闢棧幀空間，函數執行結束之後，會釋放棧幀空間，遞歸實際上就是不停地開闢和釋放棧幀空間的過程，每次開闢棧幀空間，都是獨立的一份，其中的資源不共用。

2、觸發回的過程當最後一層棧幀空間全部執行結束的時候，會觸底反彈，回到上一層空間的調用處，遇到return，會觸底反彈，回到上一層的調用處

3、寫遞歸時，必須給予遞歸跳出的條件，否則會發生記憶體溢出，可能會出現死機的情況，所以當遞歸的層數過多的時候，不建議使用遞歸。

Python中的環境遞歸的層數預設為1000層左右，一般都是996層。

# 下麵的遞歸函數沒有跳出遞歸的條件，所以是一個死遞歸，執行看，是不是1000左右。
def recursion(num):
	print(num)
	recursion(num+1)

recursion(1)

尾遞歸

簡單的來說，在函數返回的時候，調用其本身，並且return語句不包含表達式，這樣的一個遞歸函數就是一個尾遞歸函數。

換句話說返回的東西就是函數本身就是尾遞歸函數，而遞歸函數只是自身調用了自身而已。

一般情況下，尾遞歸的計算在參數中完成。

我們開始的舉例是一個尾遞歸函數嗎？不是，因為那個例子這是調用了自己本省，但是並沒有返回，所以還是一個普通的遞歸函數而已。

使用遞歸的時候，我們通常在一些技術博客上看到一些關於尾遞歸優化的東西，這是因為尾遞歸無論調用多少次函數，都只會占用一份空間，只開闢一個棧幀空間，但是目前 cpython 不支持，然而最常見的解釋器就是 cpython 。

Python常見的解釋器：cpython、pypy、jpython。

尾遞歸相比普通遞歸的優點就是返回值不需要額外過多的運算。

實例

階乘計算

一個正整數的階乘是所有小於及等於該數的正整數的積，並且0的階乘為1。

""" 迴圈計算 """
def factorial(num):
   if num == 0:
      return 1
   elif num < -1:
      return '只能是零和正整數'
   count = 1
   for i in range(1, num+1):
      count *= i
   return count

res = factorial(5)
print(res)  # 120


""" 使用普通遞歸 """
def factorial(num):
   if num == 0:
      return 1
   elif num < -1:
      return '只能是零和正整數'
   elif num == 1:
      return num
   return num * factorial(num-1)   # 普通函數返回的是一個表達式

res = factorial(5)
print(res)  # 120


""" 使用尾遞歸 """
def factorial(num, count=1):
   if num == 0:
      return 1
   elif num < -1:
      return '只能是零和正整數'
   elif num == 1:
      return count
   return factorial(num-1, count*num)   # 尾遞歸返回的是一個函數，計算式在參數中運算

res = factorial(5)
print(res)  # 120

斐波那契數列

斐波那契數列是以0、1兩個數開頭，從這個數列從第3個數開始，每一個數都等於前兩樹之和。

# 使用迴圈解決
def fibonacci(num):
   x, y = 0, 1

   if num < 1:
      return '輸入大於0的數字'
   elif num == 1:
      return 0
   elif num == 2:
      return 1

   for _ in range(num-2):
      x, y = y, y+x
   return y

res = fibonacci(9)
print(res)  # 21


""" 使用普通遞歸 """
def fibonacci(num):
   if num < 1:
      return '輸入大於0的數字'
   elif num == 1:
      return 0
   elif num == 2:
      return 1

   return fibonacci(num-1) + fibonacci(num-2)

res = fibonacci(9)
print(res)  # 21


""" 使用尾遞歸 """
def fibonacci(num, x=0, y=1):
   if num < 1:
      return '輸入大於0的數字'
   elif num == 1:
      return x
   elif num == 2:
      return y

   return fibonacci(num-1, x=y,  y=(x+y))

res = fibonacci(9)
print(res)  # 21