再帰 の観点から何かを定義するプロセスです自体。 Javaプログラミングに関連するように、再帰はメソッドがそれ自体を呼び出すことを可能にする属性です。自身を呼び出すメソッドは再帰的であり、Javaは再帰をサポートしています。
最初、これは終わりのないループのように見えるかもしれませんが、そして、私たちの方法は決して終わらないようです。場合によってはこれが当てはまることもありますが、実際には、特定の条件が当てはまるかどうかを確認し、その場合はメソッドを終了(復帰)できます。再帰を終了するケースは、 規範事例。さらに、ループと同じように、いくつかの値を変更して、徐々にベースケースに近づける必要があります。
すべての再帰には、次の特性が必要です。
- ソリューションと戻り値を持つ単純な基本ケース。
- 問題をベースケースに近づける方法。つまり、問題の一部を切り取って、やや単純な問題を取得する方法です。
- より単純な問題をメソッドに戻す再帰呼び出し。
メリット
再帰的な方法の主なものは、複数のアルゴリズムの反復親戚よりも明確で単純なバージョンを作成するために使用されます。たとえば、QuickSort並べ替えアルゴリズムは、反復的な方法で実装するのが非常に困難です。
短所
多くのルーチンの再帰バージョンは、追加の関数呼び出しのオーバーヘッドが追加されるため、同等の反復よりも少し遅くなります。メソッドへの多くの再帰呼び出しは、スタックオーバーランを引き起こす可能性があります。パラメータとローカル変数のストレージのため、スタックが使い果たされる可能性があります。これが発生すると、Javaランタイムシステムが例外を発生させます。ただし、再帰ルーチンが乱暴に実行されない限り、これについて心配する必要はないでしょう。
例えば:
int myFactorial(int integer) { if( integer == 1) { return 1; } else { return(integer*(myFactorial(integer-1); } }
テール再帰は、再帰呼び出しは、再帰命令の最後にあります。これは、上記の要因分解では当てはまりません。 onesアルゴリズムがテール再帰を使用する場合に注意することは有用です。そのような場合、アルゴリズムは通常、代わりに反復を使用するように書き直すことができるためです。実際、コンパイラーは再帰プログラムを反復プログラムに変換します(または少なくともそうする必要があります)。これにより、スタックオーバーフローの潜在的な問題が解消されます。
これは、ヘッドの再帰の場合、またはこの関数は、ハノイの塔ソリューションのように、さまざまな場所で再帰的に呼び出します。もちろん、これらの場合でも、独自のスタックを使用して再帰がどのように機能するかを本質的にシミュレートすることにより、再帰を削除することもできます。
コンパイラの上の階乗の私の例では乗算を完了する前に関数の(戻り)値を解決する必要があるため、乗算を実行する前に再帰関数を呼び出す必要があります。したがって、実行の順序は「先頭」の再帰になります。つまり、再帰は他の操作の前に発生します。
これを末尾再帰に変換するには、すべての乗算は終了し、関数を再帰的に呼び出す前に解決されました。戻る前に乗算を待たないように、演算の順序を強制する必要があります。これを行うと、スタックフレームを解放できます。
これまで、整数の階乗を計算するJavaプログラムを見てきました。
末尾再帰階乗を行う適切な方法は次のとおりです。
int factorial(int number) { if(number == 0) { return 1; } factorial_i(number, 1); } int factorial_i(int currentNumber, int sum) { if(currentNumber == 1) { return sum; } else { return factorial_i(currentNumber - 1, sum*currentNumber); } }
呼び出しの戻りに注意してくださいfactorial_i(currentNumber – 1、sum * currentNumber);どちらのパラメータもすぐに解決できます。再帰的な関数呼び出しが戻るのを待たずに、各パラメーターを計算できます。これは、factorialの以前のバージョンには当てはまりません。この合理化により、コンパイラーは上記で説明したようにスタックの使用を最小限に抑えることができます。
コマンドライン引数としてユーザーから番号を取得することもできます。
Java再帰プログラム
class Factorial{ int fact(int n){ int result; if ( n ==1) return 1; result = fact (n-1) * n; return result; } } class Recursion{ public static void main (String args[]){ Factorial f =new Factorial(); System.out.println("Factorial of 3 is " + f.fact(3)); System.out.println("Factorial of 4 is " + f.fact(4)); System.out.println("Factorial of 5 is " + f.fact(5)); } }
出力
Javaコードと出力の説明
再帰的な方法に慣れていない場合は、 事実() 少しわかりにくいかもしれません。これがどのように機能するかです。いつ 事実() 引数1で呼び出され、関数は1を返します。そうでなければ、それはの製品を返します fact(n-1)* n。 この式を評価するには 事実() と呼ばれる n-1。このプロセスが繰り返されるまで ん 1に等しく、メソッドの呼び出しが戻り始めます。
よりよく理解するために 事実() メソッドが機能するので、簡単な例を見てみましょう。 3の階乗を計算すると、最初の呼び出しは 事実() 引数2を使用して2回目の呼び出しが行われます。この呼び出しにより、 事実() 引数2で3回目に呼び出されます。 この呼び出しは1を返し、1を引数として3回目に呼び出されます。この呼び出しは1を返し、2を乗算します(の値 ん 2番目の呼び出しで)。次に、この結果(2)は、最初の呼び出しに戻されます。 事実() 3を掛けます(元の値 n)。 これで答えは6になります。挿入すると面白いかもしれません println() へのステートメント 事実() これは、各呼び出しがどのレベルであり、中間の応答が何であるかを示します。
メソッドがそれ自体を呼び出すと、新しいローカル変数パラメータはスタック上のストレージに割り当てられ、メソッドコードはこれらの新しい変数を使用して最初から実行されます。再帰呼び出しでは、メソッドの新しいコピーは作成されません。新しいのは引数のみです。各再帰呼び出しが戻ると、古いローカル変数とパラメーターがスタックから削除され、メソッド内の呼び出しの時点で実行が再開されます。
次に、対処方法を学びます Javaの配列.
Javaプログラミングに関するより有用なチュートリアルと明確なガイドラインをここで確認してください。
コメント