作者是一名沉迷于Python無法自拔的蛇友，為提高水平，把Python的重點(diǎn)和有趣的實(shí)例發(fā)在簡(jiǎn)書上。

尾遞歸

如果一個(gè)函數(shù)中所有遞歸形式的調(diào)用都出現(xiàn)在函數(shù)的末尾，我們稱這個(gè)遞歸函數(shù)是尾遞歸的。當(dāng)遞歸調(diào)用是整個(gè)函數(shù)體中最后執(zhí)行的語句且它的返回值不屬于表達(dá)式的一部分時(shí)，這個(gè)遞歸調(diào)用就是尾遞歸。尾遞歸函數(shù)的特點(diǎn)是在回歸過程中不用做任何操作，這個(gè)特性很重要，因?yàn)榇蠖鄶?shù)現(xiàn)代的編譯器會(huì)利用這種特點(diǎn)自動(dòng)生成優(yōu)化的代碼。

（來源于不說人話的某度）

下面是筆者的個(gè)人理解：把計(jì)算出的值存在函數(shù)內(nèi)部（當(dāng)然不止尾遞歸）是其計(jì)算方法，從而不用在棧中去創(chuàng)建一個(gè)新的，這樣就大大節(jié)省了空間。函數(shù)調(diào)用中最后返回的結(jié)果是單純的遞歸函數(shù)調(diào)用（或返回結(jié)果）就是尾遞歸。

實(shí)例

實(shí)例還是和筆者的上一篇文章相同，建議讀者閱讀 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)

我們?cè)倏聪聢?zhí)行過程：

factorial(4, 1) 
factorial(3, 4) 
factorial(2, 12) 
factorial(1, 24) 
factorial(0, 24) 
24

很直觀的就可以看出，這次的 factorial 函數(shù)在遞歸調(diào)用的時(shí)候不會(huì)產(chǎn)生一系列逐漸增多的中間變量了，而是將狀態(tài)保存在 acc 這個(gè)變量中。而這種形式的遞歸，就叫做尾遞歸。

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)用的時(shí)候，都會(huì)產(chǎn)生一個(gè)臨時(shí)變量，導(dǎo)致進(jìn)程內(nèi)存占用量增大一些。這樣執(zhí)行一些遞歸層數(shù)比較深的代碼時(shí)，除了無謂的內(nèi)存浪費(fèi)，還有可能導(dǎo)致著名的堆棧溢出錯(cuò)誤。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論