對象的尾遞歸

我有一個遞歸函數，我想做尾遞歸。我的實際問題更復雜並且與上下文有關。但我想解決的問題是用這個簡單的程序來演示的：對象的尾遞歸

#include <iostream> 

struct obj 
{ 
    int n; 

    operator int&() { return n; } 
}; 

int tail(obj n) 
{ 
    return tail(obj{ n + 1 > 1000 ? n - 1000 : n + 1 }); 
} 

int main() 
{ 
    tail(obj{ 1 }); 
}

這似乎是自然的，這是尾遞歸。但它不是，因爲每次都需要調用obj n的析構函數。至少MSVC13（編輯:) 和MSVC15不會優化此。如果我用int替換obj並相應地更改調用，它將按預期變爲尾遞歸。

我的實際問題是：是否有一種簡單的方法可以將這個尾遞歸分開，只需將obj替換爲int？我的目標是獲得性能優勢，因此使用堆分配內存和new最有可能沒有幫助。

來源

2016-12-30 IceFire

最簡單的方法：獲得更好的編譯器，無論如何你已經過時了...... –

msvc15不會這樣做，要麼 – IceFire

你如何期待這個尾遞歸終止？ –

由於您使用一個臨時的，我想你不需要遞歸調用之後的對象。

一個相當的hackish的解決辦法是分配一個對象，一個指針傳遞給它，並且使遞歸調用，向其中傳遞您新構造的對象之前重新分配它。

struct obj 
{ 
    int n; 

    operator int&() { return n; } 
}; 

int tail_impl(obj*& n) 
{ 
    int n1 = *n + 1 > 1000 ? *n - 1000 : *n + 1; 
    delete n; 
    n = new obj{n1}; 
    return tail_impl(n); 
} 

int tail(obj n) 
{ 
    obj *n1 = new obj{n}; 
    auto ret = tail_impl(n1); 
    delete n1; 
    return ret; 
} 

int main() 
{ 
    tail(obj{ 1 }); 
}

我明顯地忽略了一些關鍵的異常安全細節。但GCC is able to turn tail_impl into a loop，因爲它確實是尾遞歸。

來源

2016-12-30 14:12:57 StoryTeller

好主意，的確如此！但是，我確實需要不要改變這個對象。我的真實故事是，我有部分應該是尾遞歸的，而其他部分不是......也許，您的解決方案可以用於任何方面，我仍然在尋找一個非參考解決方案 - 如果有任何問題的話，請點擊這裏 – IceFire

How 'tail_impl'遞歸結束了嗎？ – 0x499602D2

@ 0x499602D2 - 它沒有，就像在OP的帖子中一樣。他們使用無限遞歸來測試代碼是否被循環代替。如果沒有，則會發生堆棧溢出。 – StoryTeller

簡短的回答：號

再回應：你可能會找到一種方法來實現這一點，但肯定是不容易的。由於尾調用優化的不是標準所要求的，你永遠無法知道，如果你的程序將會使編譯器的一些小的改動不能對代碼進行優化。

更糟的是，考慮當你需要調試程序時會發生什麼。編譯器幾乎肯定不會使用調試器標誌優化高級尾調用，這意味着您的程序只能在發佈模式下正常工作。這會使程序難以維護。

替代尾部遞歸 只需編寫一個循環。它總是可以完成的，而且可能會非常複雜，而且更不復雜。它也不使用堆，所以開銷會小得多。

來源

2017-01-02 09:36:37

謝謝！你的回答更直截了當，但在大多數情況下，StoryTeller更有幫助，這就是爲什麼我給他的標誌。我希望這是可以理解的 – IceFire

嗯......有用的東西是編寫一個循環。我完全忘了在我的回答中提到，所以我現在就添加了它。 :-) –

也是一個很好的想法，謝謝。可悲的是，我再也無法贊成 – IceFire

對象的尾遞歸

回答

相關問題