1

この記事に関して質問があります。

このコードの間

function odds(n, p) {
  if(n == 0) {
    return 1
  } else {
    return (n / p) * odds(n - 1, p - 1)
  }
}

そしてこのコード

(function(){
  var odds1 = function(n, p, acc) {
    if(n == 0) {
      return acc
    } else {
      return odds1(n - 1, p - 1, (n / p) * acc)
    }
  }

  odds = function(n, p) {
    return odds1(n, p, 1)
  }  
})()

1) これがどれだけ役立つか、私は混乱しています。2 番目のスニペットには、自分自身を再度呼び出す前に必要なものを計算するため、オーバーヘッドが少ないテール コールが含まれているだけですか?

私が理解しているように、テールコールはまだ排除されておらず、最適化されているだけです。

odds2) そして、odds1とにかく存在する必要があるのはなぜですか? それは私にもまだはっきりしていません。

4

3 に答える 3

1

return (n / p) * odds(n - 1, p - 1)末尾再帰の最適化は次のとおりです。最初の例では、 odds（n-1）を呼び出すまで乗算の結果を計算できないため、インターペレーターは現在の位置を（スタック上の）メモリに保持する必要があります。そして、オッズへの新しい呼び出しを開きます。

再帰的に、それは次の呼び出しでも発生し、次の呼び出しでも発生します。したがって、再帰の終わりに到達して値を返し、積を計算し始めるまでに、保留中の操作はn個あります。

2番目の例では、実行されるreturnステートメントは単純return odds1(n - 1, p - 1, (n / p) * acc)なので、関数の引数を計算し、現在の位置を保持せずにodds1（n-1）を呼び出すだけです。これが最適化の場所です。スタックで新しいフレームを開くたびに、自分がどこにいるかを覚えておく必要がないからです。

本の参照のように考えてください。クックブックを開いて特定のレシピに移動すると、材料が次のように表示されます。

  1. 塩
  2. 次のページの材料

次のページには

  1. コショウ
  2. 次のページの材料

など。すべての材料が何であるかをどのように見分けますか？すべてのページで見たものを覚えておく必要があります。

2番目の例は次の成分リストに似ていますが：

  1. 塩
  2. これを忘れて、次のページに表示されているものを使用してください

次のページは次のとおりです。

  1. 塩
  2. コショウ
  3. これを忘れて、次のページに表示されているものを使用してください

最後のページに到達するまでに（両方が同じ量の関数呼び出しを行うという点で類推は正確であることに注意してください）、すべてのページで見たものを「記憶に留める」必要なしに、すべての要素を手に入れることができます。それはすべて最後のページにあるからです！

于 2011-01-16T20:55:39.560 に答える
1

最初のバージョンは末尾再帰ではありません。これは、値を取得した後にodds(n - 1, p - 1)を掛ける必要があるためです(n / p)。2 番目のバージョンでは、これを関数のパラメーターの計算に移動して、odds1適切に末尾再帰にする必要があります。

コール スタックを見ると、最初は次のようになります。

odds(2, 3)
  odds(1, 2)
    odds(0, 1)
    return 1
  return 1/2 * 1
return 2/3 * 1/2

一方、2番目は次のようになります。

odds(2, 3)
  odds1(2, 3, 1)
    odds1(1, 2, 2/3)
      odds1(0, 1, 1/2 * 2/3)
      return 1/3
    return 1/3
  return 1/3
return 1/3

再帰呼び出しの値を返すだけなので、コンパイラはこれを簡単に最適化できます。

odds(2, 3)
#discard stackframe
odds1(2, 3, 1)
#discard stackframe
odds1(1, 2, 2/3)
#discard stackframe
odds1(0, 1, 1/3)
return 1/3

oddsとを使用する理由はodds1、他のコードがこの関数を呼び出したときにアキュムレータの初期値を提供するためです。

于 2011-01-16T20:51:17.370 に答える
1

これがどれだけ役立つか、私は混乱しています。2 番目のスニペットには、自分自身を再度呼び出す前に必要なものを計算するため、オーバーヘッドが少ないテール コールが含まれているだけですか?

私が理解しているように、テールコールはまだ排除されておらず、最適化されているだけです。

手順の最後が次のようになっている場合:

push args
call foo
return

次に、コンパイラはそれを最適化して、

jump startOfFoo

プロシージャ コールを完全に排除します。

とにかく、なぜオッズとオッズ 1 が必要なのですか? それは私にもまだはっきりしていません。

の「コントラクト」はodds2 つの引数のみを指定します。3 番目の引数は単なる実装の詳細です。したがって、内部メソッドでそれを隠し、「ラッパー」を外部 API として提示します。

odds1次のように呼び出すoddsImplと、より明確になると思います。

于 2011-01-16T20:44:09.893 に答える