python遞歸_python算法遞歸于尾遞歸！

遞歸概念

遞歸：程式調用自身的程式設計技巧稱為遞歸（ 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 裝飾器，