Python開啟尾遞歸優化!

junnplus 發布于2019-07-31 10:54 / 588人閱讀

摘要：尾遞歸優化一般遞歸與尾遞歸一般遞歸執行可以看到一般遞歸每一級遞歸都產生了新的局部變量必須創建新的調用棧隨著遞歸深度的增加創建的棧越來越多造成爆棧尾遞歸尾遞歸基于函數的尾調用每一級調用直接返回遞歸函數更新調用棧沒有新局部變量的產生類似迭代的

Python尾遞歸優化 一般遞歸與尾遞歸 一般遞歸:

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

執行：

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)

執行：

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

可以看到, 尾遞歸每一級遞歸函數的調用變成"線性"的形式. 這時, 我們可以思考, 雖然尾遞歸調用也會創建新的棧, 但是我們可以優化使得尾遞歸的每一級調用共用一個棧!, 如此便可解決爆棧和遞歸深度限制的問題!

C中尾遞歸的優化

gcc使用-O2參數開啟尾遞歸優化:

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開啟尾遞歸優化

對比反匯編代碼如下(AT&T語法, 左圖為優化后)

可以看到, 開啟尾遞歸優化前, 使用call調用函數, 創建了新的調用棧(LBB0_3); 而開啟尾遞歸優化后, 就沒有新的調用棧生成了, 而是直接pop bp指向的_tail_recursion函數的地址(pushq %rbp)然后返回, 仍舊用的是同一個調用棧!

Python開啟尾遞歸優化

cpython本身不支持尾遞歸優化, 但是一個牛人想出的解決辦法：實現一個 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()函數:

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深度調用的棧幀對象.

import sys

def get_cur_info():
    print sys._getframe().f_code.co_filename  # 當前文件名
    print sys._getframe().f_code.co_name  # 當前函數名
    print sys._getframe().f_lineno # 當前行號
    print sys._getframe().f_back # 調用者的幀

更多關于sys._getframe的使用請看Frame Hacks
說一下tail_call_optimized實現尾遞歸優化的原理: 當遞歸函數被該裝飾器修飾后, 遞歸調用在裝飾器while循環內部進行, 每當產生新的遞歸調用棧幀時: f.f_back.f_back.f_code == f.f_code:, 就捕獲當前尾調用函數的參數, 并拋出異常, 從而銷毀遞歸棧并使用捕獲的參數手動調用遞歸函數. 所以遞歸的過程中始終只存在一個棧幀對象, 達到優化的目的.
為了更清晰的展示開啟尾遞歸優化前、后調用棧的變化和tail_call_optimized裝飾器拋異常退出遞歸調用棧的作用, 我這里利用pudb調試工具做了動圖:

開啟尾遞歸優化前的調用棧

開啟尾遞歸優化后(tail_call_optimized裝飾器)的調用棧

通過pudb右邊欄的stack, 可以很清晰的看到調用棧的變化.
因為實現了尾遞歸優化, 所以factorial(10000)都不害怕遞歸深度限制報錯啦!

GPU云服務器云服務器優化遞歸數據棧 python遞歸錯誤 python遞歸例子 python遞歸調用

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/44328.html

js 實現斐波那契數列(數組緩存、動態規劃、尾調用優化)

摘要：根據該規則，返回第個斐波那契數。尾遞歸函數調用自身，稱為遞歸。一個前端眼中的斐波那契數列解斐波那契數列的實用解法調用棧尾遞歸和手動優化尾調用優化譯我從用寫斐波那契生成器中學到的令人驚訝的件事斐波那契數列是以下一系列數字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在種子數字 0 和 1 ...

趙連江 2019-08-23 11:38 評論0 收藏0
用 JavaScript 實現鏈表操作 - 08 Remove Duplicates

摘要：遞歸版本尾遞歸很多遞歸沒辦法自然的寫成尾遞歸，本質原因是無法在多次遞歸過程中維護共有的變量，這也是循環的優勢所在。這是因為雖然用的，但并沒有開啟尾遞歸優化。 TL;DR 為一個已排序的鏈表去重，考慮到很長的鏈表，需要尾調用優化。系列目錄見前言和目錄。需求實現一個 removeDuplicates() 函數，給定一個升序排列過的鏈表，去除鏈表中重復的元素，并返回修改后的鏈表。理想...

Me_Kun 2019-08-21 15:04 評論0 收藏0
小李飛刀：python你慢點飛，我的腦子還在后面追

摘要：默認參數設置默認參數時，有幾點要注意一是必選參數在前，默認參數在后，否則的解釋器會報錯二是如何設置默認參數。注意此處，獲得的其實是的拷貝，函數內對的改變不會影響到。使用遞歸函數需要注意防止棧溢出。總是在最前面的叨逼叨最近總是在想成長這兩個很常常被提起的事情，這對于一個已經25歲的半中年而言，已經是一個不太能高頻提起的詞。但是，最近一些事情吧，總讓我覺得我的生長期似乎比正常人來的晚了...

kevin 2019-07-30 18:40 評論0 收藏0
Python筆記

摘要：針對尾遞歸優化的語言可以通過尾遞歸防止棧溢出。尾遞歸事實上和循環是等價的，沒有循環語句的編程語言只能通過尾遞歸實現循環。標準的解釋器沒有針對尾遞歸做優化，任何遞歸函數都存在棧溢出的問題。 python 頭部： #!/usr/bin/env python # -*- coding: utf-8 -*- 函數的參數 Python的函數具有非常靈活的參數形態，既可以實現簡單的調用，又可以傳入...

yuxue 2019-07-31 10:07 評論0 收藏0
【數據科學系統學習】Python # 編程基礎[一]

摘要：在定義函數時給定的名稱稱作形參，在調用函數時你所提供給函數的值稱作實參。調用函數要調用一個函數，需要知道函數的名稱和參數。默認參數值可以有效幫助解決這一情況。是默認參數定義默認參數要牢記一點默認參數必須指向不變對象。關于數據科學在做什么，我們已經在前兩篇文章中進行了總結，即專題概述和描述性統計分析。要進行數據科學的探索，需要一個好工具，就是Python。從本篇開始，將總結學習Pyth...

luckyyulin 2019-07-30 17:21 評論0 收藏0