オブジェクトによるテール再帰

Question

私はテール再帰的にする再帰関数を持っています。私の実際の問題は、より複雑で文脈に依存しています。しかし、私は解決したい問題は、この単純なプログラムで実証されています

#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はこれを最適化しません。 objをintに置き換え、それに応じて呼び出しを変更すると、期待どおりにテール再帰的になります。

私の実際の質問は、objをintに置き換えるだけで、これを末尾再帰的にする簡単な方法はありますか？私はパフォーマンスのメリットを狙っているので、ヒープ割り当てメモリとnewで遊んでいるのは、ほとんど役に立ちません。

Answer 1

一時的なものを使用しているので、再帰呼び出し後にオブジェクトが必要ないと仮定します。

非常に有益な解決策の1つは、再帰呼び出しを作成する前に、オブジェクトを割り当て、ポインタを渡し、再割り当てして、新しく作成したオブジェクトを渡すことです。

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、それは確かにテール再帰です。

Answer 2

短い答え：号

長い回答：あなたがこれを達成するための方法が、確かに簡単なものを見つけるかもしれません。 標準でテールコールの最適化が必要ないため、プログラムのマイナーチェンジによってコンパイラがコードを最適化できない場合は、絶対にわからないことがあります。

さらに悪いことに、プログラムをデバッグする必要があるときに何が起こるかを検討してください。コンパイラはデバッガフラグを使って高度なテールコールを最適化することはほとんどありません。つまり、プログラムはリリースモードでのみ正しく動作します。これにより、プログラムのメンテナンスがはるかに難しくなります。

テイル再帰の代替 ループを作成するだけです。それはいつでも行うことができ、ずっと複雑ではありません。また、ヒープも使用しないため、オーバーヘッドははるかに小さくなります。