尾遞歸是一種特殊的遞歸形式，它在遞歸調(diào)用時(shí)不會(huì)產(chǎn)生新的棧幀，從而避免了棧溢出的問題。Python并沒有對(duì)尾遞歸進(jìn)行優(yōu)化，但我們可以通過一些技巧來實(shí)現(xiàn)遞歸優(yōu)化。本文將詳細(xì)介紹Python如何實(shí)現(xiàn)尾遞歸優(yōu)化，并提供兩個(gè)示例來說明它的用法。

什么是尾遞歸

在介紹如何實(shí)現(xiàn)尾遞歸優(yōu)化之前，我們先來了解一下什么是尾遞歸。

遞歸是指遞歸函數(shù)在調(diào)用自身之后，不再有其他操作，直接返回結(jié)果。這種形式的遞歸可以被優(yōu)化為迭代形式，從而避免了棧溢出的問題。

例如，下面是一個(gè)階乘函數(shù)的遞歸實(shí)現(xiàn)：

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

這個(gè)函數(shù)不是尾遞歸，因?yàn)樵谶f歸調(diào)用之后還有其他操作（乘法）。如果我們將其改寫為尾遞歸形式，可以得到下代碼：

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

在這個(gè)函數(shù)中，我們引入了一個(gè)額外的參數(shù)acc，用于保存中間結(jié)果。在遞歸調(diào)用時(shí)，我們將中結(jié)果乘以當(dāng)前的n，并將結(jié)果傳遞給下一次遞歸調(diào)用。當(dāng)遞歸到n=0時(shí)，我們直接返回中間結(jié)果``，從而避免了棧溢出的問題。

如何實(shí)現(xiàn)尾遞歸優(yōu)化

Python并沒有對(duì)尾遞歸進(jìn)行優(yōu)化，但我們可以通過一些技巧來實(shí)現(xiàn)尾遞歸優(yōu)化。具體來，我們可以使用循環(huán)、函數(shù)參數(shù)等方式來避免遞歸調(diào)用產(chǎn)生新的棧幀。

使用循環(huán)

使用循環(huán)是一種常見的實(shí)現(xiàn)尾遞歸優(yōu)化的方式。例如，下面是一個(gè)使用循環(huán)實(shí)現(xiàn)階乘函數(shù)的代碼：

def factorial(n):
    acc = 1
    while n > 0:
        acc *= n
        n -= 1
    return acc

在這個(gè)函數(shù)中，我們使用循環(huán)來計(jì)算階乘，避免了遞歸調(diào)用產(chǎn)生新的棧幀。

使用函數(shù)參數(shù)

使用函數(shù)參數(shù)也是一種實(shí)現(xiàn)尾遞歸優(yōu)化的方式。例如，下面是一個(gè)使用函數(shù)參數(shù)實(shí)現(xiàn)階乘函數(shù)的代碼：

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

在這個(gè)函數(shù)中，我們引入了一個(gè)額外的參數(shù)acc，用于保存中間結(jié)果。在遞歸調(diào)用時(shí)，我們將中間結(jié)果乘以當(dāng)前的參數(shù)n，并將結(jié)果傳遞給下次遞歸調(diào)用。當(dāng)遞歸到n=0時(shí)，我們直接返回中間結(jié)果acc從而避免了棧溢出的問題。

示例1：使用循環(huán)實(shí)現(xiàn)斐波那契數(shù)列

下面是一個(gè)使用循環(huán)實(shí)現(xiàn)斐波那契數(shù)列的示例：

def fibonacci(n):
    if n == 0:
        return 0
 elif n == 1:
        return 1
    else:
        a, b = 0, 1
        for i in range(n-1):
            a, b = b, a+b
        return b

在這個(gè)函數(shù)中，我們使用循環(huán)來計(jì)算斐波那契數(shù)列的第n項(xiàng)，避免了遞歸調(diào)用產(chǎn)生新的棧幀。

示例2：使用函數(shù)參數(shù)實(shí)現(xiàn)尾遞歸優(yōu)化

下面是一個(gè)使用函數(shù)參數(shù)實(shí)現(xiàn)尾遞歸優(yōu)化的階乘函數(shù)的示例：

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

在這個(gè)函數(shù)中，我們引入了一個(gè)額外的參數(shù)acc，用于保存中間結(jié)果。在遞歸調(diào)用時(shí)，我們將中間結(jié)果乘以當(dāng)前的參數(shù)n，并將結(jié)果傳遞給下一次遞調(diào)用。當(dāng)遞歸到=0時(shí)，我們直接返回中間結(jié)果acc，從而避免了棧溢出的問題。

一般遞歸與尾遞歸

一般遞歸

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)建的棧越來越多, 造成爆棧?

尾遞歸

尾遞歸基于函數(shù)的尾調(diào)用, 每一級(jí)調(diào)用直接返回遞歸函數(shù)更新調(diào)用棧, 沒有新局部變量的產(chǎn)生, 類似迭代的實(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è)棧!, 如此便可解決爆棧和遞歸深度限制的問題!

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

gcc使用-O2參數(shù)開啟尾遞歸優(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開啟尾遞歸優(yōu)化

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

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

Python開啟尾遞歸優(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)用者的幀

說一下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ù), 并拋出異常, 從而銷毀遞歸棧并使用捕獲的參數(shù)手動(dòng)調(diào)用遞歸函數(shù). 所以遞歸的過程中始終只存在一個(gè)棧幀對(duì)象, 達(dá)到優(yōu)化的目的.

為了更清晰的展示開啟尾遞歸優(yōu)化前、后調(diào)用棧的變化和tail_call_optimized裝飾器拋異常退出遞歸調(diào)用棧的作用, 我這里利用pudb調(diào)試工具做了動(dòng)圖:

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

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

通過pudb右邊欄的stack, 可以很清晰的看到調(diào)用棧的變化.

因?yàn)閷?shí)現(xiàn)了尾遞歸優(yōu)化, 所以factorial(10000)都不害怕遞歸深度限制報(bào)錯(cuò)啦!

到此這篇關(guān)于詳解Python如何實(shí)現(xiàn)尾遞歸優(yōu)化的文章就介紹到這了,更多相關(guān)Python尾遞歸優(yōu)化內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論