"find"の再帰バージョンと再帰的でないバージョンの違いは何ですか？本<em>加速C++プログラミング</em>で

Question

は、205ページ、find

template <class In, class X> In find(In begin, In end, const X& x) 

の2次実装があります私は何の違いは、パフォーマンスの面であるものを知ることに興味があります（それは実際には同じ後ですかコンパイル？）を実行します。コンパイラExplorerを使用して

非再帰的

template <class In, class X> In find(In begin, In end, const X& x) 
{ 
    while (begin != end && *begin != x) 
     ++begin; 
    return begin; 
} 

再帰

template <class In, class X> In find(In begin, In end, const X& x) 
{ 
    if (begin == end || *begin == x) 
     return begin; 
    begin++; 
    return find(begin, end, x); 
} 

は、私は、次の

非再帰的https://godbolt.org/g/waKUF2

再帰https://godbolt.org/g/VKNnYZ

を得たKerrekによって提案されました

コンパイル後はまったく同じようですか？ （私がツールを正しく使っていれば申し訳ありませんが、私はC++の新機能です）

Answer 1

再帰関数がスタック上にさらに要素を追加します。これは潜在的に再帰を開始する前にスタックの状態と再帰回数に応じてスタックオーバーフローエラーを引き起こす可能性があります。

各関数呼び出しは、戻りアドレスを含むスタックにデータをプッシュします。これは、データが見つかるまで続きます。この時点で、すべての関数は、最後に返された値を返すようになり、最後に元の関数findを呼び出すまで戻ります。

各関数呼び出しで格納される正確なデータ量は、呼び出し規約とアーキテクチャによって異なります。スタック上にデータをプッシュすることによるオーバーヘッドもあり、アルゴリズムを遅くすることができますが、それはアルゴリズムに依存します。

厳密には、テールコールに最適化されていない再帰です。

Answer 2

ほとんどの場合、再帰は遅く、スタックの多くを占めます。再帰の主な利点は、ツリートラバーサルのような問題では、アルゴリズムを少し容易に、あるいはより「エレガント」にすることです。

チェックアウトの比較のいくつか： Recursion vs Iteration