遞歸與無窮大有關。我知道遞歸與無窮大有關。我想我知道遞歸與無窮大有關。他确信我認為我知道遞歸與無窮大有關。我們懷疑他是否确定我認為我知道......

我們認為，你認為，我們現在說服了你，我們可以永遠繼續這個自然語言遞歸的例子。遞歸不僅是自然語言的一個基本特征，也是人類認知能力的一個基本特征。我們的思維方式是基于遞歸的思維過程。即使使用非常簡單的語法規則，例如“英語句子包含主語和謂語，謂語包含動詞、賓語和補語”，我們也可以展示自然語言的無限可能。

認知科學家和語言學家斯蒂芬·平克 (Stephen Pinker) 是這樣描述的：“有幾千個名詞可以填滿主語，幾千個動詞可以填滿謂語，人們已經有幾百萬種打開句子的方式。可能的組合很快地乘以難以想象的大數。事實上，句子的全部内容在理論上是無限的，因為語言規則使用了一種叫做遞歸的技巧。

遞歸規則允許一個短語包含自身的一個例子，如她認為他認為他們認為他們認為他知道等等，無窮無盡。如果句子的數量是無限的，那麼可能的想法和意圖的數量也是無限的，因為實際上每個句子都表達了不同的想法或意圖。”1

我們必須停止在自然語言中使用遞歸的短途旅行，回到計算機科學和程序中的遞歸，最後回到編程語言 Python 中的遞歸。

形容詞“遞歸”源于拉丁語動詞“recurrere”，意思是“跑回去”。這就是遞歸定義或遞歸函數所做的：它在“跑回”或返回到自身。大多數學過數學、計算機科學或閱讀有關編程的書的人都會遇到階乘，它在數學術語中定義為

啊！= n * (n-1)!，如果 n > 1 且 0！= 1

由于其簡單明了，它經常被用作遞歸的示例。

遞歸是一種對問題進行編程或編碼的方法，其中函數在其主體中一次或多次調用自身。通常，它返回此函數調用的返回值。如果一個函數定義滿足遞歸條件，我們稱這個函數為遞歸函數。

終止條件：遞歸函數必須滿足一個重要的條件才能在程序中使用：它必須終止。如果每次遞歸調用問題的解決方案都縮小并朝着基本情況移動，則遞歸函數将終止。基本情況是指無需進一步遞歸即可解決問題的情況。如果調用中沒有滿足基本情況，遞歸可能會以無限循環結束。

例子：

4！= 4 * 3！ 3！= 3 * 2！ 2！= 2 * 1

替換計算值給了我們以下表達式

4！= 4 * 3 * 2 * 1

換句話說，計算機科學中的遞歸是一種解決問題的方法，它基于解決同一問題的較小實例。

現在我們來在 Python 中實現階乘。它就像數學定義一樣簡單而優雅。

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

我們可以通過在前面的函數定義中添加兩個 print() 函數來跟蹤該函數的工作方式：

def factorial ( n ): print ( "factorial has been called with n = " str ( n )) if n == 1 : return 1 else : res = n * factorial ( n - 1 ) print ( "intermediate result for " , n , " * factorial(" , n - 1 , "): " , res ) 返回 res 打印（階乘（5 ））

階乘已被調用，n = 5 階乘已被調用，n = 4 階乘已被調用，n = 3 階乘已被調用，n = 2 階乘已被調用，n = 1 2 * factorial( 1 ) 的中間結果：2 3 * factorial( 2 ) 的中間結果：6 4 * factorial( 3 ) 的中間結果：24 5 * factorial( 4 ) 的中間結果：120 120

讓我們看一下階乘函數的疊代版本。

def iterative_factorial ( n ): result = 1 for i in range ( 2 , n 1 ): result *= i return result 對于 我 在 範圍（5 ）： 打印（我， iterative_factorial （我））

0 1 1 1 2 2 3 6 4 24

通常的做法是将 0 的階乘函數擴展為參數。定義0!為 是有道理的1，因為隻有零個對象的一個​​排列，即如果沒有什麼要排列，“一切”就留在原地。另一個原因是在一組 n 中選擇 n 個元素的方法的數量計算為 n！除以 n! 的乘積！和0！。

為了實現這一點，我們所要做的就是改變 if 語句的條件：

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

我們關于遞歸的論文現在将我們引向另一個有趣的遞歸案例。

向日葵、黃金比例、枞樹球果、達芬奇密碼、Tool 的歌曲“Lateralus”和右側的圖形有什麼共同點？對，斐波那契數列。我們不介紹斐波那契數列，因為它們是遞歸函數的另一個有用示例。嘗試為這個數字序列編寫遞歸函數可能會導緻程序效率低下。事實上，如此低效以至于它不會有用。我們介紹斐波那契數列是為了向您展示遞歸的陷阱。

斐波那契數是以下整數值序列的數字：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

斐波那契數列定義為：

Fn=Fn- Fn-2

F0=0 和 F1=1F0=0 和 F1=1

斐波那契數列以比薩的數學家列奧納多 (Leonardo of Pisa) 的名字命名，他更為人所知的是斐波那契。在他的書“Liber Abaci”（出版于 1202 年）中，他介紹了這個序列作為處理兔子的練習。他的斐波那契數列從 F1 = 1 開始，而在現代數學中，該序列從 F0 = 0 開始。但這對序列的其他成員沒有影響。

斐波那契數是人工兔子種群的結果，滿足以下條件：

• 一對剛出生的兔子，一公一母，建立初始種群
• 這些兔子可以在一個月大的時候交配，這樣在第二個月末，雌性就可以生育另一對兔子
• 這些兔子是不朽的
• 從第二個月開始，一對交配的一對總是每個月産生一對新的（一男一女）

斐波那契數是n幾個月後兔子對的數量，即 10 個月後我們将擁有 F10 兔子。F10兔子。

斐波那契數列很容易寫成 Python 函數。它或多或少是數學定義中的一對一映射：

def fib ( n ): if n == 0 : return 0 elif n == 1 : return 1 else : return fib ( n - 1 ) fib ( n - 2 )

疊代解決方案也很容易編寫，盡管遞歸解決方案看起來更像定義：

def fibi ( n ): old , new = 0 , 1 if n == 0 : return 0 for i in range ( n - 1 ): old , new = new , old new return new

我們将編寫一個名稱fibonacci包含函數fib和fibi. 為此，您必須将以下代碼複制到名為 fibonacci0.py 的文件中：

""" 包含斐波那契函數的遞歸和疊代實現的 模塊。該模塊的目的在于展示斐波那契函數的純遞歸實現的低效率！""" def fib ( n ): """ 斐波那契函數的遞歸版本 """ if n == 0 : return 0 elif n == 1 : return 1 else : return fib ( n - 1 ) fib ( n - 2 ) def fibi ( n ): """ 斐波那契函數的疊代版本 """ old , new = 0 , 1 if n == 0 : return 0 for i in range ( n - 1 ): old , new = new , old 新 返回 新

覆蓋 fibonacci0.py

如果您檢查函數 fib() 和 fibi()，您會發現疊代版本 fibi() 比遞歸版本 fib() 快很多。為了了解這“快得多”可以達到多少，我們編寫了一個腳本，它使用 timeit 模塊來測量調用。為此，我們将 fib 和 fibi 的函數定義保存在文件 fibonacci.py 中，我們可以在下面的程序 (fibonacci_runit.py) 中導入該文件：

從 timeit 導入 計時器 t1 = Timer ( "fib(10)" , "from fibonacci import fib" ) 對于 我 在 範圍（1 ， 20 ）： CMD = “FIB（” STR （我） “）” T1 = 定時器（CMD ， “從進口斐波納契FIB” ） TIME1 = T1 。timeit ( 3 ) cmd = "fibi(" str ( i ) ")" t2 = Timer ( cmd , "from fibonacci import fibi" ) 時間 2 = t2 。timeit ( 3 ) 打印( f "n= { i : 2d } , fib: { time1 : 8.6f } , fibi: { time2 : 7.6f } , time1/time2: { time1 / time2 : 10.2f } " )

n= 1, fib: 0.000001, fibi: 0.000002, time1/time2: 0.50 n= 2, fib: 0.000002, fibi: 0.000002, time1/time2: 0.85 n= 3, fib: 0.000003, fibi: 0.000002, time1/time2: 1.11 n= 4, fib: 0.000004, fibi: 0.000003, time1/time2: 1.45 n= 5, fib: 0.000011, fibi: 0.000003, time1/time2: 3.35 n= 6, fib: 0.000008, fibi: 0.000003, time1/time2: 2.98 n= 7, fib: 0.000012, fibi: 0.000002, time1/time2: 5.05 n= 8, fib: 0.000018, fibi: 0.000002, time1/time2: 7.98 n= 9, fib: 0.000029, fibi: 0.000002, time1/time2: 12.15 n=10, fib: 0.000046, fibi: 0.000003, time1/time2: 18.18 n=11, fib: 0.000075, fibi: 0.000003, time1/time2: 28.42 n=12, fib: 0.000153, fibi: 0.000003, time1/time2: 51.99 n=13, fib: 0.000194, fibi: 0.000003, time1/time2: 72.11 n=14, fib: 0.000323, fibi: 0.000003, time1/time2: 109.50 n=15, fib: 0.001015, fibi: 0.000008, time1/time2: 134.65 n=16, fib: 0.002165, fibi: 0.000008, time1/time2: 261.11 n=17, fib: 0.003795, fibi: 0.000019, time1/time2: 198.87 n=18, fib: 0.006021, fibi: 0.000010, time1/time2: 574.59 n=19, fib: 0.008807, fibi: 0.000011, time1/time2: 785.54

time1是 3 次調用所需的時間（以秒為單位）fib(n)，time2分别是fibi(n).

我們的遞歸實現有什麼問題？

讓我們來看看計算樹，即調用函數的順序。fib() 被 f() 代替。

我們可以看到子樹 f(2) 出現了 3 次，而用于計算 f(3) 的子樹出現了兩次。如果你想象為 f(6) 擴展這棵樹，你就會明白 f(4) 将被調用兩次，f(3) 被調用三次，依此類推。這意味着，我們的遞歸不會記住先前計算的值。

我們可以通過使用字典來保存先前計算的值，為我們的遞歸版本實現“内存”。我們稱這個版本為fibm：

備忘錄 = { 0 ：0 ， 1 ：1 } DEF fibm （Ñ ）： 如果 不 Ñ 在 備忘錄： 備忘錄[ Ñ ] = fibm （ñ - 1 ） fibm （ñ - 2 ） 返回 備忘錄[ Ñ ]

在我們對新版本做一些計時之前，我們将它添加到我們的fibonacci模塊中：

""" 包含斐波那契函數的遞歸和疊代實現的 模塊。該模塊的目的在于展示斐波那契函數的純遞歸實現的低效率！""" def fib ( n ): """ 斐波那契函數的遞歸版本 """ if n == 0 : return 0 elif n == 1 : return 1 else : return fib ( n - 1 ) fib ( n - 2 ) def fibi ( n ): """ 斐波那契函數的疊代版本 """ old , new = 0 , 1 if n == 0 : return 0 for i in range ( n - 1 ): old , new = new , old 新 返回 新 memo = { 0 : 0 , 1 : 1 } def fibm ( n ): """ 遞歸斐波那契函數，它 在字典 memo 的幫助下 記憶先前計算的值 """如果 在memo 中不是 n : memo [ n ] = fibm ( n - 1 ) fibm ( n - 2 )返回備忘錄[ n ]

覆蓋 fibonacci.py

我們再次計時以将其與 fibi() 進行比較：

from timeit import Timer from fibonacci import fib t1 = Timer ( "fib(10)" , "from fibonacci import fib" ) 對于 我 在 範圍（1 ， 20 ）： 小号 = “fibm（” STR （我） “）” T1 = 定時器（小号，“從進口斐波納契fibm” ） TIME1 = T1 。timeit ( 3 ) s = "fibi(" str ( i ) ")" t2 = Timer ( s , "from fibonacci import fibi" ) 時間 2 = t2 。timeit ( 3 ) 打印( f "n= { i : 2d } , fibm: { time1 : 8.6f } , fibi: { time2 : 7.6f } , time1/time2: { time1 / time2 : 10.2f } " )

n= 1, fibm: 0.000002, fibi: 0.000002, time1/time2: 0.68 n= 2, fibm: 0.000001, fibi: 0.000002, time1/time2: 0.63 n= 3, fibm: 0.000001, fibi: 0.000002, time1/time2: 0.51 n= 4, fibm: 0.000001, fibi: 0.000002, time1/time2: 0.46 n= 5, fibm: 0.000001, fibi: 0.000002, time1/time2: 0.48 n= 6, fibm: 0.000001, fibi: 0.000002, time1/time2: 0.41 n= 7, fibm: 0.000001, fibi: 0.000002, time1/time2: 0.41 n= 8, fibm: 0.000001, fibi: 0.000011, time1/time2: 0.10 n= 9, fibm: 0.000001, fibi: 0.000002, time1/time2: 0.40 n=10, fibm: 0.000001, fibi: 0.000002, time1/time2: 0.36 n=11, fibm: 0.000001, fibi: 0.000003, time1/time2: 0.38 n=12, fibm: 0.000001, fibi: 0.000003, time1/time2: 0.35 n=13, fibm: 0.000001, fibi: 0.000003, time1/time2: 0.44 n=14, fibm: 0.000001, fibi: 0.000003, time1/time2: 0.36 n=15, fibm: 0.000001, fibi: 0.000003, time1/time2: 0.35 n=16, fibm: 0.000001, fibi: 0.000004, time1/time2: 0.34 n=17, fibm: 0.000001, fibi: 0.000003, time1/time2: 0.33 n=18, fibm: 0.000001, fibi: 0.000004, time1/time2: 0.29 n=19, fibm: 0.000001, fibi: 0.000004, time1/time2: 0.27

我們可以看到它甚至比疊代版本還要快。當然，論點越大，我們記憶的好處就越大：

我們還可以通過使用具有 callabe 實例的類，即使用特殊方法call為我們的 Fibonacci 函數定義遞歸算法。這樣，我們将能夠以優雅的方式隐藏字典。我們使用了一種通用方法，它允許定義類似于 Fibonacci 的函數，如 Lucas 函數。這意味着我們可以通過實例化此類的實例來創建類似斐波那契數列的數字序列。基本上，構建原理，即前兩個數字的總和，将是相同的。它們将因兩個初始值而異：

FibonacciLike類： def __init__ ( self , i1 = 0 , i2 = 1 ): self 。備忘錄 = { 0 : i1 , 1 : i2 } 高清 __call__ （自我， ñ ）： 如果 ñ 不是 在 自我。備忘錄： 自我。備忘錄[ n ] = 自我。__call__ ( n - 1 ) self 。__call__ ( n - 2 ) 返回 self 。備忘錄[ n ] # 我們創建一個可調用對象來創建斐波那契數列： fib = FibonacciLike () # 這将創建一個可調用對象來創建 Lucas 數列： lucas = FibonacciLike ( 2 , 1 ) 對于 我 在 範圍（1 ， 16 ）： 打印（我， FIB （我）， 盧卡斯（我））

1 1 1 2 1 3 3 2 4 4 3 7 5 5 11 6 8 18 7 13 29 8 21 47 9 34 76 10 55 123 11 89 199 12 144 322 13 233 521 14 377 843 15 610 1364

盧卡斯數或盧卡斯級數是一個整數序列，以數學家弗朗索瓦·愛德華·阿納托爾·盧卡斯 (1842-91) 的名字命名，他研究了該序列和密切相關的斐波那契數。盧卡斯數與斐波那契數有相同的創生法則，即前兩個數之和，但0和1的取值不同。

現在我們将證明我們的方法也适用于計算任意廣義斐波那契數列。斐波那契數列取決于前面的兩個值。我們現在通過以下方式定義 k-Fib 序列來概括這個概念

給定一個固定的自然數k和k >= 2。還給出了k初始值一世0,一世1,…一世克-1

滿意 F克(0)=一世0,…F克(克-1)=一世克-1

該功能還需要 克 系數 C0,C1,…C克-1

F克(n) 被定義為

F克(n)=一個0⋅F克(n-1) 一個1⋅F克(n-2)…一個克-1⋅F克(n-克)

和 克<=n

kFibonacci類： def __init__ ( self , k , initials , coefficients ): self . memo = dict ( zip ( range ( k ), initials )) self . coeffs = 系數 self 。k = k def __call__ ( self , n ): k = self 。ķ 如果 ñ 不是 在 自我。備忘錄： 結果 = 0 為 系數_ ， 我 在 拉鍊（自我。coeffs ， 範圍（1 ， ķ 1 ））： 結果 = 系數_ * 自我。__call__ ( n - i ) self. 備注[ n ] = 結果 返回 self 。備忘錄[ n ] fib = kFibonacci ( 2 , ( 0 , 1 ), ( 1 , 1 )) lucas = kFibonacci ( 2 , ( 2 , 1 ), ( 1 , 1 )) 對于 我 在 範圍（1 ， 16 ）： 打印（我， FIB （我）， 盧卡斯（我））

1 1 1 2 1 3 3 2 4 4 3 7 5 5 11 6 8 18 7 13 29 8 21 47 9 34 76 10 55 123 11 89 199 12 144 322 13 233 521 14 377 843 15 610 1364

Pell 數字的序列以 1, 2, 5, 12, 29, ...

功能是

磷(n)=2⋅磷(n-1) 磷(n-2) 和 磷(0)=1 和 磷(1)=1

用我們的kFibonacci類很容易制定這個序列：

P = kFibonacci （2 ， （1 ， 2 ）， （2 ， 1 ）） 為 我 在 範圍（10 ): print ( i , P ( i ))

0 1 1 2 2 5 3 12 4 29 5 70 6 169 7 408 8 985 9 2378

我們可以通過在兩個佩爾數 P(i) 和 P(i 1) 之間添加前兩個佩爾數之和來創建另一個有趣的系列。我們得到：

磷(0),磷(1),磷(0) 磷(1),磷(2),磷(1) 磷(2),磷(3),磷(2) 磷(3),…

對應于： 1,2,3,5,7,12,17,29,…

def nP ( n ): 如果 n < 2 : return P ( n ) else : i = n // 2 1 if n % 2 : # n 是奇數 return P ( i ) else : return P ( i - 1 ) P ( i - 2 ) 對于 我 在 範圍（20 ）： 打印（為nP （我）， 結束= “” ）

1, 2, 3, 5, 7, 12, 17, 29, 41, 70, 99, 169, 239, 408, 577, 985, 1393, 2378, 3363, 5741,

如果你仔細觀察這些數字，你會發現在這個序列中還有另一個規則。我們可以将 nP 定義為

n磷(n)=2⋅n磷(n-2) n磷(n-4) 和 n>3 和起始值 1,2,3,5

這是我們kFibonacci班級的另一個簡單應用：

nP = kFibonacci ( 4 , ( 1 , 2 , 3 , 5 ), ( 0 , 2 , 0 , 1 )) for i in range ( 20 ): print ( nP ( i ), end = ", " )

1, 2, 3, 5, 7, 12, 17, 29, 41, 70, 99, 169, 239, 408, 577, 985, 1393, 2378, 3363, 5741,

一個有趣的數學事實：對于每個奇數 n 的商 磷(n) 經過 磷(n-1) 是一個近似值 2. 如果n是偶數，商是一個近似值1 12

sqrt2 = 2 ** 0.5 print ( "2的平方根：" , sqrt2 ) print ( "3的平方根:" , 1 1 / sqrt2 ) for i in range ( 1 , 20 ): print ( nP ( i ) / nP ( i - 1 ), end = ", " )

2 的平方根：1.4142135623730951 3 的平方根：1.7071067811865475 2.0，1.5，1.6666666666666667，1.4，1.7142857142857142，1.4166666666666667，1.7058823529411764，1.4137931034482758，1.7073170731707317，1.4142857142857144，1.707070707070707，1.4142011834319526，1.707112970711297，1.4142156862745099，1.707105719237435，1.4142131979695431，1.7071069633883704，1.4142136248948696，1.7071067499256616，

如果您想了解更多關于遞歸的知識，我們建議您嘗試解決以下練習。在你盡力而為之前，請不要盯着解決方案。如果您已經考慮了一段時間的任務，但仍然無法解決該練習，您可以參考我們的示例解決方案。

在我們教程的“高級主題”部分，我們對遊戲或謎題“河内之塔”進行了全面的處理。當然，我們通過使用遞歸函數的函數來解決它。“河内問題”很特别，因為遞歸解決方案幾乎将自己強加于程序員，而遊戲的疊代解決方案很難找到和掌握。

想想函數 f(n) = 3 * n 的遞歸版本，即 3 的倍數

編寫一個遞歸 Python 函數，返回前 n 個整數的總和。（提示：該函數将類似于階乘函數！）

編寫一個實現帕斯卡三角形的函數：

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1

斐波那契數列隐藏在帕斯卡三角形内。如果您将以下三角形的彩色數字相加，您将得到第 7 個斐波那契數：

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1

使用帕斯卡三角形編寫一個遞歸程序來計算斐波那契數列。

在 Python 中為 Eratosthenes 的篩子實現遞歸函數。

Eratosthenes 篩法是一種簡單的算法，用于查找指定整數以内的所有素數。它是由古希臘數學家埃拉托色尼創造的。求所有小于或等于給定整數n的素數的算法：

1. 創建一個從 2 到 n 的整數列表：2, 3, 4, ..., n
2. 從我設置為 2 的計數器開始，即第一個質數
3. 從 i i 開始，按 i 遞增并從列表中删除這些數字，即 2 i、3 i、4*i 等。
4. 找出 i 後面的列表的第一個數字。這是下一個質數。
5. 将 i 設置為在上一步中找到的數字
6. 重複步驟 3 和 4，直到 i 大于 n。（作為改進：去n的平方根就夠了）
7. 所有仍在列表中的數字都是素數

你可以很容易地看到，如果我們嚴格使用這個算法，我們将是低效的，例如，我們将嘗試去除 4 的倍數，盡管它們已經被 2 的倍數去除了。所以它足以産生所有的倍數直到 n 的平方根的素數。我們可以遞歸地創建這些集合。

寫一個遞歸函數fib_indexfib()，返回斐波那契數列中某個數的索引，如果該數是該數列的元素，則返回-1，如果不包含該數，即

F一世乙(F一世乙_一世nd電子X(n))==n

兩個連續斐波那契數的平方和也是斐波那契數，例如2和3是斐波那契數列的元素，2 2 3 3 = 13對應斐波那契(7)。 用前面的函數求位置斐波那契數列中兩個連續數的平方和。

數學解釋：設 a 和 b 是兩個連續的斐波那契數，a 先于 b。以數字“a”開頭的斐波那契數列如下所示：

0個 1個 2 a b 3 a 2b 4 2a 3b 5 3a 5b 6 5a 8b

我們可以看到斐波那契數列作為 a 和 b 的因子出現。此序列中的第 n 個元素可以使用以下公式計算：

F(n)=F一世乙(n-1)⋅一個 F一世乙(n)⋅乙

由此我們可以得出結論，對于自然數 n，n>1，以下成立：

F一世乙(2⋅n 1)=F一世乙(n)2 F一世乙(n 1)2

的tribonacci号碼是像斐波那契數，但不是與兩個預定條件開始，該序列與三個預定術語開始的，每個術語之後是前述三項的總和。前幾個 tribonacci 數是：

0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 356812, ...

所述tetranacci号碼與四個預定術語開始，每個術語之後是前述4項的總和。前幾個四連數是：

0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, ...

對于pentanacci、hexanacci、heptanacci、octanacci 等，這以相同的方式繼續。

為 tribonacci 和tetranacci 數編寫函數。

如果有人想檢查遞歸函數中的參數怎麼辦？例如階乘函數。好的，請編寫一個遞歸版本的 factorial 來檢查參數。也許你以完美的方式做到了，但也許不是。你能改進你的版本嗎？擺脫不必要的測試？

在數學上，我們可以這樣寫：

F(1)=3,

F(n 1)=F(n) 3

一個 Python 函數可以這樣寫：

def mult3 ( n ): 如果 n == 1 : return 3 else : return mult3 ( n - 1 ) 3 對于 我 在 範圍（1 ，10 ）： 打印（mult3 （我））

3 6 9 12 15 18 21 24 27

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

def pascal ( n ): if n == 1 : return [ 1 ] else : line = [ 1 ] previous_line = pascal ( n - 1 ) for i in range ( len ( previous_line ) - 1 ): line 。追加（previous_line [ i ] previous_line [ i 1 ]) 行 = [ 1 ] 返回 行 打印（帕斯卡（6 ））

[1, 5, 10, 10, 5, 1]

或者，我們可以使用列表推導編寫一個函數：

def pascal ( n ): if n == 1 : return [ 1 ] else : p_line = pascal ( n - 1 ) line = [ p_line [ i ] p_line [ i 1 ] for i in range ( len ( p_line ) - 1 )] 行。插入( 0 , 1） 線。追加( 1 ) 返回 行 打印（帕斯卡（6 ））

[1, 5, 10, 10, 5, 1]

從帕斯卡三角形中産生斐波那契數列：

def fib_pascal ( n , fib_pos ): if n == 1 : line = [ 1 ] fib_sum = 1 if fib_pos == 0 else 0 else : line = [ 1 ] ( previous_line , fib_sum ) = fib_pascal ( n - 1 , fib_pos 1 ） 用于 我 在 範圍（len個（ previous_line ) - 1 ): 行。append ( previous_line [ i ] previous_line [ i 1 ]) line = [ 1 ] if fib_pos < len ( line ): fib_sum = line [ fib_pos ] return ( line , fib_sum ) def fib ( n ): 返回 fib_pascal ( n , 0 )[ 1 ] # 現在打印出前十個斐波那契數： for i in range ( 1 , 10 ): print ( fib ( i ))

1 1 2 3 5 8 13 21 34

下面的程序按照任務的規則以疊代的方式實現了埃拉托色尼篩法。它将打印出前 100 個質數。

from math import sqrt def screen ( n ): # 返回 2 和 n 之間的所有素 數 = list ( range ( 2 , n 1 )) max = sqrt ( n ) num = 2 while num < max : i = num while i <= n : i = num if i in primes : primes .删除( i ) for j in primes : if j > num : num = j break return primes 打印（篩（100 ））

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 ]

但是我們教程的這一章是關于遞歸和遞歸函數的，我們需要一個遞歸函數來計算素數。要理解以下解決方案，您可以參考我們關于列表理解的章節：

從 數學 導入 sqrt def primes ( n ): if n == 0 : return [] elif n == 1 : return [] else : p = primes ( int ( sqrt ( n ))) no_p = [ j for i in p for j in range ( i * 2 , n 1 , i )] p = x [ 為 X 在 範圍（2 ， Ñ 1 ） 如果 X 不 在 no_p ] 返回 p 打印（素數（100 ））

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 ]

備忘錄 = { 0 ：0 ， 1 ：1 } DEF FIB （Ñ ）： 如果 不 Ñ 在 備忘錄： 備忘錄[ Ñ ] = FIB （ñ - 1 ） FIB （ñ - 2 ） 返回 備忘錄[ Ñ ] def fib_index ( * x ): """ 用 fib(i) == n """ 查找自然數 i if len ( x ) == 1 : # 由用戶開始 # 查找從 0 開始的索引return fib_index ( x [ 0 ], 0 ) else : n = fib ( x [ 1 ]) m = x [ 0 ] 如果 n > m : return - 1 elif n == m : return x [ 1 ] else : return fib_index ( m , x [ 1 ] 1 ) # 上一示例中帶有 fib() 和 find_index() 函數的代碼 print ( " a | a | b | 平方和 | 索引" 的索引" ) print ( "============================== ========================” ） 為 我 在 範圍（15 ）： 方形 = FIB （我）** 2 FIB （我 1 ）** 2 打印( f " { i : 12d } | { fib ( i ) : 6d } |{fib ( i 1 ) : 9d } | {正方形：14d } | { fib_index ( square ) : 5d } " )

索引 | 一個| 乙 | 平方和 | 指數 ================================================== === 0| 0| 1| 1| 1 1| 1| 1| 2| 3 2| 1| 2| 5| 5 3| 2| 3| 13| 7 4| 3| 5| 34| 9 5| 5| 8| 89| 11 6| 8| 13| 233| 13 7| 13| 21| 610| 15 8| 21| 34| 1597| 17 9| 34| 55| 4181| 19 10| 55| 89| 10946| 21 11| 89| 144| 28657| 23 12| 144| 233| 75025| 25 13| 233| 377| 196418| 27 14| 377| 610| 514229| 29

我們将使用kFibonacci我們在本章中定義的類。

tribonacci = kFibonacci ( 3 , ( 0 , 0 , 1 ), ( 1 , 1 , 1 )) 對于 我 在 範圍（20 ）： 打印（tribonacci （我）， 結束= “” ）

0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513,

四面體 = kFibonacci ( 4 , ( 0 , 0 , 0 , 1 ), ( 1 , 1 , 1 , 1 )) 對于 我 在 範圍（20 ）： 打印（tetranacci （我）， 結束= “” ）

0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569,

我們可以像這樣輕松地創建它們：

前綴 = [ '摩擦' ， '四' ， '的Pentra' ， '六' ， '庚' ， '八' ] 為 ķ ， 前綴 在 拉鍊（範圍（len個（前綴））， 前綴）： CMD = 前綴 “ nacci = kFibonacci(" cmd = str ( k 3 ) ", (" "0, " * ( k 2 ) "1), " cmd = "(" "1, " * ( k 2 ) "1))" 打印( cmd ) exec ( cmd ) 打印( " \n測試八角函數：" ) for i in range ( 20 ): 打印(八角( i ), end = ", " )

tribonacci = kFibonacci(3, (0, 0, 1), (1, 1, 1)) 四面體 = kFibonacci(4, (0, 0, 0, 1), (1, 1, 1, 1)) pentranacci = kFibonacci(5,​​ (0, 0, 0, 0, 1), (1, 1, 1, 1, 1)) 六面體 = kFibonacci(6, (0, 0, 0, 0, 0, 1), (1, 1, 1, 1, 1, 1)) heptanacci = kFibonacci(7, (0, 0, 0, 0, 0, 0, 1), (1, 1, 1, 1, 1, 1, 1)) Octanacci = kFibonacci(8, (0, 0, 0, 0, 0, 0, 0, 1), (1, 1, 1, 1, 1, 1, 1, 1)) 測試八角函數： 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028,

def factorial ( n ): """ 計算 n 的階乘， n 應該是一個整數并且 n <= 0 """ if type ( n ) == int and n >= 0 : if n == 0 : return 1 否則： 返回 n * 階乘( n - 1 ) 其他： 加薪 類型錯誤（“N必須是一個正整數或零” ）

你怎麼看這個解決方案？factorial(10)例如你打電話。該函數将檢查是否10為正整數。該函數将遞歸調用factorial(9). 在此調用中，函數将再次檢查是否9為整數。還能是什麼？第一次調用已檢查10所有我們所做的就是減去1從10。

我們可以通過定義一個内部函數來解決這個問題：

def factorial ( n ): """ 計算 n 的階乘， n 應該是一個整數并且 n <= 0 """ def inner_factorial ( n ): if n == 0 : return 1 else : return n * inner_factorial ( n - 1 ) 如果 類型( n ) == int 并且 n >= 0 ： 返回 inner_factorial ( n ) else ： 加注 類型錯誤（“n應為positve int或0” ） 打印（階乘（10 ））

3628800

測試隻會在第一次調用時執行10！

*斯蒂芬平克，空白石闆，2002