ここで尾の再帰を使用することの利点は何ですか？

Question 1

Tail Recursive Function Callにより、コンパイラは通常、定期的な再帰ではできない特別な最適化を実行できます。尾の再帰関数では、再帰コールが実行される最後のものです。この場合、コールごとにスタックフレームを割り当てる代わりに、コンパイラはコードを再加工して現在のスタックフレームを再利用することができます。つまり、テール再帰関数は、数百または数千とは対照的に、単一のスタックフレームのみを使用します。

この最適化は、テールの再帰呼び出しが行われたら、実行するコードがもうないため、変数の以前のコピーが必要になることをコンパイラが知っているため、この最適化が可能です。たとえば、印刷されたステートメントが再帰コールに続いた場合、コンパイラは再帰コールリターン後に印刷する変数の値を知る必要があるため、スタックフレームを再利用できません。

この「スペース節約」とスタックの再利用が実際にどのように機能するかについての詳細情報と、例とともに、次のようになります。テールコール

編集：これがクイックソートにどのように適用されるかを説明しませんでしたか？まあ、いくつかの用語がその記事に投げ込まれているため、すべてがすべて混乱するようになります（そして、それのいくつかは単なる間違っています）。指定された最初の関数（QuickSort）は、左側に再帰的な呼び出しを行い、右側に再帰的な呼び出しを行い、その後終了します。右側の再帰呼び出しは、関数で起こる最後のことであることに注意してください。コンパイラがTail Recursive Optimizationをサポートする場合（上記で説明）、左呼び出しのみが新しいスタックフレームを作成します。すべての適切な呼び出しは、現在のフレームを再利用するだけです。これは保存できます いくつか スタックフレームがありますが、パーティション化がテールの再帰の最適化が重要ではない一連の呼び出しを作成する場合に依然として苦しむ可能性があります。さらに、右側の呼び出しが同じフレームを使用しても、左側の呼び出しは呼ばれます内部右側の呼び出しは、まだスタックを使用しています。最悪の場合、スタックの深さはnです。

説明されている2番目のバージョンはです いいえ 尾の再帰的なクイックソートですが、左並べ替えのみが再帰的に行われ、右のソートがループを使用して行われるクイックソートです。実際、このクイックソート（以前に別のユーザーが説明したように）は、再帰コールが実行する最後のものではないため、テール再帰の最適化を適用することはできません。これはどのように作動しますか？正しく実装すると、QuickSortの最初の呼び出しは、元のアルゴリズムの左側の呼び出しと同じです。ただし、右側の再帰呼び出しも呼ばれません。これはどのように作動しますか？まあ、ループはそれを処理します：「左右」をソートする代わりに、左を呼び出しで並べ替え、右を継続的に並べ替えて並べ替えます。 右の左. 。それは本当にばかげたサウンドですが、基本的には非常に多くの左翼を並べ替えて、権利が単一の要素になり、ソートする必要はありません。これにより、適切な再帰が効果的に削除され、機能が再帰的ではなくなります（擬似再帰的であれば）。ただし、実際の実装では、毎回左側だけを選択しません。最小の側面を選択します。アイデアはまだ同じです。基本的には、両方ではなく片側で再帰的な呼び出しのみを行います。短い側を選ぶと、スタックの深さが適切なバイナリツリーの深さであるLog2（n）よりも大きくなることができないようにします。これは、短い側が常に現在の配列セクションの最大半分のサイズになるためです。ただし、記事で与えられた実装は、これを確実にしません。これは、「左はツリー全体」という同じ最悪のシナリオに苦しむ可能性があるためです。この記事は、実際にもっと読みたいと思っているなら、それについてかなり良い説明をしています。クイックソートに基づく効率的な選択と部分的な並べ替え

Question 2

「混合再帰/反復」バージョンの全体的なポイント、つまり、再帰によって1つのサブレンジを処理するバージョンと反復によって別のサブレンジの全体的なバージョンは、再帰的に処理する2つのサブレンジのどれがどれを選択できるかを選択することで、再帰の深さが決して超えないことを保証します log2 N, ピボットの選択がどれほど悪いかに関係なく.

のために TAIL-RECURSIVE-QUICKSORT 質問で提供される擬似コード、再帰処理が文字通り再帰的な呼び出しによって最初に実行される場合、その再帰呼び出しは短いサブレンジ。それ自体が、再帰深度が制限されることを確認することができます log2 N. 。したがって、再帰深度を達成するために、コードは、再帰コールでどのサブレンジを処理するかを決定する前に、サブレンジの長さを絶対に比較する必要があります。

そのアプローチの適切な実装は、次のように見えるかもしれません（出発点として擬似コードを借りる）

HALF-RECURSIVE-QUICKSORT(A, p, r)
   while p < r
      q = PARTITION(A, p, r)
      if (q - p < r - q)
        HALF-RECURSIVE-QUICKSORT(A, p, q-1)
        p = q+1
      else
        HALF-RECURSIVE-QUICKSORT(A, q+1, r)
        r = q-1

TAIL-RECURSIVE-QUICKSORT あなたが提供した擬似コードは、サブレンジの長さを比較する試みをしません。そのような場合、それはまったく利益をもたらしません。いいえ、それは実際には「尾の再帰」ではありません。 QuickSortは、テール再帰アルゴリズムに還元することはできません。

「QSORT Loguy Higuy」という用語でGoogle検索を行うと、2つのサブレンジの1つだけで再帰を使用するという同じアイデアに基づいて、別の人気のあるクイックソート実装（C標準ライブラリスタイル）の多数のインスタンスを簡単に見つけることができます。。 32ビットプラットフォームの実装では、再帰の深さがそれよりも高くなることはないことを保証できるため、最大深度の明示的なスタックを最大32の明示的なスタックを使用します。（同様に、64ビットプラットフォームでは、〜64のスタック深度のみが必要です。）

QUICKSORT 2つの文字通りの再帰通話を行うバージョンは、その点で非常に悪化しています。 N 最悪の場合。 2回の再帰コールを使用すると、再帰の深さが制限されることを保証することはできません log2 N. 。スマートコンパイラは、トレーリングコールをに交換できる場合があります QUICKSORT イテレーションで、つまりあなたを回します QUICKSORT あなたに TAIL-RECURSIVE-QUICKSORT, 、しかし、サブレンジの長さの比較を実行するほど賢くはありません。

Question 3

テールリクールを使用することの利点：=コンパイラがコードを最適化し、それを非再帰コードに変換するようにします。

再帰的なコードに対する非再帰コードの利点：=非再帰コードでは、再帰的なコードよりも少ないメモリを実行する必要があります。これは、再帰が消費するアイドルスタックフレームのためです。

ここに興味深い部分があります： - コンパイラが できる 理論はその最適化を実行し、実際にはそうではありません。 Dot-NetやJavaのような広範なコンパイラーでさえ、その最適化を実行しません。

すべてのコードの最適化が直面する問題の1つは、デバッグ性の犠牲です。最適化されたコードはソースコードに対応しなくなるため、スタックトレースと例外の詳細を簡単に理解できません。高性能コードまたは科学的アプリケーションは1つのことですが、大部分の消費者アプリケーションでは、リリース後もデバッグが必要です。したがって、最適化はそれほど活発に行われていません。

参照してください：

Question 4

ここには語彙の混乱があるようです。

最後のステートメントは再帰的な呼び出しであるため、最初のバージョンはテール再帰的です。

QUICKSORT(A, p, r)
  q = PARTITION(A, p, r)
  QUICKSORT(A, p, q-1)
  QUICKSORT(A, q+1, r)

再帰をループに変換することであるテールリクールの最適化を適用すると、2番目のものを取得します。

TAIL-RECURSIVE-QUICKSORT(A, p, r)
  while p < r
    q = PARTITION(A, p, r)
    TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
    p = q+1

これの利点は、通常、スタックメモリが少ないことです。何故ですか？理解するには、31個のアイテムで配列を並べ替えたいと想像してください。すべてのパーティションが完璧であるという非常にありそうもないケースでは、つまりアレイを中央に分割し、再帰深さは4になります。 3番目の3つのアイテムの2つ、そして4番目のアイテムの後、すべてがソートされます。

しかし、パーティションがこれほど完璧であることはめったにありません。その結果、すべての再帰が等しく深くなるわけではありません。私たちの例では、深さは3レベルしかないもので、7つ以上のレベルがあるものがある場合があります（最悪の場合は30）。再帰の半分を排除することで、最大再帰の深さが少なくなる可能性がかなりあります。

アンドレイトが指摘したように、多くの場合、最大のパーティションが常に繰り返し処理され、最小のパーティションが再帰的に処理されることを確認するために、範囲を比較します。これにより、特定の入力およびピボット選択戦略の可能な限り最小の再帰深度が保証されます。

しかし、これは必ずしもそうではありません。時には、人々はできるだけ早く結果をもたらしたい、または最初のn要素のみを見つけて並べ替えたい場合があります。これらの場合、彼らは常に2番目のパーティションの前に最初のパーティションをソートしたいと考えています。この状況でさえ、尾の再帰を排除すると、通常、メモリの使用が改善され、決して悪化することはありません。

Question 5

これがこの疑いを尋ねるのに正しい場所なのか、新しい質問を投稿するべきだったのか正確にはわかりませんが、非常によく似た疑問があります。



void print(int n) {
  if (n < 0) return;
  cout << " " << n;
// The last executed statement is recursive call
  print(n-1);
  print(n-1);
}

この尾は再帰的ですか？

Question 6

Tail Recursionは、Tail Call Eliminationと呼ばれる最新のコンパイラが行う最適化です。発信者/親が子供の呼び出しが終了した後、巻き戻し段階で何もしなければならない場合、最後に再帰コール自体が、最新のコンパイラが最適化のためにgotoとラベルを使用します。

例：私たちのバージョン - > nを1に印刷します

void fun(int n){
if(n==0)
return;
printf("%d\n",n);
fun(n-1)
}

最適化後 - >

void fun(int n){
start:
if(n==0)
return;
printf("%d\n",n);
n=n-1;
goto start;
}

この最適化の利点：1。テール再転用コールのスタックフレームはほとんどありません。 3.セグメンテーションの障害は、JavaのC/C ++とスタックオーバーフローです。