Coverting遞歸函數的尾遞歸一個在Python

作爲練習，我實現了使用遞歸的地圖功能在python如下：Coverting遞歸函數的尾遞歸一個在Python

#map function that applies the function f on every element of list l and returns the new list 
def map(l,f): 
    if l == []: 
     return [] 
    else: 
     return [f(l[0])] + map(l[1:],f)

我知道的事實，Python不支持尾遞歸優化，但我將如何去寫尾部遞歸方式相同的功能？

請幫助謝謝

來源

2011-08-08 Joe

爲什麼這個函數不是尾遞歸？ –

它不是因爲映射不是最後一個操作，映射的結果被添加到[f（l [0]）]，所以遞歸過程中的每個堆棧幀將需要 – Joe

好吧，所以你遞歸地生成元素，然後合併他們到一個列表。迭代過程會在每一步中更新列表的狀態，並將其傳遞給下一次迭代，對吧？你需要更多的幫助嗎？ –

這將是內置函數圖中尾遞歸執行的例子：

def map(func, ls, res=None): 
    if res is None: 
     res = [] 
    if not ls: 
     return res 
    res.append(func(ls[0])) 
    return map(func, ls[1:], res)

但它不會解決沒有蟒蛇的問題支持TRE，這意味着每個函數調用的調用堆棧始終保持不變。

來源

2011-08-08 01:28:58 mouad

這似乎是尾遞歸：

def map(l,f,x=[]): 
    if l == []: 
     return x 
    else: 
     return map(l[1:],f,x+[f(l[0])])

或在更緊湊的形式：

def map(l,f,x=[]): 
    return l and map(l[1:],f,x+[f(l[0])]) or x

來源

2011-08-08 01:29:23

使用一個可變的默認參數是不明智的想做：http：///stackoverflow.com/questions/1132941/least-astonishment-in-python-the-mutable-default-argument – mouad

@mouand，我知道這個功能。如果以正確的方式使用該功能，它不會導致任何錯誤。 –

除非你調用'my_list = map（empty_list，some_func）; my_list.append（5）'。現在每一個更多的空列表都將被映射到[5]。 – Ben

尾遞歸意味着你必須直接返回遞歸調用的結果，沒有進一步的操作。

映射中明顯的遞歸是計算列表中一個元素上的函數，然後使用遞歸調用來處理列表的其餘部分。但是，您需要將處理一個元素的結果與處理列表的其餘部分的結果相結合，這需要遞歸調用之後的操作。

避免這種情況的一個很常見的模式是將組合內部的遞歸調用;你將處理後的元素作爲參數傳入，並使其成爲map負責進行組合的一部分。

def map(l, f): 
    if l == []: 
     return [] 
    else: 
     return map(l[1:], f, f(l[0]))

現在它是尾遞歸！但它顯然也是錯誤的。在尾遞歸調用中，我們傳遞了3個參數，但map只有兩個參數。然後就是我們用第三個值做什麼的問題。在基本情況下（列表爲空時），很明顯：返回一個包含傳入信息的列表。在遞歸情況下，我們計算一個新值，並從頂部傳入此額外參數，並且我們有遞歸調用。新值和額外參數需要彙總在一起傳遞給遞歸調用，以便遞歸調用可以是尾遞歸。所有這一切都表明了以下幾點：

def map(l, f): 
    return map_acc(l, f, [])  

def map_acc(l, f, a): 
    if l == []: 
     return a 
    else: 
     b = a + [f(l[0])] 
     return map_acc(l[1:], f, b)

從而可以更簡潔，Pythonically表現爲其他的答案顯示，而不訴諸單獨的輔助功能。但是這顯示了將非尾遞歸函數轉換爲尾遞歸函數的一般方法。

在上面，a被稱爲累加器。通常的想法是將通常做的操作移到遞歸調用後進入下一個遞歸調用，通過包裝工作外部調用完成「迄今」並將其傳遞到累加器中。

如果map可以被看作意義「的l每個元素上調用f，並返回結果列表」，map_acc可以被認爲是意爲「叫f的l每一個元素，返回列表結果結合a，已經產生的結果列表「。

來源

2011-08-08 01:43:32 Ben

它可以，而不是鍵入另一個函數，使第三個參數的默認值作爲參數在主函數中？第一次通話完成後會被修改。 –

@JuanGallostra是的，這是有效的（只要你小心不要改變或返回值可能會綁定到一些代碼路徑中的默認參數）。 – Ben

map_acc中的尾部調用應該是map_acc（l [1：]，f，b），因爲map只需要2個參數。 – andrebask

不是一個真正的答案，對不起，但另一種實現地圖的方法是把它寫成一個摺疊。如果你嘗試，你會發現它只是出現在「正確」與foldr;使用foldl會給你一個反向列表。不幸的是，foldr不是尾遞歸，而foldl是。這表明關於rev_map有更多的「自然」（地圖返回反向列表）。不幸的是，我沒有受到足夠的教育，無法進一步採取這一做法（我懷疑你可能會將此概括爲說沒有不使用累加器的解決方案，但我個人不知道如何提出論證）。

來源

2011-08-08 01:51:39

Coverting遞歸函數的尾遞歸一個在Python

回答

相關問題