6

この SO answer に書かれているように、末尾再帰アルゴリズムが何であるかを知っています。しかし、MIT のクイック ソート アルゴリズムのビデオを見ていると、18:30 秒で、教授はこれが末尾再帰アルゴリズムであると述べています。これがどのように末尾再帰的であるかを接続できません。再帰のどのステップでも計算を行っていませんか？これが末尾再帰アルゴリズムの例として引用されている理由を説明できますか? 再帰アルゴリズムとは何かを知っているという前提に基づいて答えてください。私には明確ではない部分は、なぜ末尾再帰と呼ばれるのですか?

4

3 に答える 3

7

末尾再帰は、段階的に計算することではありません。「コールスタックを構築せずに再帰を評価できた」ということです。What is tail recursion? で与えられた例 はこれの特殊なケースです。例をさらに深く見ると、次のことがわかります。

def recsum(x):
 if x==1:
  return x
 else:
  return x+recsum(x-1)

1) 上記のコードを正常に実行するには、コール スタックを構築する必要があります。しかし、

def tailrecsum(x,running_total=0):
  if x==0:
    return running_total
  else:
    return tailrecsum(x-1,running_total+x)

2) 上記のコードを実行するために、running_total のためにコール スタックを構築する必要はありません。この関数を評価するために必要なステータスが running_total に格納されているため、「元の呼び出し」と再帰のコール スタックを構築するだけで、コール スタックを構築する必要はありません。

そして、クイックソートについては、教授はおそらく、末尾再帰を「使用する」ことでクイックソートを最適化できることを意味していたと思います。qsort() の 2 つの分岐部分については、(ピボット位置に基づいて) より高い項目を持つ一方の側で末尾再帰を使用できます。

ここに画像の説明を入力

于 2012-08-08T12:25:23.830 に答える
4

Quicksortの wiki ページを見てください。末尾再帰のバージョンがあります

 function quicksort(array, 'left', 'right')

  // If the list has 2 or more items
  if 'left' < 'right'

      // See "Choice of pivot" section below for possible choices
      choose any 'pivotIndex' such that 'left' ≤ 'pivotIndex' ≤ 'right'

      // Get lists of bigger and smaller items and final position of pivot
      'pivotNewIndex' := partition(array, 'left', 'right', 'pivotIndex')

      // Recursively sort elements smaller than the pivot
      quicksort(array, 'left', 'pivotNewIndex' - 1)

      // Recursively sort elements at least as big as the pivot
      quicksort(array, 'pivotNewIndex' + 1, 'right')

Tail recursionの定義によると、 の最後のメソッド呼び出しquicksortはそれ自体であり、それが末尾再帰です。しかし、他のいくつかの実装は末尾再帰ではありません。

 quicksort(left) + pivot + quicksort(right)

の最終quicksortアクションはsorted_left + pivot + sorted_right

于 2012-08-08T12:25:45.957 に答える
1

再帰関数の最初のステップはパーティショニングです。そして、最後のステップとして、2 つのパーティションで再帰関数を呼び出します。

ウィキペディアから：

コンピューター サイエンスでは、テール コールは、別のプロシージャ内で最終アクションとして発生するサブルーチン コールです。戻り値を生成する場合があり、呼び出し元のプロシージャによってすぐに返されます。

于 2012-08-08T12:02:11.087 に答える