文章目錄

• • 遞歸概念
  • 遞歸要素
  • 遞歸與迭代的區(qū)別
  • 示例一：階乘
  • 示例二：斐波那契數(shù)列
  • 示例三：漢諾塔問題
  • 尾遞歸
  • Python 中尾遞歸的解決方案

---

遞歸概念

遞歸：程序調(diào)用自身的編程技巧稱為遞歸（ recursion）。用一種通俗的話來說就是自己調(diào)用自己，它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的、但是規(guī)模較小的問題來求解，當(dāng)問題小到一定規(guī)模的時候，需要一個遞歸出口返回。遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。

遞歸函數(shù)：在編程語言中，函數(shù)直接或間接調(diào)用函數(shù)本身，則該函數(shù)稱為遞歸函數(shù)；在數(shù)學(xué)上的定義如下：對于某一函數(shù) $f(x)$，其定義域是集合 A，那么若對于 A 集合中的某一個值 $X_0$，其函數(shù)值 $f(x_0)$ 由 $f(f(x_0))$ 決定，那么就稱 $f(x)$ 為遞歸函數(shù)。

---

遞歸要素

• 遞歸必須包含一個基本的出口（結(jié)束條件），否則就會無限遞歸，最終導(dǎo)致棧溢出；

• 遞歸必須包含一個可以分解的問題，例如要想求得 $fact(n)$，就需要用 $n?fact(n?1)$；

• 遞歸必須必須要向著遞歸出口靠近，例如每次遞歸調(diào)用都會 $n?1$，向著遞歸出口 $n==0$ 靠近。

---

遞歸與迭代的區(qū)別

• 遞歸（recursion）：遞歸則是一步一步往前遞推，直到遞歸基礎(chǔ)，尋找一條路徑， 然后再由前向后計算。（A調(diào)用A）

• 迭代（iteration）：迭代是重復(fù)反饋過程的活動，其目的通常是為了逼近所需目標(biāo)或結(jié)果。每一次對過程的重復(fù)稱為一次“迭代”，而每一次迭代得到的結(jié)果會作為下一次迭代的初始值，因此迭代是從前往后計算的。（A重復(fù)調(diào)用B）

---

示例一：階乘

一個正整數(shù)的階乘（factorial）是所有小于及等于該數(shù)的正整數(shù)的積，并且 0 的階乘為 1。即 $n!=1\times 2\times 3\times ...\times (n?1)\times n$，以遞歸方式定義：$n!=(n?1)!\times n$

def factorial(n):if n == 0:return 1else:return n * factorial(n-1)

---

示例二：斐波那契數(shù)列

斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列、因數(shù)學(xué)家萊昂納多·斐波那契以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”。

有一個數(shù)列：0、1、1、2、3、5、8、13、21、34、55、89…，這個數(shù)列從第3項開始，每一項都等于前兩項之和。以遞推的方法定義：$F(n)=F(n?1)+F(n?2)（n\ge 3，n\in N^{?}）$

def fibonacc(n):if n == 1 or n == 2:return 1else:return fibonacc(n-1) + fibonacc(n-2)

以上方法的時間復(fù)雜度為$O(2^n)$，稍微大一點的數(shù)都會算很久，有一個簡單的解決方案，使用 lru_cache 緩存裝飾器，緩存一些中間結(jié)果：

from functools import lru_cache# 緩存斐波那契函數(shù)已經(jīng)計算出的結(jié)果，最多占用1024字節(jié)內(nèi)存 @lru_cache(maxsize=1024) def fibonacc(n):if n == 1 or n == 2:return 1else:return fibonacc(n-1) + fibonacc(n-2)

另外還有更加節(jié)省時間和空間的方法：

def fibonacc(n, current=0, next=1):if n == 0:return currentelse:return fibonacc(n-1, next, current+next)

---

示例三：漢諾塔問題

漢諾塔（又稱河內(nèi)塔）問題是源于印度一個古老傳說的益智玩具。大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。64片黃金圓盤移動完畢之日，就是世界毀滅之時。

對于 n 個盤子，移動步驟如下：

• 把 n-1 個盤子由 A 經(jīng)過 C 移動到 B
• 把最后一個盤子移動到 C
• 把 n-1 個盤子由 B 經(jīng)過 A 移動到 C

遞歸代碼實現(xiàn)：

def hanoi(n, a, b, c): # n 個盤子，a，b，c三個柱子if n > 0:hanoi(n-1, a, c, b) # 把 n-1 個盤子由 a 經(jīng)過 c 移動到 bprint('moving from {0} to {1}'.format(a, c)) # 把最后一個盤子移動到 chanoi(n-1, b, a, c) # 把 n-1 個盤子由 b 經(jīng)過 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

---

尾遞歸

如果一個函數(shù)中所有遞歸形式的調(diào)用都出現(xiàn)在函數(shù)的末尾，我們稱這個遞歸函數(shù)是尾遞歸的。通俗來講就是遞歸調(diào)用放在了函數(shù)的最后。

# 一般遞歸 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 = nif n > 0:a += 1print(a, n)return func(n-1)

對于普通的遞歸，每一級遞歸都產(chǎn)生了新的局部變量，必須創(chuàng)建新的調(diào)用棧，隨著遞歸深度的增加，創(chuàng)建的棧越來越多，容易造成爆棧。

def normal_recursion(n):if n == 1:return 1else:return n + normal_recursion(n-1)

normal_recursion(5) 執(zhí)行：

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

尾遞歸基于函數(shù)的尾調(diào)用，每一級調(diào)用直接返回遞歸函數(shù)更新調(diào)用棧，沒有新局部變量的產(chǎn)生，類似迭代的實現(xiàn)。

def tail_recursion(n, total=0):if n == 0:return totalelse:return tail_recursion(n-1, total+n)

normal_recursion(5) 執(zhí)行：

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 等語言中是無法實現(xiàn)尾遞歸優(yōu)化的，所以采用了 for，while，goto 等特殊結(jié)構(gòu)以迭代的方式來代替尾遞歸。

---

Python 中尾遞歸的解決方案

使用普通的遞歸來實現(xiàn)斐波那契數(shù)列的計算，代碼段如下：

def fibonacc(n, current=0, next=1):if n == 0:return currentelse:return fibonacc(n-1, next, current+next)a = fibonacc(1000) print(a)

此時會報錯，因為超過了最大遞歸深度（默認(rèn)深度900-1000左右）：

Traceback (most recent call last):File "F:/PycharmProjects/algorithm/fibonacc_test.py", line 57, in <module>a = fibonacc(1000)File "F:/PycharmProjects/algorithm/fibonacc_test.py", line 47, in fibonaccreturn fibonacc(n-1, next, current+next)File "F:/PycharmProjects/algorithm/fibonacc_test.py", line 47, in fibonaccreturn fibonacc(n-1, next, current+next)File "F:/PycharmProjects/algorithm/fibonacc_test.py", line 47, in fibonaccreturn fibonacc(n-1, next, current+next)[Previous line repeated 995 more times]File "F:/PycharmProjects/algorithm/fibonacc_test.py", line 44, in fibonaccif n == 0: RecursionError: maximum recursion depth exceeded in comparison

如果是遞歸深度不是很大的情況，可以手動重設(shè)遞歸深度來解決：

import sys sys.setrecursionlimit(10000) # 遞歸深度設(shè)置為 10000

如果遞歸深度非常大，那么就可以采用尾遞歸優(yōu)化，但是 Python 官方是并不支持尾遞歸的（不知道為啥），然而這難不到廣大的程序員們，早在 2006 年 Crutcher Dunnavant 就想出了一個解決辦法，實現(xiàn)一個 tail_call_optimized 裝飾器，原文鏈接：https://code.activestate.com/recipes/474088/，原代碼是 Python 2.4 實現(xiàn)的，用 Python 3.x 實現(xiàn)如下：

# This program shows off a python decorator # which implements tail call optimization. It # does this by throwing an exception if it is # it's own grandparent, and catching such # exceptions to recall the stack.import sysclass TailRecurseException(BaseException):def __init__(self, args, kwargs):self.args = argsself.kwargs = kwargsdef tail_call_optimized(g):"""This function decorates a function with tail calloptimization. It does this by throwing an exceptionif it is it's own grandparent, and catching suchexceptions to fake the tail call optimization.This function fails if the decorated5function recurses in a non-tail context."""def func(*args, **kwargs):f = sys._getframe()if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:raise TailRecurseException(args, kwargs)else:while 1:try:return g(*args, **kwargs)except TailRecurseException as e:args = e.argskwargs = e.kwargsfunc.__doc__ = g.__doc__return func

使用該裝飾器再來實現(xiàn)比較大的斐波那契數(shù)列的計算：

@tail_call_optimized def fibonacc(n, current=0, next=1):if n == 0:return currentelse:return fibonacc(n-1, next, current+next)a = fibonacc(1000) print(a)

輸出結(jié)果：

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

tail_call_optimized 實現(xiàn)尾遞歸優(yōu)化的原理：當(dāng)遞歸函數(shù)被該裝飾器修飾后，遞歸調(diào)用在裝飾器while循環(huán)內(nèi)部進(jìn)行，每當(dāng)產(chǎn)生新的遞歸調(diào)用棧幀時，f.f_back.f_back.f_code == f.f_code: 就捕獲當(dāng)前尾調(diào)用函數(shù)的參數(shù)，并拋出異常，從而銷毀遞歸棧并使用捕獲的參數(shù)手動調(diào)用遞歸函數(shù)，所以遞歸的過程中始終只存在一個棧幀對象，達(dá)到優(yōu)化的目的。

---

這里是一段防爬蟲文本，請讀者忽略。 本文原創(chuàng)首發(fā)于 CSDN，作者 TRHX?鮑勃。 博客首頁：https://itrhx.blog.csdn.net/ 本文鏈接：https://itrhx.blog.csdn.net/article/details/109322815 未經(jīng)授權(quán)，禁止轉(zhuǎn)載！惡意轉(zhuǎn)載，后果自負(fù)！尊重原創(chuàng)，遠(yuǎn)離剽竊！ 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的Python 算法之递归与尾递归，斐波那契数列以及汉诺塔的实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。