瞭解遞歸函數

Question

我正在通過本書介紹NLP與Python，並且我從「高級」部分中看到了這個示例。我很感激幫助理解它是如何工作的。該函數計算一系列音節的所有可能性，以達到「米」長度n。短音節「S」佔據一個單位長度，而長音節「L」佔據兩個單位長度。因此，對於每米長度的4，return語句是這樣的：

['SSSS', 'SSL', 'SLS', 'LSS', 'LL'] 

功能：

def virahanka1(n): 
    if n == 0: 
     return [""] 
    elif n == 1: 
     return ["S"] 
    else: 
     s = ["S" + prosody for prosody in virahanka1(n-1)] 
     l = ["L" + prosody for prosody in virahanka1(n-2)] 
     return s + l 

我不明白的部分是如何 'SSL'， 'SLS' ，如果s和l是單獨的列表，則進行'LSS'匹配。在「virahanka1（n-1）中的韻律」中，「什麼是韻律？函數每次返回是什麼？我試圖一步一步地思考，但我沒有得到任何地方。在此先感謝您的幫助！

阿德里安

Answer 1

此功能說：

virakhanka1(n)相同[""]當n是零，當["S"]n爲1，且否則s + l。 其中s與結果列表virahanka1(n - 1)中的每個元素前面的"S"相同，並且l與virahanka1(n - 2)的元素前面的"L"相同。

所以計算將是：

When n is 0: 
    [""] 
When n is 1: 
    ["S"] 
When n is 2: 
    s = ["S" + "S"] 
    l = ["L" + ""] 
    s + l = ["SS", "L"] 
When n is 3: 
    s = ["S" + "SS", "S" + "L"] 
    l = ["L" + "S"] 
    s + l = ["SSS", "SL", "LS"] 
When n is 4: 
    s = ["S" + "SSS", "S" + "SL", "S" + "LS"] 
    l = ["L" + "SS", "L" + "L"] 
    s + l = ['SSSS", "SSL", "SLS", "LSS", "LL"] 

有你有它，一步一步來。

爲了計算最終的值，你需要知道其他函數調用的結果，如你所見，這可能會非常麻煩。重要的是你不要試圖在你的腦海中遞歸地思考。這會讓你的思想融化。我用文字描述了功能，以便您可以看到這些功能是是描述，而不是一系列命令。

您看到的prosody，這是s和l定義的一部分，是變量。它們用於列表理解，這是一種建立列表的方式。我之前已經描述過這個列表是如何構建的。

Answer 2

讓我們從零開始構建函數。這是徹底理解它的好方法。

假設那麼我們需要一個遞歸函數來列舉Ls和Ss的每個組合以使給定的米長度爲n。讓我們考慮一些簡單的情況：

• n = 0：唯一的方法是用空字符串。
• n = 1：唯一的辦法是用單個S.
• n = 2：您可以用一個L或兩個S做到這一點。
• n = 3：LS，SL，SSS。

現在，考慮上述數據，請考慮如何爲n = 4建立答案。那麼，答案要麼包括在米長度爲3時加S，要麼在米長度爲2時加L。所以，這種情況下的答案將是n = 2時的LL, LSS和從n = 3開始的SLS, SSL, SSSS。你可以檢查這是所有可能的組合。我們也可以看到n = 2和n = 3可以從n = 0,1和n = 1,2得到，所以我們不需要特殊說明。

一般，那麼，對於n ≥ 2，您可以通過查看長度n-1和長度n-2的字符串導出長度n字符串。

然後，答案是顯而易見的：

• 如果n = 0，僅返回一個空字符串
• 如果n = 1，返回一個單獨的S
• 否則，返回添加的結果S到儀表長度爲n-1的所有字符串，並結合對所有長度爲n-2的字符串添加L得到的結果。

順便說一句，寫入的函數有點低效，因爲它重新計算了很多值。如果你要求例如這樣會很慢。 n = 30。您可以通過使用在Python 3.3的新lru_cache讓它更快一點很容易：

@lru_cache(maxsize=None) 
def virahanka1(n): 
    ... 

每個n這個緩存的結果，使得它更快。

Answer 3

我試圖融化我的大腦。我添加了打印語句來向我解釋發生了什麼事。我認爲關於遞歸調用最令人困惑的部分是，它似乎進入了調用中，但是出現了反向，正如您在運行以下代碼時可能會看到的那樣;

def virahanka1(n): 
    if n == 4: 
      print 'Lets Begin for ', n 
    else: 
      print 'recursive call for ', n, '\n' 
    if n == 0: 
     print 'n = 0 so adding "" to below' 
     return [""] 
    elif n == 1: 
     print 'n = 1 so returning S for below' 
     return ["S"] 
    else: 
     print 'next recursivly call ' + str(n) + '-1 for S' 
     s = ["S" + prosody for prosody in virahanka1(n-1)] 
     print '"S" + each string in s equals', s 
     if n == 4: 
      print '**Above is the result for s**' 
     print 'n =',n,'\n', 'next recursivly call ' + str(n) + '-2 for L' 
     l = ["L" + prosody for prosody in virahanka1(n-2)] 
     print '\t','what was returned + each string in l now equals', l 
     if n == 4: 
      print '**Above is the result for l**','\n','**Below is the end result of s + l**' 
     print 'returning s + l',s+l,'for below', '\n','='*70 
     return s + l 
virahanka1(4) 

仍撲朔迷離，對我來說這個和Jocke典雅的解釋，我想我可以理解是怎麼回事。

你呢？

下面是上面產生的代碼;

Lets Begin for 4 
next recursivly call 4-1 for S 
recursive call for 3 

next recursivly call 3-1 for S 
recursive call for 2 

next recursivly call 2-1 for S 
recursive call for 1 

n = 1 so returning S for below 
"S" + each string in s equals ['SS'] 
n = 2 
next recursivly call 2-2 for L 
recursive call for 0 

n = 0 so adding "" to below 
     what was returned + each string in l now equals ['L'] 
returning s + l ['SS', 'L'] for below 
====================================================================== 
"S" + each string in s equals ['SSS', 'SL'] 
n = 3 
next recursivly call 3-2 for L 
recursive call for 1 

n = 1 so returning S for below 
     what was returned + each string in l now equals ['LS'] 
returning s + l ['SSS', 'SL', 'LS'] for below 
====================================================================== 
"S" + each string in s equals ['SSSS', 'SSL', 'SLS'] 
**Above is the result for s** 
n = 4 
next recursivly call 4-2 for L 
recursive call for 2 

next recursivly call 2-1 for S 
recursive call for 1 

n = 1 so returning S for below 
"S" + each string in s equals ['SS'] 
n = 2 
next recursivly call 2-2 for L 
recursive call for 0 

n = 0 so adding "" to below 
     what was returned + each string in l now equals ['L'] 
returning s + l ['SS', 'L'] for below 
====================================================================== 
     what was returned + each string in l now equals ['LSS', 'LL'] 
**Above is the result for l** 
**Below is the end result of s + l** 
returning s + l ['SSSS', 'SSL', 'SLS', 'LSS', 'LL'] for below 
======================================================================