1

Javaでの再帰に関する2つの小さな質問。

public int recursiveFunc(int n) {
    if (n==0)
        return(1);
    else
        return( recursiveFunc(n -1) + 1 );
}

recursiveFunc（150）が呼び出された場合、答えは151になります。誰かがこの答えを取得する方法/どのような手順を実行するかを説明してもらえますか？

recursiveFunc2（17）を想定した次の関数についても同じですが、答えは何で、どのようになりますか？ありがとう。

public int recursiveFunc2(int n) {
    if (n == 0)
        return(0);
    else
        return( recursiveFunc2(n/2)+1 );
}
4

2 に答える 2

3

置き換えた場合:

return( recursiveFunc(n1) + 1 );

と：

return recursiveFunc(n - 1) + 1 ;

期待どおりに動作します。

2 番目の関数については、もう少し興味深いものです。0 (再帰停止条件) になるまでに、17 を 2 で割る回数を考えてみてください。少しトリッキーですが、手順を分析してください。

recursiveFunc2(17) = 
recursiveFunc2(8) + 1 = 
recursiveFunc2(4) + 1 + 1 = 
recursiveFunc2(2) + 1 + 1 + 1 = 
recursiveFunc2(1) + 1 + 1 + 1 + 1 = 
recursiveFunc2(0) + 1 + 1 + 1 + 1 + 1 = 
                0 + 1 + 1 + 1 + 1 + 1 = 5
于 2012-11-01T08:21:28.390 に答える
1

再帰を分析するときは、基本ケースを調べて最終結果を得る必要があります。このセットアップでは、基本ケースは

if (n == 0)
    return(0);

そのため、そこからリバース エンジニアリングを行ってから、エントランス ケースまで構築することができます。あなたの例では、入り口は whenn = 150です。

規範事例

recursiveFunc(0)と呼ばれます。その中でベースケースをぶつけてn == 0返し1ます。

築き上げる

1以前の呼び出しに戻されます。

return recursiveFunc( n - 1 ) + 1;//note that n was 1 to produce a call of 0

したがって、recursiveFunc( 1 - 1 )1になり、その行はより似ています

return 1 + 1;

継続する

これをさらにバックアップすると、次の呼び出しはそれが戻る場所になります2。さて、明らかなパターンがあるはずです。つまり、その

A0 = 1;
A1 = A0 + 1;
A2 = A1 + 1;
...
An = A(n-1) + 1;
...
An = n + 1;

これが、A150 = 151、またはより明確にrecursiveFunc(150) == 151.

于 2012-11-01T08:33:23.103 に答える