末尾再帰を学習するためのテストとして、Visual Studioで簡単なC ++フィボナッチ関数を作成しました。 仕組みを見てみましょう。
int fib_tail(int n, int res, int next) { if (n == 0) { return res; } return fib_tail(n - 1, next, res + next); }
値を返す前に末尾呼び出しを行うために、 fib_tail関数は最後のアクションとして自分自身を呼び出します。 生成されたアセンブラコードを見てみましょう。 これを行うには、/ O2最適化キーを使用してリリースモードでプログラムをコンパイルしました。 このコードは次のようになります。

あります! 最後の行に注意してください。CALLステートメントの代わりにJMPを使用します。 この場合、末尾再帰が機能し、アセンブラレベルで反復関数になったため、関数にはスタックオーバーフローの問題はありません。
これでは十分ではなかったので、入力変数nを増やしてパフォーマンスを試すことにしました。 次に、関数で使用される変数の型をintからunsigned long longに変更しました 。 プログラムを再度実行すると、突然スタックオーバーフローが発生しました。 このバージョンの関数は次のようになります。
typedef unsigned long long ULONG64; ULONG64 fib_tail(ULONG64 n, ULONG64 res, ULONG64 next) { if (n == 0) { return res; } return fib_tail(n - 1, next, res + next); }
生成されたアセンブラコードをもう一度見てみましょう。

予想通り、末尾再帰はここにはありませんでした! 現在、予想されるJMPの代わりに、 CALLが使用されます。 一方、2つのバージョンの関数の唯一の違いは、2番目のケースでは、32ビット変数ではなく64ビット変数を使用したことです。 これに関連して、64ビット変数を使用するときにコンパイラが末尾再帰を使用しないのはなぜですか?
プログラムを64ビットモードでコンパイルし、その動作を確認することにしました。 生成されたアセンブリコード:

ここでテール再帰が再現されました! 64ビットのレジスタ(rax、r8、rcx、rdx)のおかげで、呼び出された関数と呼び出された関数は共通のスタックを持ち、呼び出された関数は結果を呼び出し元関数内の呼び出しポイントに直接返します。
StackOverflow Webサイトで質問しました。問題はMicrosoft C ++コンパイラ自体にあるようです。 いずれかのコメントの著者は、この問題は他のC ++コンパイラでは見られないと述べていますが、自分で確認する必要があります。
GitHubにサンプルコードを投稿しました。コピーして、自分で実行してみてください。 RedditとStackoverflowで、VS2013 Community Editionでは説明した問題は発生しないと言われました。 VS2013 Ultimateで作業しようとしましたが、そこでも遭遇しました。 近日中に、GCCでコードをテストし、結果を比較しようとします。
GitHubのサンプルプロジェクトを参照してください。
特定のケースでコンパイラが末尾再帰を実装しない理由を突然理解する必要がある場合、私の調査があなたにとって役立つことを願っています。
じゃあね!
続き: habrahabr.ru/company/pvs-studio/blog/261029