在C＃中優化尾部調用

我有一個深度遞歸函數，即使在大量輸入的情況下，理論上也應該可以很好地工作。問題在寫這篇文章的時候，我忘記了C＃並沒有很好地完成尾部優化，如果有的話，那麼我會得到StackOverflowExceptions以滿足任何複雜的輸入。該方法的基本結構是兩種大方法，每種方法都稱爲另一種方法。在C＃中優化尾部調用

public object Simplify(object param) { 
    if (IsSimple(param)) 
     return param; 
    else 
     return Expand(param); 
} 

private object Expand(object param) { 
    return Simplify(ProcessExpansion(param)); 
}

兩個IsSimple和ProcessExpansion具有相對固定的堆棧深度 - 唯一的問題是簡化和展開之間的遞歸。你將如何去減少堆棧深度？

我在想返回會計算結果的代表，但這看起來像是矯枉過正 - 必須有一個更簡單的方法。這是我的一個解決方案的想法（這是不是很優美，因爲我一直在想我必須做一些可怕的錯誤這裏）：

public object Simplify(object param) { 
    object result =() => SimplifyInternal(param); 
    while (result is Func<object>) 
     result = ((Func<object>)result)(); 
    return result; 
} 

private object SimplifyInternal(object param) { 
    if (IsSimple(param)) 
     return param; 
    else 
     return Expand(param); 
} 

private object Expand(object param) { 
    return() => SimplifyInternal(ProcessExpansion(param)); 
}

所以我的兩個問題是：

這是什麼這種解決方案感覺可怕嗎？
你能想到更好的嗎？

來源

2010-09-10 configurator

只需注意一點，.NET 4.0 x64運行時會優化尾部調用，而x86不會。我知道，完全愚蠢。 – 2010-09-10 00:19:39

爲什麼不在F＃中編程？我寧願讓編譯器優化它（語言特性），然後祈禱抖動會計算出來。 – MrDosu 2010-09-10 00:24:41

儘管我喜歡F＃，但如果可以的話，我會把這個評論排在前面。建議您將整個項目切換到F＃只是因爲您需要在一個點上進行尾部呼叫優化不是很有建設性。 – 2010-09-10 00:38:08

這不只是

while(!IsSimple(param)) 
    param = ProcessExpansion(param); 
return param;

？

來源

2010-09-10 00:15:20 Brian

問題是，如果A僅在尾部位置調用B，而B只在尾部位置調用A，那麼您應該能夠做一點按摩來合併兩個方法，並圍繞它進行一個while循環並獲得相同的語義。 – Brian 2010-09-10 00:54:14

是的。這個例子大大簡化了 - 功能足夠複雜，每個功能都完全不同。還有一些多態性與參數可能具有的不同類型的值有關。我可以在理論上將它們組合成一個單一的函數，但這會使它們難以維護。 – configurator 2010-09-10 01:02:30

確實。在這種情況下，一種可能的途徑是在F＃中編寫這些函數。另一個是使用蹦牀（看起來像你正在嘗試這個）。還有一種情況是使用線程（例如，當堆棧變高時，QueueUserWorkItem並阻止結果）。這些選擇都不是非常有吸引力的;使用您在創作和維護時很熟悉的人。此外，請考慮您是否可以「改變問題」，以便首先解決問題。 – Brian 2010-09-10 01:31:23

在C＃中優化尾部調用

回答

相關問題