3.2 函數(shù)和所生成的過程

來源：3.2 Functions and the Processes They Generate

譯者：飛龍

協(xié)議：CC BY-NC-SA 4.0

函數(shù)是計算過程的局部演化模式。它規(guī)定了過程的每個階段如何構(gòu)建在之前的階段之上泉粉。我們希望能夠創(chuàng)建有關(guān)過程整體行為的語句炭分，而過程的局部演化由一個或多個函數(shù)指定。這種分析通常非常困難延届，但是我們至少可以試圖描述一些典型的過程演化模式址貌。

在這一章中脚翘，我們會檢測一些用于簡單函數(shù)所生成過程的通用“模型”骂因。我們也會研究這些過程消耗重要的計算資源炎咖，例如時間和空間的比例。

3.2.1 遞歸函數(shù)

如果函數(shù)的函數(shù)體直接或者間接自己調(diào)用自己寒波，那么這個函數(shù)是遞歸的乘盼。也就是說，遞歸函數(shù)的執(zhí)行過程可能需要再次調(diào)用這個函數(shù)俄烁。Python 中的遞歸函數(shù)不需要任何特殊的語法绸栅，但是它們的確需要一些注意來正確定義。

作為遞歸函數(shù)的介紹页屠，我們以將英文單詞轉(zhuǎn)換為它的 Pig Latin 等價形式開始粹胯。Pig Latin 是一種隱語：對英文單詞使用一種簡單、確定的轉(zhuǎn)換來掩蓋單詞的含義卷中。Thomas Jefferson 據(jù)推測是先行者矛双。英文單詞的 Pig Latin 等價形式將輔音前綴（可能為空）從開頭移動到末尾渊抽，并且添加-ay元音蟆豫。所以，pun會變成unpay懒闷，stout會變成outstay十减，all會變成allay栈幸。

>>> def pig_latin(w):
        """Return the Pig Latin equivalent of English word w."""
        if starts_with_a_vowel(w):
            return w + 'ay'
        return pig_latin(w[1:] + w[0])
>>> def starts_with_a_vowel(w):
        """Return whether w begins with a vowel."""
        return w[0].lower() in 'aeiou'

這個定義背后的想法是，一個以輔音開頭的字符串的 Pig Latin 變體和另一個字符串的 Pig Latin 變體相同：它通過將第一個字母移到末尾來創(chuàng)建帮辟。于是速址，sending的 Pig Latin 變體就和endings的變體（endingsay）相同。smother的 Pig Latin 變體和mothers的變體（othersmay）相同由驹。而且芍锚，將輔音從開頭移動到末尾會產(chǎn)生帶有更少輔音前綴的更簡單的問題。在sending的例子中蔓榄，將s移動到末尾會產(chǎn)生以元音開頭的單詞并炮，我們的任務(wù)就完成了。

即使pig_latin函數(shù)在它的函數(shù)體中調(diào)用甥郑，pig_latin的定義是完整且正確的逃魄。

>>> pig_latin('pun')
'unpay'

能夠基于函數(shù)自身來定義函數(shù)的想法可能十分令人混亂：“循環(huán)”定義如何有意義，這看起來不是很清楚澜搅，更不用說讓計算機來執(zhí)行定義好的過程伍俘。但是，我們能夠準(zhǔn)確理解遞歸函數(shù)如何使用我們的計算環(huán)境模型來成功調(diào)用勉躺。環(huán)境的圖示和描述pig_latin('pun')求值的表達(dá)式樹展示在下面：

Python 求值過程的步驟產(chǎn)生如下結(jié)果：

1. pig_latin的def語句 被執(zhí)行癌瘾，其中：
   1. 使用函數(shù)體創(chuàng)建新的pig_latin函數(shù)對象，并且
   2. 將名稱pig_latin在當(dāng)前（全局）幀中綁定到這個函數(shù)上饵溅。
2. starts_with_a_vowel的def語句類似地執(zhí)行柳弄。
3. 求出pig_latin('pun')的調(diào)用表達(dá)式，通過
   1. 求出運算符和操作數(shù)子表達(dá)式概说，通過
      1. 查找綁定到pig_latin函數(shù)的pig_latin名稱
      2. 對字符串對象'pun'求出操作數(shù)字符串字面值
   2. 在參數(shù)'pun'上調(diào)用pig_latin函數(shù)碧注，通過
      1. 添加擴展自全局幀的局部幀
      2. 將形參w綁定到當(dāng)前幀的實參'pun'上。
      3. 在以當(dāng)前幀起始的環(huán)境中執(zhí)行pig_latin的函數(shù)體
         1. 最開始的條件語句沒有效果糖赔，因為頭部表達(dá)式求值為False
         2. 求出最后的返回表達(dá)式pig_latin(w[1:] + w[0])萍丐，通過
            1. 查找綁定到pig_latin函數(shù)的pig_latin名稱
            2. 對字符串對象'pun'求出操作數(shù)表達(dá)式
            3. 在參數(shù)'unp'上調(diào)用pig_latin，它會從pig_latin函數(shù)體中的條件語句組返回預(yù)期結(jié)果放典。

就像這個例子所展示的那樣逝变，雖然遞歸函數(shù)具有循環(huán)特征，他仍舊正確調(diào)用奋构。pig_latin函數(shù)調(diào)用了兩次壳影，但是每次都帶有不同的參數(shù)。雖然第二個調(diào)用來自pig_latin自己的函數(shù)體弥臼，但由名稱查找函數(shù)會成功宴咧，因為名稱pig_latin在它的函數(shù)體執(zhí)行前的環(huán)境中綁定。

這個例子也展示了 Python 的遞歸函數(shù)的求值過程如何與遞歸函數(shù)交互径缅，來產(chǎn)生帶有許多嵌套步驟的復(fù)雜計算過程掺栅，即使函數(shù)定義本身可能包含非常少的代碼行數(shù)烙肺。

3.2.2 剖析遞歸函數(shù)

許多遞歸函數(shù)的函數(shù)體中都存在通用模式。函數(shù)體以基本條件開始氧卧，它是一個條件語句桃笙，為需要處理的最簡單的輸入定義函數(shù)行為。在pig_latin的例子中沙绝，基本條件對任何以元音開頭的單詞成立搏明。這個時候，只需要返回末尾附加ay的參數(shù)闪檬。一些遞歸函數(shù)會有多重基本條件熏瞄。

基本條件之后是一個或多個遞歸調(diào)用。遞歸調(diào)用有特定的特征：它們必須簡化原始問題谬以。在pig_latin的例子中强饮，w中最開始輔音越多，就需要越多的處理工作为黎。在遞歸調(diào)用pig_latin(w[1:] + w[0])中邮丰，我們在一個具有更少初始輔音的單詞上調(diào)用pig_latin -- 這就是更簡化的問題。每個成功的pig_latin調(diào)用都會更加簡化铭乾，直到滿足了基本條件：一個沒有初始輔音的單詞剪廉。

遞歸調(diào)用通過逐步簡化問題來表達(dá)計算。與我們在過去使用過的迭代方式相比炕檩，它們通常以不同方式來解決問題斗蒋。考慮用于計算n的階乘的函數(shù)fact笛质，其中fact(4)計算了4! = 4·3·2·1 = 24泉沾。

使用while語句的自然實現(xiàn)會通過將每個截至n的正數(shù)相乘來求出結(jié)果。

>>> def fact_iter(n):
        total, k = 1, 1
        while k <= n:
            total, k = total * k, k + 1
        return total
>>> fact_iter(4)
24

另一方面妇押，階乘的遞歸實現(xiàn)可以以fact(n-1)（一個更簡單的問題）來表示fact(n)跷究。遞歸的基本條件是問題的最簡形式：fact(1)是1。

>>> def fact(n):
        if n == 1:
            return 1
        return n * fact(n-1)
>>> fact(4)
24

函數(shù)的正確性可以輕易通過階乘函數(shù)的標(biāo)準(zhǔn)數(shù)學(xué)定義來驗證敲霍。

(n ? 1)! = (n ? 1)·(n ? 2)· ... · 1
n俊马！ = n·(n ? 1)·(n ? 2)· ... · 1
n! = n·(n ? 1)!  

這兩個階乘函數(shù)在概念上不同。迭代的函數(shù)通過將每個式子肩杈，從基本條件1到最終的總數(shù)逐步相乘來構(gòu)造結(jié)果柴我。另一方面，遞歸函數(shù)直接從最終的式子n和簡化的問題fact(n-1)構(gòu)造結(jié)果扩然。

將fact函數(shù)應(yīng)用于更簡單的問題實例艘儒，來展開遞歸的同時，結(jié)果最終由基本條件構(gòu)建。下面的圖示展示了遞歸如何向fact傳入1而終止索守，以及每個調(diào)用的結(jié)果如何依賴于下一個調(diào)用，直到滿足了基本條件卵佛。

雖然我們可以使用我們的計算模型展開遞歸，通常把遞歸調(diào)用看做函數(shù)抽象更清晰一些截汪。也就是說，我們不應(yīng)該關(guān)心fact(n-1)如何在fact的函數(shù)體中實現(xiàn)阳柔；我們只需要相信它計算了n-1的階乘。將遞歸調(diào)用看做函數(shù)抽象叫做遞歸的“信仰飛躍”（leap of faith）舌剂。我們以函數(shù)自身來定義函數(shù)，但是僅僅相信更簡單的情況在驗證函數(shù)正確性時會正常工作暑椰。這個例子中我們相信霍转，fact(n-1)會正確計算(n-1)!；我們只需要檢查一汽，如果滿足假設(shè)n!是否正確計算避消。這樣，遞歸函數(shù)正確性的驗證就變成了一種歸納證明召夹。

函數(shù)fact_iter和fact也不一樣岩喷，因為前者必須引入兩個額外的名稱，total和k监憎，它們在遞歸實現(xiàn)中并不需要均驶。通常，迭代函數(shù)必須維護一些局部狀態(tài)枫虏，它們會在計算過程中改變妇穴。在任何迭代的時間點上，狀態(tài)刻畫了已完成的結(jié)果隶债，以及未完成的工作總量腾它。例如，當(dāng)k為3且total為2時死讹，就還剩下兩個式子沒有處理瞒滴，3和4。另一方面，fact由單一參數(shù)n來刻畫妓忍。計算的狀態(tài)完全包含在表達(dá)式樹的結(jié)果中虏两，它的返回值起到total的作用，并且在不同的幀中將n綁定到不同的值上世剖，而不是顯式跟蹤k定罢。

遞歸函數(shù)可以更加依賴于解釋器本身，通過將計算狀態(tài)儲存為表達(dá)式樹和環(huán)境的一部分旁瘫，而不是顯式使用局部幀中的名稱祖凫。出于這個原因，遞歸函數(shù)通常易于定義惠况，因為我們不需要試著弄清必須在迭代中維護的局部狀態(tài)稠屠。另一方面完箩，學(xué)會弄清由遞歸函數(shù)實現(xiàn)的計算過程弊知，需要一些練習(xí)秩彤。

3.2.3 樹形遞歸

另一個遞歸的普遍模式叫做樹形遞歸漫雷。例如降盹，考慮斐波那契序列的計算谤辜，其中每個數(shù)值都是前兩個的和丑念。

>>> def fib(n):
        if n == 1:
            return 0
        if n == 2:
            return 1
        return fib(n-2) + fib(n-1)
>>> fib(6)
5

這個遞歸定義和我們之前的嘗試有很大關(guān)系：它準(zhǔn)確反映了斐波那契數(shù)的相似定義脯倚。考慮求出fib(6)所產(chǎn)生的計算模式恍涂，它展示在下面尼夺。為了計算fib(6)汞斧，我們需要計算fib(5)和fib(4)什燕。為了計算fib(5)屎即，我們需要計算fib(4)和fib(3)技俐。通常统台，這個演化過程看起來像一棵樹（下面的圖并不是完整的表達(dá)式樹贱勃，而是簡化的過程描述仇穗；一個完整的表達(dá)式樹也擁有同樣的結(jié)構(gòu)）戚绕。在遍歷這棵樹的過程中舞丛，每個藍(lán)點都表示斐波那契數(shù)的已完成計算球切。

調(diào)用自身多次的函數(shù)叫做樹形遞歸片林。以樹形遞歸為原型編寫的函數(shù)十分有用费封，但是用于計算斐波那契數(shù)則非常糟糕，因為它做了很多重復(fù)的計算焚鹊。要注意整個fib(4)的計算是重復(fù)的，它幾乎是一半的工作量锤窑。實際上渊啰，不難得出函數(shù)用于計算fib(1)和fib(2)（通常是樹中的葉子數(shù)量）的時間是fib(n+1)隧膏。為了弄清楚這有多糟糕嚷那，我們可以證明fib(n)的值隨著n以指數(shù)方式增長腐泻。所以贫悄，這個過程的步驟數(shù)量隨輸入以指數(shù)方式增長窄坦。

我們已經(jīng)見過斐波那契數(shù)的迭代實現(xiàn)鸭津，出于便利在這里貼出來：

>>> def fib_iter(n):
        prev, curr = 1, 0  # curr is the first Fibonacci number.
        for _ in range(n-1):
             prev, curr = curr, prev + curr
        return curr

這里我們必須維護的狀態(tài)由當(dāng)前值和上一個斐波那契數(shù)組成逆趋。for語句也顯式跟蹤了迭代數(shù)量闻书。這個定義并沒有像遞歸方式那樣清晰反映斐波那契數(shù)的數(shù)學(xué)定義魄眉。但是坑律，迭代實現(xiàn)中所需的計算總數(shù)只是線性晃择，而不是指數(shù)于n的宫屠。甚至對于n的較小值，這個差異都非常大作彤。

然而我們不應(yīng)該從這個差異總結(jié)出，樹形遞歸的過程是沒有用的浙踢。當(dāng)我們考慮層次數(shù)據(jù)結(jié)構(gòu)洛波，而不是數(shù)值上的操作時蹬挤，我們發(fā)現(xiàn)樹形遞歸是自然而強大的工具。而且吨悍，樹形過程可以變得更高效育瓜。

記憶躏仇。用于提升重復(fù)計算的遞歸函數(shù)效率的機制叫做記憶焰手。記憶函數(shù)會為任何之前接受的參數(shù)儲存返回值蚓挤。fib(4)的第二次調(diào)用不會執(zhí)行與第一次同樣的復(fù)雜過程灿意，而是直接返回第一次調(diào)用的已儲存結(jié)果缤剧。

記憶函數(shù)可以自然表達(dá)為高階函數(shù)荒辕，也可以用作裝飾器。下面的定義為之前的已計算結(jié)果創(chuàng)建緩存李皇，由被計算的參數(shù)索引宙枷。在這個實現(xiàn)中慰丛，這個字典的使用需要記憶函數(shù)的參數(shù)是不可變的哪亿。

>>> def memo(f):
        """Return a memoized version of single-argument function f."""
        cache = {}
        def memoized(n):
            if n not in cache:
                cache[n] = f(n)
            return cache[n]
        return memoized
>>> fib = memo(fib)
>>> fib(40)
63245986

由記憶函數(shù)節(jié)省的所需的計算時間總數(shù)在這個例子中是巨大的锣夹。被記憶的遞歸函數(shù)fib和迭代函數(shù)fib_iter都只需要線性于輸入n的時間總數(shù)。為了計算fib(40)苏潜，fib的函數(shù)體只執(zhí)行 40 次银萍，而不是無記憶遞歸中的 102,334,155 次。

空間恤左。為了理解函數(shù)所需的空間贴唇，我們必須在我們的計算模型中規(guī)定內(nèi)存如何使用搀绣，保留和回收。在求解表達(dá)式過程中戳气，我們必須保留所有活動環(huán)境和所有這些環(huán)境引用的值和幀链患。如果環(huán)境為表達(dá)式樹當(dāng)前分支中的一些表達(dá)式提供求值上下文呀袱，那么它就是活動環(huán)境寇僧。

例如，當(dāng)求值fib時馒铃，解釋器按序計算之前的每個值议谷，遍歷樹形結(jié)構(gòu)逼裆。為了這樣做恢着，它只需要在計算的任何時間點，跟蹤樹中在當(dāng)前節(jié)點之前的那些節(jié)點。用于求出剩余節(jié)點的內(nèi)存可以被回收，因為它不會影響未來的計算。通常，樹形遞歸所需空間與樹的深度成正比。

下面的圖示描述了由求解fib(3)生成的表達(dá)式樹。在求解fib最初調(diào)用的返回表達(dá)式的過程中，fib(n-2)被求值，產(chǎn)生值0卷雕。一旦這個值計算出來九孩，對應(yīng)的環(huán)境幀（標(biāo)為灰色）就不再需要了：它并不是活動環(huán)境的一部分宪拥。所以球涛，一個設(shè)計良好的解釋器會回收用于儲存這個幀的內(nèi)存从祝。另一方面呐赡，如果解釋器當(dāng)前正在求解fib(n-1)误趴，那么由這次fib調(diào)用（其中n為2）創(chuàng)建的環(huán)境是活動的看杭。與之對應(yīng)贮缅，最開始在3上調(diào)用fib所創(chuàng)建的環(huán)境也是活動的桂肌，因為這個值還沒有成功計算出來萍诱。

在memo的例子中，只要一些名稱綁定到了活動環(huán)境中的某個函數(shù)上籍凝，關(guān)聯(lián)到所返回函數(shù)（它包含cache）的環(huán)境必須保留退盯。cache字典中的條目數(shù)量隨傳遞給fib的唯一參數(shù)數(shù)量線性增長毒租，它的規(guī)模線性于輸入噩斟。另一方面炭庙，迭代實現(xiàn)只需要兩個數(shù)值來在計算過程中跟蹤：prev和curr腻脏，所以是常數(shù)大小鸦泳。

我們使用記憶函數(shù)的例子展示了編程中的通用模式，即通臣Ｂ可以通過增加所用空間來減少計算時間辽故，反之亦然。

3.2.4 示例：找零

考慮下面這個問題：如果給你半美元腐碱、四分之一美元、十美分、五美分和一美分症见，一美元有多少種找零的方式喂走？更通常來說，我們能不能編寫一個函數(shù)谋作，使用一系列貨幣的面額芋肠，計算有多少種方式為給定的金額總數(shù)找零？

這個問題可以用遞歸函數(shù)簡單解決遵蚜。假設(shè)我們認(rèn)為可用的硬幣類型以某種順序排列帖池，假設(shè)從大到小排列。

使用n種硬幣找零的方式為：

1. 使用所有除了第一種之外的硬幣為a找零的方式吭净，以及
2. 使用n種硬幣為更小的金額a - d找零的方式睡汹，其中d是第一種硬幣的面額。

為了弄清楚為什么這是正確的寂殉，可以看出囚巴，找零方式可以分為兩組，不使用第一種硬幣的方式友扰，和使用它們的方式彤叉。所以，找零方式的總數(shù)等于不使用第一種硬幣為該金額找零的方式數(shù)量村怪，加上使用第一種硬幣至少一次的方式數(shù)量秽浇。而后者的數(shù)量等于在使用第一種硬幣之后，為剩余的金額找零的方式數(shù)量甚负。

因此柬焕，我們可以遞歸將給定金額的找零問題，歸約為使用更少種類的硬幣為更小的金額找零的問題腊敲。仔細(xì)考慮這個歸約原則击喂，并且說服自己，如果我們規(guī)定了下列基本條件碰辅，我們就可以使用它來描述算法：

1. 如果a正好是零懂昂，那么有一種找零方式。
2. 如果a小于零没宾，那么有零種找零方式凌彬。
3. 如果n小于零，那么有零種找零方式循衰。

我們可以輕易將這個描述翻譯成遞歸函數(shù)：

>>> def count_change(a, kinds=(50, 25, 10, 5, 1)):
        """Return the number of ways to change amount a using coin kinds."""
        if a == 0:
            return 1
        if a < 0 or len(kinds) == 0:
            return 0
        d = kinds[0]
        return count_change(a, kinds[1:]) + count_change(a - d, kinds)
>>> count_change(100)
292

count_change函數(shù)生成樹形遞歸過程铲敛，和fib的首個實現(xiàn)一樣，它是重復(fù)的会钝。它會花費很長時間來計算出292伐蒋，除非我們記憶這個函數(shù)工三。另一方面，設(shè)計迭代算法來計算出結(jié)果的方式并不是那么明顯先鱼，我們將它留做一個挑戰(zhàn)俭正。

3.2.5 增長度

前面的例子表明，不同過程在花費的時間和空間計算資源上有顯著差異焙畔。我們用于描述這個差異的便捷方式掸读，就是使用增長度的概念，來獲得當(dāng)輸入變得更大時宏多，過程所需資源的大致度量儿惫。

令n為度量問題規(guī)模的參數(shù)，R(n)為處理規(guī)模為n的問題的過程所需的資源總數(shù)伸但。在我們前面的例子中肾请，我們將n看做給定函數(shù)所要計算出的數(shù)值。但是還有其他可能砌烁。例如筐喳，如果我們的目標(biāo)是計算某個數(shù)值的平方根近似值，我們會將n看做所需的有效位數(shù)的數(shù)量函喉。通常避归，有一些問題相關(guān)的特性可用于分析給定的過程。與之相似管呵，R(n)可用于度量所用的內(nèi)存總數(shù)梳毙，所執(zhí)行的基本的機器操作數(shù)量，以及其它捐下。在一次只執(zhí)行固定數(shù)量操作的計算中账锹，用于求解表達(dá)式的所需時間，與求值過程中執(zhí)行的基本機器操作數(shù)量成正比坷襟。

我們說奸柬，R(n)具有Θ(f(n))的增長度，寫作R(n)=Θ(f(n))（讀作“theta f(n)”）婴程，如果存在獨立于n的常數(shù)k1和k2廓奕，那么對于任何足夠大的n值：

k1·f(n) <= R(n) <= k2·f(n)

也就是說，對于較大的n档叔，R(n)的值夾在兩個具有f(n)規(guī)模的值之間：

• 下界k1·f(n)桌粉，以及
• 上界k2·f(n)。

例如衙四，計算n!所需的步驟數(shù)量與n成正比铃肯，所以這個過程的所需步驟以Θ(n)增長。我們也看到了，遞歸實現(xiàn)fact的所需空間以Θ(n)增長。與之相反，迭代實現(xiàn)fact_iter花費相似的步驟數(shù)量器仗，但是所需的空間保持不變宴胧。這里漱抓，我們說這個空間以Θ(1)增長表锻。

我們的樹形遞歸的斐波那契數(shù)計算函數(shù)fib的步驟數(shù)量恕齐，隨輸入n指數(shù)增長。尤其是瞬逊，我們可以發(fā)現(xiàn)显歧，第 n 個斐波那契數(shù)是距離φ^(n-2)/√5的最近整數(shù)，其中φ是黃金比例：

φ = (1 + √5)/2 ≈ 1.6180

我們也表示确镊，步驟數(shù)量隨返回值增長而增長士骤，所以樹形遞歸過程需要Θ(φ^n)的步驟，它的一個隨n指數(shù)增長的函數(shù)蕾域。

增長度只提供了過程行為的大致描述拷肌。例如，需要n^2個步驟的過程和需要1000·n^2個步驟的過程旨巷，以及需要3·n^2+10·n+17個步驟的過程都擁有Θ(n^2)的增長度巨缘。在特定的情況下，增長度的分析過于粗略采呐，不能在函數(shù)的兩個可能實現(xiàn)中做出判斷若锁。

但是，增長度提供了實用的方法斧吐，來表示在改變問題規(guī)模的時候又固，我們應(yīng)如何預(yù)期過程行為的改變。對于Θ(n)（線性）的過程煤率，使規(guī)模加倍只會使所需的資源總數(shù)加倍仰冠。對于指數(shù)的過程，每一點問題規(guī)模的增長都會使所用資源以固定因數(shù)翻倍蝶糯。接下來的例子展示了一個增長度為對數(shù)的算法洋只，所以使問題規(guī)模加倍，只會使所需資源以固定總數(shù)增加裳涛。

3.2.6 示例：求冪

考慮對給定數(shù)值求冪的問題木张。我們希望有一個函數(shù)，它接受底數(shù)b和正整數(shù)指數(shù)n作為參數(shù)端三，并計算出b^n舷礼。一種方式就是通過遞歸定義：

b^n = b·b^(n-1)
b^0 = 1

這可以翻譯成遞歸函數(shù)：

>>> def exp(b, n):
        if n == 0:
            return 1
        return b * exp(b, n-1)

這是個線性的遞歸過程，需要Θ(n)的步驟和空間郊闯。就像階乘那樣妻献，我們可以編寫等價的線性迭代形式蛛株，它需要相似的步驟數(shù)量，但只需要固定的空間育拨。

>>> def exp_iter(b, n):
        result = 1
        for _ in range(n):
            result = result * b
        return result

我們可以以更少的步驟求冪谨履，通過逐次平方。例如熬丧，我們這樣計算b^8：

b·(b·(b·(b·(b·(b·(b·b))))))

我們可以使用三次乘法來計算它：

b^2 = b·b
b^4 = b^2·b^2
b^8 = b^4·b^4

這個方法對于 2 的冪的指數(shù)工作良好笋粟。我們也可以使用這個遞歸規(guī)則，在求冪中利用逐步平方的優(yōu)點：

我們同樣可以將這個方式表達(dá)為遞歸函數(shù)：

>>> def square(x):
        return x*x
>>> def fast_exp(b, n):
        if n == 0:
            return 1
        if n % 2 == 0:
            return square(fast_exp(b, n//2))
        else:
            return b * fast_exp(b, n-1)
>>> fast_exp(2, 100)
1267650600228229401496703205376

fast_exp所生成的過程的空間和步驟數(shù)量隨n以對數(shù)方式增長析蝴。為了弄清楚它害捕，可以看出，使用fast_exp計算b^2n比計算b^n只需要一步額外的乘法操作闷畸。于是尝盼，我們能夠計算的指數(shù)大小，在每次新的乘法操作時都會（近似）加倍佑菩。所以盾沫，計算n的指數(shù)所需乘法操作的數(shù)量，增長得像以2為底n的對數(shù)那樣慢殿漠。這個過程擁有Θ(log n)的增長度赴精。Θ(log n)和Θ(n)之間的差異在n非常大時變得顯著。例如凸舵，n為1000時祖娘，fast_exp僅僅需要14個乘法操作，而不是1000啊奄。