Python開(kāi)啟尾遞歸優(yōu)化!

junnplus 發(fā)布于2019-07-31 10:54 / 599人閱讀

摘要：尾遞歸優(yōu)化一般遞歸與尾遞歸一般遞歸執(zhí)行可以看到一般遞歸每一級(jí)遞歸都產(chǎn)生了新的局部變量必須創(chuàng)建新的調(diào)用棧隨著遞歸深度的增加創(chuàng)建的棧越來(lái)越多造成爆棧尾遞歸尾遞歸基于函數(shù)的尾調(diào)用每一級(jí)調(diào)用直接返回遞歸函數(shù)更新調(diào)用棧沒(méi)有新局部變量的產(chǎn)生類(lèi)似迭代的

Python尾遞歸優(yōu)化 一般遞歸與尾遞歸 一般遞歸:

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

執(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

可以看到, 一般遞歸, 每一級(jí)遞歸都產(chǎn)生了新的局部變量, 必須創(chuàng)建新的調(diào)用棧, 隨著遞歸深度的增加, 創(chuàng)建的棧越來(lái)越多, 造成爆棧?

尾遞歸

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

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

執(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

可以看到, 尾遞歸每一級(jí)遞歸函數(shù)的調(diào)用變成"線性"的形式. 這時(shí), 我們可以思考, 雖然尾遞歸調(diào)用也會(huì)創(chuàng)建新的棧, 但是我們可以優(yōu)化使得尾遞歸的每一級(jí)調(diào)用共用一個(gè)棧!, 如此便可解決爆棧和遞歸深度限制的問(wèn)題!

C中尾遞歸的優(yōu)化

gcc使用-O2參數(shù)開(kāi)啟尾遞歸優(yōu)化:

int tail_recursion(int n, int total) {
    if (n == 0) {
        return total;
    }
    else {
        return tail_recursion(n-1, total+n);
    }
}

int main(void) {
    int total = 0, n = 4;
    tail_recursion(n, total);
    return 0;
}

反匯編

$ gcc -S tail_recursion.c -o normal_recursion.S
$ gcc -S -O2 tail_recursion.c -o tail_recursion.S gcc開(kāi)啟尾遞歸優(yōu)化

對(duì)比反匯編代碼如下(AT&T語(yǔ)法, 左圖為優(yōu)化后)

可以看到, 開(kāi)啟尾遞歸優(yōu)化前, 使用call調(diào)用函數(shù), 創(chuàng)建了新的調(diào)用棧(LBB0_3); 而開(kāi)啟尾遞歸優(yōu)化后, 就沒(méi)有新的調(diào)用棧生成了, 而是直接pop bp指向的_tail_recursion函數(shù)的地址(pushq %rbp)然后返回, 仍舊用的是同一個(gè)調(diào)用棧!

Python開(kāi)啟尾遞歸優(yōu)化

cpython本身不支持尾遞歸優(yōu)化, 但是一個(gè)牛人想出的解決辦法：實(shí)現(xiàn)一個(gè) tail_call_optimized 裝飾器

#!/usr/bin/env python2.4
# 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 sys

class TailRecurseException:
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs

def tail_call_optimized(g):
    """
    This function decorates a function with tail call
    optimization. It does this by throwing an exception
    if it is it"s own grandparent, and catching such
    exceptions to fake the tail call optimization.

    This function fails if the decorated
    function 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, e:
                    args = e.args
                    kwargs = e.kwargs
    func.__doc__ = g.__doc__
    return func

@tail_call_optimized
def factorial(n, acc=1):
    "calculate a factorial"
    if n == 0:
        return acc
    return factorial(n-1, n*acc)

print factorial(10000)

這里解釋一下sys._getframe()函數(shù):

sys._getframe([depth]):
Return a frame object from the call stack.
If optional integer depth is given, return the frame object that many calls below the top of the stack.
If that is deeper than the call stack, ValueEfror is raised. The default for depth is zero,
returning the frame at the top of the call stack.

即返回depth深度調(diào)用的棧幀對(duì)象.

import sys

def get_cur_info():
    print sys._getframe().f_code.co_filename  # 當(dāng)前文件名
    print sys._getframe().f_code.co_name  # 當(dāng)前函數(shù)名
    print sys._getframe().f_lineno # 當(dāng)前行號(hào)
    print sys._getframe().f_back # 調(diào)用者的幀

更多關(guān)于sys._getframe的使用請(qǐng)看Frame Hacks
說(shuō)一下tail_call_optimized實(shí)現(xiàn)尾遞歸優(yōu)化的原理: 當(dāng)遞歸函數(shù)被該裝飾器修飾后, 遞歸調(diào)用在裝飾器while循環(huán)內(nèi)部進(jìn)行, 每當(dāng)產(chǎn)生新的遞歸調(diào)用棧幀時(shí): f.f_back.f_back.f_code == f.f_code:, 就捕獲當(dāng)前尾調(diào)用函數(shù)的參數(shù), 并拋出異常, 從而銷(xiāo)毀遞歸棧并使用捕獲的參數(shù)手動(dòng)調(diào)用遞歸函數(shù). 所以遞歸的過(guò)程中始終只存在一個(gè)棧幀對(duì)象, 達(dá)到優(yōu)化的目的.
為了更清晰的展示開(kāi)啟尾遞歸優(yōu)化前、后調(diào)用棧的變化和tail_call_optimized裝飾器拋異常退出遞歸調(diào)用棧的作用, 我這里利用pudb調(diào)試工具做了動(dòng)圖:

開(kāi)啟尾遞歸優(yōu)化前的調(diào)用棧

開(kāi)啟尾遞歸優(yōu)化后(tail_call_optimized裝飾器)的調(diào)用棧

通過(guò)pudb右邊欄的stack, 可以很清晰的看到調(diào)用棧的變化.
因?yàn)閷?shí)現(xiàn)了尾遞歸優(yōu)化, 所以factorial(10000)都不害怕遞歸深度限制報(bào)錯(cuò)啦!

GPU云服務(wù)器云服務(wù)器優(yōu)化遞歸數(shù)據(jù)棧 python遞歸錯(cuò)誤 python遞歸例子 python遞歸調(diào)用

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/44328.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

junnplus

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

mxnet

閱讀 2264·2023-04-26 01:50
云主機(jī)怎么安裝-云主機(jī)怎么配置環(huán)境？

閱讀 720·2021-09-22 15:20
圖片加載相關(guān)技術(shù)

閱讀 2599·2019-08-30 15:53
【移動(dòng)適配】一個(gè)像素的border怎么實(shí)現(xiàn)

閱讀 1602·2019-08-30 12:49
Blockstack-2 ：Blockstack ID注冊(cè)

閱讀 1718·2019-08-26 14:05
阿里云上到底能運(yùn)行SAP哪些產(chǎn)品?

閱讀 2716·2019-08-26 11:42
學(xué)習(xí) underscore 源碼整體架構(gòu)，打造屬于自己的函數(shù)式編程類(lèi)庫(kù)

閱讀 2310·2019-08-26 10:40
JS之閉包及其作用

閱讀 2607·2019-08-26 10:38

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

Python開(kāi)啟尾遞歸優(yōu)化!

相關(guān)文章

**js 實(shí)現(xiàn)斐波那契數(shù)列(數(shù)組緩存、動(dòng)態(tài)規(guī)劃、尾調(diào)用優(yōu)化)**

用 JavaScript 實(shí)現(xiàn)鏈表操作 - 08 Remove Duplicates

**小李飛刀：python你慢點(diǎn)飛，我的腦子還在后面追**

Python筆記

**【數(shù)據(jù)科學(xué)系統(tǒng)學(xué)習(xí)】Python # 編程基礎(chǔ)[一]**

發(fā)表評(píng)論

0條評(píng)論

junnplus

男|高級(jí)講師

TA的文章

mxnet

云主機(jī)怎么安裝-云主機(jī)怎么配置環(huán)境？

圖片加載相關(guān)技術(shù)

【移動(dòng)適配】一個(gè)像素的border怎么實(shí)現(xiàn)

Blockstack-2 ：Blockstack ID注冊(cè)

阿里云上到底能運(yùn)行SAP哪些產(chǎn)品?

學(xué)習(xí) underscore 源碼整體架構(gòu)，打造屬于自己的函數(shù)式編程類(lèi)庫(kù)

JS之閉包及其作用

最新活動(dòng)

資訊專(zhuān)欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

Python開(kāi)啟尾遞歸優(yōu)化!

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！