Python進(jìn)階之尾遞歸的用法實例
作者是一名沉迷于Python無法自拔的蛇友，為提高水平，把Python的重點和有趣的實例發(fā)在簡書上。
尾遞歸
如果一個函數(shù)中所有遞歸形式的調(diào)用都出現(xiàn)在函數(shù)的末尾，我們稱這個遞歸函數(shù)是尾遞歸的。當(dāng)遞歸調(diào)用是整個函數(shù)體中最后執(zhí)行的語句且它的返回值不屬于表達(dá)式的一部分時，這個遞歸調(diào)用就是尾遞歸。尾遞歸函數(shù)的特點是在回歸過程中不用做任何操作，這個特性很重要，因為大多數(shù)現(xiàn)代的編譯器會利用這種特點自動生成優(yōu)化的代碼。
（來源于不說人話的某度）
下面是筆者的個人理解：把計算出的值存在函數(shù)內(nèi)部（當(dāng)然不止尾遞歸）是其計算方法，從而不用在棧中去創(chuàng)建一個新的，這樣就大大節(jié)省了空間。函數(shù)調(diào)用中最后返回的結(jié)果是單純的遞歸函數(shù)調(diào)用（或返回結(jié)果）就是尾遞歸。
實例
實例還是和筆者的上一篇文章相同，建議讀者閱讀 Python —— 遞歸
1、階乘
常規(guī)遞歸階乘：
def factorial(n):
if n == 0:
return 1
return factorial(n - 1) * n
我們來看一下執(zhí)行過程：
factorial(4)
factorial(3) * 4
factorial(2) * 3 * 4
factorial(1) * 2 * 3 * 4
factorial(0) * 1 * 2 * 3 * 4
1 * 1 * 2 * 3 * 4
1 * 2 * 3 * 4
2 * 3 * 4
6 * 4
24
但是如果把上面的函數(shù)寫成如下形式：
def factorial(n, acc=1):
if n == 0:
return acc
return factorial(n - 1, n * acc)
我們再看下執(zhí)行過程：
factorial(4, 1)
factorial(3, 4)
factorial(2, 12)
factorial(1, 24)
factorial(0, 24)
24
很直觀的就可以看出，這次的 factorial 函數(shù)在遞歸調(diào)用的時候不會產(chǎn)生一系列逐漸增多的中間變量了，而是將狀態(tài)保存在 acc 這個變量中。而這種形式的遞歸，就叫做尾遞歸。
2、斐波那契數(shù)列
常規(guī)遞斐波那契數(shù)列：
def fib(n):
if n < 2:
return n
else:
return fib(n - 1) + fib(n - 2)
而尾遞歸：
def fib_tail(n, r, t):
if n == 1:
return r
else:
return fib_tail(n - 1, t, r + t)
一下子就充滿了逼格，還高效了許多，何樂而不為呢！
總結(jié)
可以看出，在每次遞歸調(diào)用的時候，都會產(chǎn)生一個臨時變量，導(dǎo)致進(jìn)程內(nèi)存占用量增大一些。這樣執(zhí)行一些遞歸層數(shù)比較深的代碼時，除了無謂的內(nèi)存浪費，還有可能導(dǎo)致著名的堆棧溢出錯誤。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
pandas groupby分組對象的組內(nèi)排序解決方案
這篇文章主要介紹了pandas groupby分組對象的組內(nèi)排序解決方案，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-03-03
如何解決requests,已經(jīng)安裝卻無法import問題
這篇文章主要介紹了如何解決requests,已經(jīng)安裝卻無法import問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-06-06
Django websocket原理及功能實現(xiàn)代碼
這篇文章主要介紹了Django websocket原理及功能實現(xiàn)代碼,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-11-11
基于python+opencv調(diào)用電腦攝像頭實現(xiàn)實時人臉眼睛以及微笑識別
這篇文章主要為大家詳細(xì)介紹了基于python+opencv調(diào)用電腦攝像頭實現(xiàn)實時人臉眼睛以及微笑識別，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-09-09
python進(jìn)階教程之循環(huán)相關(guān)函數(shù)range、enumerate、zip
這篇文章主要介紹了python進(jìn)階教程之循環(huán)相關(guān)函數(shù)range、enumerate、zip,在使用循環(huán)程序經(jīng)常要配合這些函數(shù)來完成循環(huán),需要的朋友可以參考下2014-08-08
在軟件開發(fā)中,循環(huán)依賴是一個常見的問題,尤其是在使用 Python 這樣的動態(tài)語言時,循環(huán)依賴指的是兩個或多個模塊或組件相互依賴,形成一個閉環(huán),本文將探討 Python 中循環(huán)依賴的問題,并提供一些解決方案,需要的朋友可以參考下2024-06-06
Python是一種高級程序語言，其核心設(shè)計哲學(xué)是代碼可讀性和語法，能夠讓程序員用很少的代碼來表達(dá)自己的想法。這篇文章主要介紹了不知道這5種下劃線的含義，你就不算真的會Python!對此標(biāo)題感興趣的朋友一起閱讀本文吧2018-10-10
關(guān)于scipy.optimize函數(shù)使用及說明
這篇文章主要介紹了關(guān)于scipy.optimize函數(shù)使用及說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-12-12
本文將和大家一起了解什么是上下文管理器?和?Python?的?with?語句，以及如何完成自定義。然后擴(kuò)展?Timer?以便它也可以用作上下文管理器，感興趣的可以了解一下2022-06-06
jupyter notebook 寫代碼自動補(bǔ)全的實現(xiàn)
這篇文章主要介紹了jupyter notebook 寫代碼自動補(bǔ)全的實現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11