遞回函式

什么是遞回函式

如果一個函式，可以自己呼叫自己，那么這個函式就是一個遞回函式，

遞回，遞就是去，歸就是回，遞回就是一去一回的程序，

遞回函式的條件

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

定義一個簡單的遞回函式

# 定義一個函式
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

標籤：其他

上一篇：OptaPlanner實用技術 - 批量規劃和實時規劃(1)

下一篇：OutOfMemoryError例外