java - Javaでのテール/フォワード再帰

Question

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

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

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

Answer 1

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

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

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

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

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

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

Answer 2

この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
}