記事
開始
勉強を始める
JavaRush /Java Blog /Random-JA /Java での再帰
Алексей Дмитревский
レベル 31
Москва

Java での再帰

Random-JA グループに公開済み
再帰とは何かを理解するには、再帰とは何かを理解する必要があります。実際、このような機能を理解するのは難しいことではなく、一度理解するだけで十分です。そしてプログラミングに関しては練習しましょう。 Java の再帰 - 1再帰はプログラミングだけでなく、実生活でも発生します。鏡を手に取り、別の鏡の前に立ちます。反射の反射は反射などに反映されます。無限に向かう無限の数の反射が見えるでしょう。「実際の」再帰について詳しくは、記事「グラウンドホッグデーに捧げます...」を参照してください。現実の世界からプログラマーの日常生活に戻りましょう。簡単な定義: Java の再帰関数は、それ自体を呼び出す関数です。非常に単純で非常に有害な例を示しましょう。 
public void recursionFucn() {
    System.out.println("Привет, JavaRush!");
    recursionFucn();
}
なぜ有害なのでしょうか? 自分で確認することをお勧めします！この冒険に挑戦することに決めた場合 (プログラマなら、おそらくそうするでしょう!)、JVM がスローするエラーをコメントに書いてください =) この例や他の多くの例は、Java での再帰の使用には慎重に取り組む必要があることを示しています。 。問題を解決するためにそのようなアプローチがどこで、いつ、そしてなぜ正当化されるのかを理解し、関数の実行によってプログラムの実行が「グラウンドホッグデー」にならないようにする必要があります。 再帰を理解するためには、さらに 2 つの重要な定義があります。
  • 再帰の基礎- 再帰呼び出しのブロックを終了するための条件 - 再帰を呼び出す必要がない条件下での問題の基本的な解決策。
  • 再帰ステップは、パラメーターを変更するときに関数がそれ自体を呼び出すときです。
再帰関数を使用する典型的な例は、数値の階乗を計算することです。忘れた場合に備えて思い出させてください。正の整数の階乗N(N! として示されます) は、 の数値の積です1 до N: N! = 1 * 2 * 3 * … (N - 1) * N。ちなみに、定義上、ゼロの階乗は 1 に等しいです。したがって、階乗は、任意の正の整数とゼロ (数学の言葉で言えば、非負の整数の集合、または自然数と自然数の集合) に対して求めることができます。ゼロ）。ループを使用して階乗をプログラムできることは理解できたと思います。実際、この問題を解決する非再帰的な方法は次のとおりです。
Java-университет 
private int fact(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}
数値が正の整数であることのチェックと、ゼロの別のチェックを追加しましょう。 
private int fact(int n) {
    if (n < 0) {
        System.out.println("Зачем тебе факториал из отрицательного числа?");
         return null;
    }
    int result = 1;
    if (n == 0) {
        return result;
    }
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}
ここで、この問題を再帰的に解決するためのメソッド コードを示します。 
private int factorial(int n) {
    int result = 1;
    if (n == 1 || n == 0) {
        return result;
    }
    result = n * factorial(n-1);
    return result;
}
呼び出しの出力結果を見てみましょう。 
System.out.println(factorial(0));
System.out.println(factorial(1));
System.out.println(factorial(2));
System.out.println(factorial(3));
System.out.println(factorial(4));
System.out.println(factorial(5));
System.out.println(factorial(6));
期待値が得られます。 
1
1
2
6
24
120
720
素晴らしい出力を追加して、より大きな数値の階乗を計算してみましょう。 
private int factorial(int n) {
    int result = 1;

    if (n == 0) {
        System.out.print(" = ");
        return result;
    }
    if (n == 1) {
        System.out.print(" * 1 = ");
        return result;
    }

    System.out.print(n);
    if (n != 2) {
        System.out.print(" * ");
    }

    result = n * factorial(n-1);
    return result;
}


System.out.println(factorial(15) + "!");
この場合、15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! 再帰関数の使用は正当化され、安全です。私たちは再帰ブロックを終了するための条件を明確に定義しており、それが達成可能であると確信しています。負ではない整数値を入力し、その数値が 0 または 1 に等しい場合は、数値が大きい場合は結果を返します。 、結果に数値の関数を掛けますn-1。例として 3 の階乗を使用すると、次のようになります。 
factorial(3) внутри себя выполнит следующее:
	result = 3 * factorial(2); (рекурсивный вызов)

	factorial(2) внутри себя выполнит следующее:
		result = 2 * factorial(1); (рекурсивный вызов)

		factorial(1) вернет 1 (базис рекурсии)

	factorial(2) вернет 2 * 1

factorial(3) вернет 3 * 2 * 1
使用上の注意について：この機能の脆弱性は何ですか？メソッドにパラメータとして負の数値を指定した場合、チェックは 
if (n == 1 || n == 0) {
    return result;
}
意味をなさないので、自分自身を呼び続ける無限のサイクルに陥ることになります。非負性のチェックを追加する価値があります。 
if (n < 0) {
	System.out.println(«Зачем тебе факториал отрицательного числа?»);
	return null;
}
そしてすべてがうまくいくでしょう。 ある方法が他の方法と比較して優れている点は何ですか? 大きな違いがあるようには見えませんが、実際には、多くの再帰呼び出しはパフォーマンスとメモリ消費に悪影響を及ぼします。呼び出しスタックはほとんど制御できないリソースであり、同じ再帰関数を呼び出すためのさまざまな条件下では、このリソースに関連する問題が発生する場合と発生しない場合があります。反復 ( のようなサイクル) を使用して解決されるほとんどすべての問題は、for-each再帰的に解決することもできます。再帰の利点は読みやすさと書きやすさです。欠点については上で説明しました。「自分の足を撃つ」機会は幻ではありません。いわゆる「複雑な再帰」を使用する場合はさらに注意する必要があります: 関数は関数を呼び出すA()関数を呼び出しますこのような問題を解決するには、再帰がどのように機能するかを完全に理解する必要があります。このようなタスクの例: の値の計算。階乗は、上で説明したように、非負の整数のセットに基づいて定義されます。最後に解決策のコードを記載します。複雑な再帰は 2 つのメソッドで構成されます。 B()A()x^n/(n!) 
private double calculate(int x, int n) {
    return power(x, n) / n;
}
private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}
再帰に入るには、メソッドが使用されcalculate、メソッドがメソッドを呼び出しpower、さらにメソッドがメソッドを呼び出しますcalculate。べき乗法で再帰基底を定義しました。 
if (n == 1) return x;
再帰ステップもそこで定義されています。 
return x * calculate(x, n - 1);
入力データの有効性のチェックを追加する必要があります。
  • ゼロ以外の数値はゼロのべき乗に等しくなります1。の場合n = 0、n! = 1。返却する必要があります1。
  • ゼロの累乗はゼロに等しい。
  • 型の不確実性は考慮せず0^0、そのような入力データは無効なものとして受け入れます。
すべてのチェックを行うと、メソッドは次のようになります。 
private double calculate(int x, int n) throws ArithmeticException {
    if (x == 0 && n == 0) {
        throw new ArithmeticException("Невалидные входные данные: Неопределенность типа 0^0");
    }

    if (n < 0) {
        throw new ArithmeticException("Невалидные входные данные: Факториал из отрицательного числа!");
    }

    if (n == 0) {
        return 1;
    }

    if (x == 0) {
        return 0;
    }

    if (x == 0) {
        return 0;
    }
    return power(x, n) / n;
}

private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}
さて、関数を呼び出すときは、エラーをキャッチすることを忘れないでください。 
try {
    System.out.println(calculate(x, n));
} catch (ArithmeticException e) {
    System.out.println(e.getMessage());
}
コメント
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION