遞歸概念
遞歸：程序調用自身的編程技巧稱為遞歸（ recursion）。用一種通俗的話來說就是自己調用自己，它通常把一個大型複雜的問題層層轉化為一個與原問題相似的、但是規模較小的問題來求解，當問題小到一定規模的時候，需要一個遞歸出口返回。遞歸策略只需少量的程序就可描述出解題過程所需要的多次重複計算，大大地減少了程序的代碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。
遞歸函數：在程式語言中，函數直接或間接調用函數本身，則該函數稱為遞歸函數；在數學上的定義如下：對於某一函數 f(x)
f(x)，其定義域是集合 A，那麼若對於 A 集合中的某一個值 X0
X
，其函數值 f(x0)
f(x
) 由 f(f(x0))
f(f(x
)) 決定，那麼就稱 f(x)
f(x) 為遞歸函數。
遞歸要素
遞歸必須包含一個基本的出口（結束條件），否則就會無限遞歸，最終導致棧溢出；
遞歸必須包含一個可以分解的問題，例如要想求得 fact(n)
fact(n)，就需要用 nfact(n1)
nfact(n1)；
遞歸必須必須要向著遞歸出口靠近，例如每次遞歸調用都會 n1
n1，向著遞歸出口 n==0
n==0 靠近。
遞歸與迭代的區別
遞歸（recursion）：遞歸則是一步一步往前遞推，直到遞歸基礎，尋找一條路徑， 然後再由前向後計算。（A調用A）
迭代（iteration）：迭代是重複反饋過程的活動，其目的通常是為了逼近所需目標或結果。每一次對過程的重複稱為一次「迭代」，而每一次迭代得到的結果會作為下一次迭代的初始值，因此迭代是從前往後計算的。（A重複調用B）
示例一：階乘
一個正整數的階乘（factorial）是所有小於及等於該數的正整數的積，並且 0 的階乘為 1。即 n!=1×2×3×...×(n1)×n
n!=1×2×3×...×(n1)×n，以遞歸方式定義：n!=(n1)!×n
n!=(n1)!×n
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
示例二：斐波那契數列
斐波那契數列（Fibonacci sequence），又稱黃金分割數列、因數學家萊昂納多·斐波那契以兔子繁殖為例子而引入，故又稱為「兔子數列」。
有一個數列：0、1、1、2、3、5、8、13、21、34、55、89…，這個數列從第3項開始，每一項都等於前兩項之和。以遞推的方法定義：F(n)=F(n1)+F(n2)（n≥3，n∈N）
F(n)=F(n1)+F(n2)（n≥3，n∈N
）
def fibonacc(n):
if n == 1 or n == 2:
return 1
else:
return fibonacc(n-1) + fibonacc(n-2)
以上方法的時間複雜度為O(2n)
O(2
n
)，稍微大一點的數都會算很久，有一個簡單的解決方案，使用 lru_cache 緩存裝飾器，緩存一些中間結果：
from functools import lru_cache
# 緩存斐波那契函數已經計算出的結果，最多佔用1024位元組內存
@lru_cache(maxsize=1024)
def fibonacc(n):
if n == 1 or n == 2:
return 1
else:
return fibonacc(n-1) + fibonacc(n-2)
另外還有更加節省時間和空間的方法：
def fibonacc(n, current=0, next=1):
if n == 0:
return current
else:
return fibonacc(n-1, next, current+next)
示例三：漢諾塔問題
漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。64片黃金圓盤移動完畢之日，就是世界毀滅之時。
01漢諾塔
對於 n 個盤子，移動步驟如下：
把 n-1 個盤子由 A 經過 C 移動到 B
把最後一個盤子移動到 C
把 n-1 個盤子由 B 經過 A 移動到 C
02漢諾塔
遞歸代碼實現：
def hanoi(n, a, b, c): # n 個盤子，a，b，c三個柱子
if n > 0:
hanoi(n-1, a, c, b) # 把 n-1 個盤子由 a 經過 c 移動到 b
print('moving from {0} to {1}'.format(a, c)) # 把最後一個盤子移動到 c
hanoi(n-1, b, a, c) # 把 n-1 個盤子由 b 經過 a 移動到 c
示例：
def hanoi(n, a, b, c):
if n > 0:
hanoi(n-1, a, c, b)
print('moving from {0} to {1}'.format(a, c))
hanoi(n-1, b, a, c)
hanoi(3, 'A', 'B', 'C')
moving from A to C
moving from A to B
moving from C to B
moving from A to C
moving from B to A
moving from B to C
moving from A to C
尾遞歸
如果一個函數中所有遞歸形式的調用都出現在函數的末尾，我們稱這個遞歸函數是尾遞歸的。通俗來講就是遞歸調用放在了函數的最後。
# 一般遞歸
def func(n):
if n > 0:
func(n-1)
print(n)
# 一般遞歸
def func(n):
if n > 0:
return func(n-1) + n
# 尾遞歸
def func(n):
a = n
if n > 0:
a += 1
print(a, n)
return func(n-1)
對於普通的遞歸，每一級遞歸都產生了新的局部變量，必須創建新的調用棧，隨著遞歸深度的增加，創建的棧越來越多，容易造成爆棧。
def normal_recursion(n):
if n == 1:
return 1
else:
return n + normal_recursion(n-1)
normal_recursion(5) 執行：
normal_recursion(5)
5 + normal_recursion(4)
5 + 4 + normal_recursion(3)
5 + 4 + 3 + normal_recursion(2)
5 + 4 + 3 + 2 + normal_recursion(1)
5 + 4 + 3 + 3
5 + 4 + 6
5 + 10
15
尾遞歸基於函數的尾調用，每一級調用直接返回遞歸函數更新調用棧，沒有新局部變量的產生，類似迭代的實現。
def tail_recursion(n, total=0):
if n == 0:
return total
else:
return tail_recursion(n-1, total+n)
normal_recursion(5) 執行：
tail_recursion(5, 0)
tail_recursion(4, 5)
tail_recursion(3, 9)
tail_recursion(2, 12)
tail_recursion(1, 14)
tail_recursion(0, 15)
15
在 Python，Java，Pascal 等語言中是無法實現尾遞歸優化的，所以採用了 for，while，goto 等特殊結構以迭代的方式來代替尾遞歸。
Python 中尾遞歸的解決方案
使用普通的遞歸來實現斐波那契數列的計算，代碼段如下：
def fibonacc(n, current=0, next=1):
if n == 0:
return current
else:
return fibonacc(n-1, next, current+next)
a = fibonacc(1000)
print(a)
此時會報錯，因為超過了最大遞歸深度（默認深度900-1000左右）：
Traceback (most recent call last):
File "F:/PycharmProjects/algorithm/fibonacc_test.py", line 57, in
a = fibonacc(1000)
File "F:/PycharmProjects/algorithm/fibonacc_test.py", line 47, in fibonacc
return fibonacc(n-1, next, current+next)
File "F:/PycharmProjects/algorithm/fibonacc_test.py", line 47, in fibonacc
return fibonacc(n-1, next, current+next)
File "F:/PycharmProjects/algorithm/fibonacc_test.py", line 47, in fibonacc
return fibonacc(n-1, next, current+next)
[Previous line repeated 995 more times]
File "F:/PycharmProjects/algorithm/fibonacc_test.py", line 44, in fibonacc
if n == 0:
RecursionError: maximum recursion depth exceeded in comparison
如果是遞歸深度不是很大的情況，可以手動重設遞歸深度來解決：
import sys
sys.setrecursionlimit(10000) # 遞歸深度設置為 10000
如果遞歸深度非常大，那麼就可以採用尾遞歸優化，但是 Python 官方是並不支持尾遞歸的（不知道為啥），然而這難不到廣大的程式設計師們，早在 2006 年 Crutcher Dunnavant 就想出了一個解決辦法，實現一個 tail_call_optimized 裝飾器，