1

この関数は何をしますか？そして、それをどのように評価しますか？

それを追跡する方法は？再帰的方法を理解する方法は？

再帰が理解できず、試験日が近づいています。再帰を理解するには、まず再帰を理解する必要があります。

しかし、私は少し複雑な再帰的メソッドを書くことはできません。誰でも最も単純な英語の単語を使って私を助けてくれますか。

public class BalancedStrings {

    public static void printBalanced(String prefix, int a, int b) {
        if (a > 0)
            printBalanced(prefix + "a", a - 1, b);
        if (b > 0)
            printBalanced(prefix + "b", a, b - 1);
        if (a == 0 && b == 0)
            System.out.println(prefix);
    }

    public static void printBalanced(int n) {
        if (n % 2 == 0) {
            printBalanced("", n / 2, n / 2);
        }
    }

    public static void main(String[] args) {
        printBalanced(4);
    }
}
4

4 に答える 4

6

への呼び出しprintBalanced()は再帰呼び出しです。再帰を認識する方法は、関数が自分自身を呼び出しているときです。再帰は、ツリーを使用して描画すると最もよく理解されます。

ここに画像の説明を入力

ツリーの分岐は、終了条件(この場合は ) が満たされるまで、さらに関数を作成し続けますa == 0 && b == 0。あなたが提供した関数は、指定された数の「a」および「b」文字と連結された文字列「prefix」を再帰的に出力しているように見えます。変数aとbが に達する0と、再帰が停止し、結果が次を使用して出力されます。System.out.println(prefix);

メイン関数では、次のようなパラメーターを持つprintBalanced(int n)呼び出しに整数 4 を渡しています。printBalanced(String prefix, int a, int b)printBalanced("",2,2);

全体的な結果は、バランスのとれた数の a と b で連結されたプレフィックスです。

于 2012-06-29T15:16:27.650 に答える
0

あなたの停止条件はそれです

a == 0 & b == 0

この条件が満たされるまで、関数を再帰的に呼び出し、両方が 0 になるまで a と b を下げます。

printBalanced() にいくつかのブレークポイントを設定してみて、どのように機能するかを確認してください。

于 2012-06-29T15:20:55.507 に答える
0

printBalanced への各呼び出しの前に print ステートメントを配置し、各 printBalanced メソッド定義の最初の行として print ステートメントを配置すると、再帰を確認するのに役立つ場合があります。下記参照：

public class BalancedStrings {

    public static void printBalanced(String prefix, int a, int b) {
        System.out.println( "printBalanced called prefix = " + prefix + " a = " + a + " b = " + b );
        if (a > 0) {
            System.out.println( "printBalanced calling printBalanced with prefix = " + prefix + " a-1 = " + (a-1) + " b = " + b );
            printBalanced(prefix + "a", a - 1, b);
        }
        if (b > 0) {
            System.out.println( "printBalanced calling printBalanced with prefix = " + prefix + " a = " + a + " b-1 = " + (b-1) );
            printBalanced(prefix + "b", a, b - 1);
        }
        if (a == 0 && b == 0)
            System.out.println(prefix);
    }

    public static void printBalanced(int n) {
        System.out.println( "printBalanced called n = " + n );
        if (n % 2 == 0) {
            printBalanced("", n / 2, n / 2);
        }
    }

    public static void main(String[] args) {
        printBalanced(4);
    }
}

また、printBalanced はオーバーロードされたメソッドとも呼ばれます。2 つの「メソッド シグネチャ」があるためです。これは、基本的に複数回定義され、各メソッド定義にはメソッドに渡される変数の異なるセットがあることを意味します。

基本的に、変数 a と b がゼロになるまで、printBalanced は自分自身を呼び出し続けます。次に、蓄積し続ける結果のプレフィックスを出力します。

また、各メソッド呼び出しがプレフィックス a と b の現在の状態を呼び出しスタックにプッシュするため、この魔法のすべてが発生する可能性があります。メソッドが再帰呼び出しを行わずに最終的に戻ると、スタックは巻き戻されます。

これが役立つことを願っています！再帰は理解するのが難しい場合があります。また、自分でコンピューターを再生し、呼び出しスタックにプッシュされるプレフィックス a と b の値を紙に書き留めてメソッドの実行を追跡することにより、呼び出しを手動で追跡することもできます。

トレーシング プリントを含めたプログラムの出力を次に示します。

C:\Users\>java BalancedStrings
printBalanced called n = 4
printBalanced called prefix =  a = 2 b = 2
printBalanced calling printBalanced with prefix =  a-1 = 1 b = 2
printBalanced called prefix = a a = 1 b = 2
printBalanced calling printBalanced with prefix = a a-1 = 0 b = 2
printBalanced called prefix = aa a = 0 b = 2
printBalanced calling printBalanced with prefix = aa a = 0 b-1 = 1
printBalanced called prefix = aab a = 0 b = 1
printBalanced calling printBalanced with prefix = aab a = 0 b-1 = 0
printBalanced called prefix = aabb a = 0 b = 0
aabb
printBalanced calling printBalanced with prefix = a a = 1 b-1 = 1
printBalanced called prefix = ab a = 1 b = 1
printBalanced calling printBalanced with prefix = ab a-1 = 0 b = 1
printBalanced called prefix = aba a = 0 b = 1
printBalanced calling printBalanced with prefix = aba a = 0 b-1 = 0
printBalanced called prefix = abab a = 0 b = 0
abab
printBalanced calling printBalanced with prefix = ab a = 1 b-1 = 0
printBalanced called prefix = abb a = 1 b = 0
printBalanced calling printBalanced with prefix = abb a-1 = 0 b = 0
printBalanced called prefix = abba a = 0 b = 0
abba
printBalanced calling printBalanced with prefix =  a = 2 b-1 = 1
printBalanced called prefix = b a = 2 b = 1
printBalanced calling printBalanced with prefix = b a-1 = 1 b = 1
printBalanced called prefix = ba a = 1 b = 1
printBalanced calling printBalanced with prefix = ba a-1 = 0 b = 1
printBalanced called prefix = baa a = 0 b = 1
printBalanced calling printBalanced with prefix = baa a = 0 b-1 = 0
printBalanced called prefix = baab a = 0 b = 0
baab
printBalanced calling printBalanced with prefix = ba a = 1 b-1 = 0
printBalanced called prefix = bab a = 1 b = 0
printBalanced calling printBalanced with prefix = bab a-1 = 0 b = 0
printBalanced called prefix = baba a = 0 b = 0
baba
printBalanced calling printBalanced with prefix = b a = 2 b-1 = 0
printBalanced called prefix = bb a = 2 b = 0
printBalanced calling printBalanced with prefix = bb a-1 = 1 b = 0
printBalanced called prefix = bba a = 1 b = 0
printBalanced calling printBalanced with prefix = bba a-1 = 0 b = 0
printBalanced called prefix = bbaa a = 0 b = 0
bbaa
于 2012-06-29T15:30:22.593 に答える
0

最も基本的なコンピューター サイエンスの意味では、再帰はそれ自体を呼び出す関数です。再帰の実用的な使用法はほとんどありません。

ツリー トラバーサル
グラフ
字句解析/解析
並べ替え

再帰の基本的な考え方は、元の問題をそれ自体の小さな (より簡単に解決できる) インスタンスに分割し、それらの小さなインスタンスを (通常は同じアルゴリズムを再度使用して) 解決し、最終的なソリューションに再構築することです。

たとえば、数値の階乗を計算する次の C コードを考えてみましょう。

function factorial(int n)
{
  int fact = 1;
  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }
  return fact;
}
于 2012-06-29T15:21:43.717 に答える