4

これが前方再帰である理由がわかりません。

int count(int x) {
    if(x<=0) return 0;
    return 1 + count(x - 1);
}

それは模擬試験の質問であり、答えはその前方再帰です。なぜそうなのですか?どうすれば2つを区別できますか?

4

2 に答える 2

8

あなたは自分自身を呼んだ後に追加をしています。末尾再帰は、後には絶対に何もできないことを意味します

実装を理解していれば、その理由は明らかです。

プログラムカウンターにあるcountから初めて電話をかけたとしましょう。その後、ほとんどのメソッドを実行します。このスタックフレームに対して、カウントの再帰呼び出しが行われていると言います。末尾再帰を使用している場合、それ自体を呼び出すときに、リターンアドレスをとして設定できます(私を呼び出したコードに直接移動します)。それ以降に何かを行う場合は、差出人住所を(加算のアドレス)として設定する必要があります。リターンアドレスを格納するためにスタックフレームを必要としないため、再帰を反復に変換することもはるかに簡単です。自分自身を呼び出すと、メソッドの先頭にジャンプできます。main 0xAAA0xBBB0xAAA0xBBCcount

(簡単な例の)解決策は、結果を別のパラメーターに積み上げることです。

int count(int x, int res) {
  if(x<=0) return res;
  return count(x - 1, res + 1);
}

その後は何もしないことに注意してください。

于 2010-11-15T20:59:46.463 に答える
4

このSOの質問、テールとフォワードの再帰を見ましたか?

マシューには答えがあり、長い形式は次のようになります。

int count(int x) {
  if(x<=0) return 0;
  return 1 + count(x - 1);
}  

次のように書くことができます(そして次のように展開されます):

int count(int x) {
    if(x<=0) return 0;
    int tmp_result = count(x - 1);
    return 1 + tmp_result; // e.g. recursion is not last
}
于 2010-11-15T20:59:48.010 に答える