在講解遞回函式之前我們先了解一下堆疊堆
單獨講堆疊堆是資料結構
- 堆疊：后進先出的一種資料結構
- 堆：排序后的一種樹狀資料結構
堆疊區堆區是記憶體空間
- 堆疊區：按照后進先出的資料結構(堆疊)，無論創建或銷毀都是自動為資料分配記憶體，釋放記憶體(系統自動做的)
- 堆區：按照排序后的樹狀資料結構(堆)，可優先取出必要資料，無論創建或銷毀都是手動分配記憶體，釋放記憶體(程式員手動做的)
- 記憶體中的堆疊區： 自動分配 自動釋放
- 記憶體中的堆區： 手動分配 手動釋放
運行程式時在記憶體中執行，會因為資料型別的不同而在記憶體的不同區域運行，因不同語言對記憶體劃分的機制不一，但大體來講，有如下四大區域：
- 堆疊區：分配區域變數空間，
- 堆區：是用于手動分配程式員申請的記憶體空間，
- 靜態區(全域堆疊區)：分配靜態變數，全域變數空間，
- 代碼區(只讀區，常量區)：分配常量和程式代碼空間的，
堆疊區 堆區 靜態區 代碼區 都是記憶體中的一段空間
遞回函式
在函式內部，可以呼叫其他函式，如果一個函式在內部呼叫自身本身，這個函式就是遞回函式，
舉個例子，我們來計算階乘n! = 1 x 2 x 3 x ... x n，用函式func(n)表示，可以看出：
func(n)=n!=1×2×3×???×(n?1)×n=(n?1)!×n=func(n?1)×n
所以，func(n)可以表示為n x func(n-1)，只有n=1時需要特殊處理，
于是，func(n)用遞回的方式寫出來就是：
def func(n):
if n==1:
return 1
return n * func(n - 1)
上面就是一個遞回函式，可以試試：
print(func(1))
# 1
print(func(5))
# 120
print(func(100))
# 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
如果我們計算func(5)，可以根據函式定義看到計算程序如下：
遞回函式的優點是定義簡單，邏輯清晰，理論上，所有的遞回函式都可以寫成回圈的方式，但回圈的邏輯不如遞回清晰，
使用遞回函式需要注意防止堆疊溢位，在計算機中，函式呼叫是通過堆疊（stack）這種資料結構實作的，每當進入一個函式呼叫，堆疊就會加一層堆疊幀，每當函式回傳，堆疊就會減一層堆疊幀，由于堆疊的大小不是無限的，所以，遞回呼叫的次數過多，會導致堆疊溢位，可以試試func(1000)：
print(func(1000))
'''
Traceback (most recent call last):
File "D:/python_project/mxxl/test/test.py", line 7, in <module>
print(func(1000))
File "D:/python_project/mxxl/test/test.py", line 4, in func
return n * func(n - 1)
File "D:/python_project/mxxl/test/test.py", line 4, in func
return n * func(n - 1)
File "D:/python_project/mxxl/test/test.py", line 4, in func
return n * func(n - 1)
[Previous line repeated 995 more times]
File "D:/python_project/mxxl/test/test.py", line 2, in func
if n==1:
RecursionError: maximum recursion depth exceeded in comparison
'''
解決遞回呼叫堆疊溢位的方法是通過尾遞回優化，
尾遞回
事實上尾遞回和回圈的效果是一樣的，所以，把回圈看成是一種特殊的尾遞回函式也是可以的，
尾遞回是指，在函式回傳的時候，呼叫自身本身，并且，return陳述句不能包含運算式，
這樣，編譯器或者解釋器就可以把尾遞回做優化，使遞回本身無論呼叫多少次，都只占用一個堆疊幀，不會出現堆疊溢位的情況，
上面的func(n)函式由于return n * func(n - 1)引入了乘法運算式，所以就不是尾遞回了，要改成尾遞回方式，需要多一點代碼，主要是要把每一步的乘積傳入到遞回函式中：
def func(n):
return func_iter(n, 1)
def func_iter(num, product):
if num == 1:
return product
return func_iter(num - 1, num * product)
可以看到，return func_iter(num - 1, num * product)僅回傳遞回函式本身，num - 1和num * product在函式呼叫前就會被計算，不影響函式呼叫，
func(5)對應的func_iter(5, 1)的呼叫如下：
尾遞回呼叫時，如果做了優化，堆疊不會增長，因此，無論多少次呼叫也不會導致堆疊溢位，
遺憾的是，大多數編程語言沒有針對尾遞回做優化，Python解釋器也沒有做優化，所以，即使把上面的func(n)函式改成尾遞回方式，也會導致堆疊溢位，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/276567.html
標籤：其他