この質問に答えようとしたときに、いくつかの奇妙な結果に出くわしました:再帰メソッドのパフォーマンスを改善するにはどうすればよいですか?
しかし、その投稿を読む必要はありません。ここで関連するコンテキストを示します。これは長いように思えるかもしれませんが、一度読み通せばそれほど複雑ではありません。すべての人にとって興味深いものになることを願っています。コンテキストについては、
syra(n) = { 1 if n=1;
n + syra(n/2) if n is even; and
n + syra(3n+1) if n is odd
}
と
syralen(n) = No. of steps to calculate syra (n)
例:
syralen(1)=1, syralen(2)=2 since we need to go two steps.
syra(10) = 10 + syra(5) = 15 + syra(16) = 31 + syra(8) = 39 + syra(4) = 43 + syra(2) = 45 + syra(1) = 46. したがって、syra(10) には 7 つのステップが必要でした。したがってsyralen(10)=7
そして最後に、
lengths(n) = syralen(1)+syralen(2)+...+syralen(n)
そこの質問ポスターは計算しようとしていますlengths(n)
私の質問は、Op が投稿した再帰的なソリューションに関するものです (これは、その質問の 2 番目のスニペットです)。ここに再投稿します：
public class SyraLengths{
int total=1;
public int syraLength(long n) {
if (n < 1)
throw new IllegalArgumentException();
if (n == 1) {
int temp=total;
total=1;
return temp;
}
else if (n % 2 == 0) {
total++;
return syraLength(n / 2);
}
else {
total++;
return syraLength(n * 3 + 1);
}
}
public int lengths(int n){
if(n<1){
throw new IllegalArgumentException();
}
int total=0;
for(int i=1;i<=n;i++){
total+=syraLength(i);
}
return total;
}
public static void main(String[] args){
System.out.println(new SyraLengths().lengths(5000000));
}
}
確かに、再帰的にそれを行う珍しい（そしておそらく推奨されない）方法ですが、正しいことを計算します。私はそれを確認しました。私は同じもののより一般的な再帰バージョンを書き込もうとしました:
public class SyraSlow {
public long lengths(int n) {
long total = 0;
for (int i = 1; i <= n; ++i) {
total += syraLen(i);
}
return total;
}
private long syraLen(int i) {
if (i == 1)
return 1;
return 1 + ((i % 2 == 0) ? syraLen(i / 2) : syraLen(i * 3 + 1));
}
ここで奇妙な部分があります-上記の両方のバージョンのパフォーマンスを次のようにテストしようとしました:
public static void main(String[] args){
long t1=0,t2=0;
int TEST_VAL=50000;
t1 = System.currentTimeMillis();
System.out.println(new SyraLengths().lengths(TEST_VAL));
t2 = System.currentTimeMillis();
System.out.println("SyraLengths time taken: " + (t2-t1));
t1 = System.currentTimeMillis();
System.out.println(new SyraSlow().lengths(TEST_VAL));
t2 = System.currentTimeMillis();
System.out.println("SyraSlow time taken: " + (t2-t1));
}
の場合TEST_VAL=50000、出力は次のとおりです。
5075114
SyraLengths time taken: 44
5075114
SyraSlow time taken: 31
予想どおり (私は推測します)、単純な再帰はわずかに優れています。しかし、さらに一歩進んで を使用するTEST_VAL=500000と、出力は次のようになります。
62634795
SyraLengths time taken: 378
Exception in thread "main" java.lang.StackOverflowError
at SyraSlow.syraLen(SyraSlow.java:15)
at SyraSlow.syraLen(SyraSlow.java:15)
at SyraSlow.syraLen(SyraSlow.java:15)
それはなぜです？SyraLengths のバージョンが StackOverflow に当たらない(でも動作するTEST_VAL=5000000)のは、ここで Java によってどのような最適化が行われているのでしょうか? JVM が末尾呼び出しの最適化を行っている場合に備えて、アキュムレータ ベースの再帰バージョンを使用してみました。
private long syraLenAcc(int i, long acc) {
if (i == 1) return acc;
if(i%2==0) {
return syraLenAcc(i/2,acc+1);
}
return syraLenAcc(i * 3 + 1, acc+1);
}
しかし、それでも同じ結果が得られました (したがって、ここには末尾呼び出しの最適化はありません)。それで、ここで何が起こっているのですか？
PS: 思いついた場合は、より適切なタイトルに編集してください。