これが前方再帰である理由がわかりません。
int count(int x) {
if(x<=0) return 0;
return 1 + count(x - 1);
}
それは模擬試験の質問であり、答えはその前方再帰です。なぜそうなのですか?どうすれば2つを区別できますか?
これが前方再帰である理由がわかりません。
int count(int x) {
if(x<=0) return 0;
return 1 + count(x - 1);
}
それは模擬試験の質問であり、答えはその前方再帰です。なぜそうなのですか?どうすれば2つを区別できますか?
あなたは自分自身を呼んだ後に追加をしています。末尾再帰は、後には絶対に何もできないことを意味します
実装を理解していれば、その理由は明らかです。
プログラムカウンターにあるcount
から初めて電話をかけたとしましょう。その後、ほとんどのメソッドを実行します。このスタックフレームに対して、カウントの再帰呼び出しが行われていると言います。末尾再帰を使用している場合、それ自体を呼び出すときに、リターンアドレスをとして設定できます(私を呼び出したコードに直接移動します)。それ以降に何かを行う場合は、差出人住所を(加算のアドレス)として設定する必要があります。リターンアドレスを格納するためにスタックフレームを必要としないため、再帰を反復に変換することもはるかに簡単です。自分自身を呼び出すと、メソッドの先頭にジャンプできます。main
0xAAA
0xBBB
0xAAA
0xBBC
count
(簡単な例の)解決策は、結果を別のパラメーターに積み上げることです。
int count(int x, int res) {
if(x<=0) return res;
return count(x - 1, res + 1);
}
その後は何もしないことに注意してください。
この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
}