recursion java tutorial with examples
このJavaでの再帰に関する詳細なチュートリアルでは、例、タイプ、および関連する概念を使用して再帰とは何かについて説明します。また、再帰と反復についても説明します。
Javaでの以前のチュートリアルから、ループを宣言してから、一度に1つの要素を取得することにより、データ構造を反復的にトラバースする反復アプローチを見てきました。
また、1つのループ変数を保持し、ループ変数が条件を満たしているまでコードの一部を繰り返す条件付きフローも確認しました。関数呼び出しに関しては、関数呼び出しの反復アプローチも検討しました。
=> ここですべてのJavaチュートリアルを確認してください。
このチュートリアルでは、プログラミングへの別のアプローチ、つまり再帰的アプローチについて説明します。
学習内容：
Javaの再帰とは何ですか？
再帰は、関数またはメソッドがそれ自体を何度も呼び出すプロセスです。直接的または間接的に何度も呼び出されるこの関数は、「再帰関数」と呼ばれます。
再帰を理解するためのさまざまな例を見ていきます。それでは、再帰の構文を見てみましょう。
再帰構文
再帰を実装するメソッドには、2つの基本的な部分があります。
- 自分自身を呼び出すことができるメソッド呼び出し、つまり再帰的
- 再帰を停止する前提条件。
再帰メソッドを中断しないと、再帰が無限に実行され続け、スタックオーバーフローが発生するため、再帰メソッドには前提条件が必要であることに注意してください。
再帰の一般的な構文は次のとおりです。
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } 前提条件は基本条件とも呼ばれることに注意してください。基本条件については、次のセクションで詳しく説明します。
Javaでの再帰を理解する
このセクションでは、再帰プロセスを理解し、それがどのように行われるかを確認します。基本条件、スタックオーバーフローについて学習し、再帰などの詳細を使用して特定の問題を解決する方法を確認します。
再帰基本条件
再帰プログラムを作成するときは、最初に基本ケースのソリューションを提供する必要があります。次に、大きな問題を小さな問題で表現します。
として 例、 数の階乗を計算するという古典的な問題を取り上げることができます。数nが与えられると、nで表されるnの階乗を見つける必要があります。
次に、再帰を使用してn階乗（n！）を計算するプログラムを実装しましょう。
public class Main{ static int fact(int n) { if (n == 1) // base condition return 1; else return n*fact(n-1); } public static void main(String() args) { int result = fact(10); System.out.println('10! = ' + result); } }出力
このプログラムでは、条件（n<=1) is the base condition and when this condition is reached, the function returns 1. The else part of the function is the recursive call. But every time the recursive method is called, n is decremented by 1.
したがって、最終的にnの値は1または1未満になり、この時点でメソッドは値1を返すと結論付けることができます。この基本条件に到達し、関数は停止します。 nの値は、基本条件を満たす限り、何でもかまいません。
任意のウェブサイトからビデオをダウンロードするプログラム
再帰を使用した問題解決
再帰を使用する背後にある基本的な考え方は、小さな問題の観点から大きな問題を表現することです。また、再帰から抜け出すことができるように、1つ以上の基本条件を追加する必要があります。
これは、上記の階乗の例ですでに示されています。このプログラムでは、n階乗（n！）を小さい値で表現し、基本条件（n<=1) so that when n reaches 1, we can quit the recursive method.
再帰でのスタックオーバーフローエラー
メソッドまたは関数が呼び出されると、関数の状態がスタックに格納され、関数が戻ったときに取得されることを認識しています。スタックは再帰的メソッドにも使用されます。
ただし、再帰の場合、基本条件を定義しない場合や、基本条件に到達または実行されない場合に問題が発生する可能性があります。この状況が発生すると、スタックオーバーフローが発生する可能性があります。
以下の階乗表記の例を考えてみましょう。
ここでは、間違った基本条件、n == 100を指定しています。
public class Main { static int fact(int n) { if (n == 100) // base condition resulting in stack overflow return 1; else return n*fact(n-1); } public static void main(String() args) { int result = fact(10); System.out.println('10! = ' + result); } }したがって、n> 100の場合、メソッドは1を返しますが、再帰は停止しません。 nの値は、それを停止する他の条件がないため、無期限に減少し続けます。これは、スタックがオーバーフローするまで続きます。
別のケースは、nの値が<100. In this case, as well the method will never execute the base condition and result in a stack overflow.
Javaでの再帰の例
このセクションでは、再帰を使用して次の例を実装します。
携帯電話のための最高のスパイプログラム
＃1）再帰を使用したフィボナッチ数列
フィボナッチ数列は、によって与えられます、
1,1,2,3,5,8,13,21,34,55、..。
上記のシーケンスは、現在の要素が前の2つの要素の合計であることを示しています。また、フィボナッチ数列の最初の要素は1です。
したがって、一般に、nが現在の数である場合、（n-1）と（n-2）の合計で与えられます。現在の要素は前の要素で表されるため、再帰を使用してこの問題を表すことができます。
フィボナッチ数列を実装するためのプログラムを以下に示します。
public class Main { //method to calculate fibonacci series static int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); } public static void main(String() args) { int number = 10; //print first 10 numbers of fibonacci series System.out.println ('Fibonacci Series: First 10 numbers:'); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + ' '); } } } 出力
＃2）再帰を使用して数値が回文であるかどうかを確認する
回文は、左から右、または右から左に読んだときに等しいシーケンスです。
121という数字を考えると、左から右、右から左に読むと、等しいことがわかります。したがって、121番は回文です。
別の番号1242を見てみましょう。左から右に読むと1242で、右から左に読むと2421と表示されます。したがって、これは回文ではありません。
数字の桁を逆にして、指定された数字をその逆の表現と再帰的に比較することにより、回文プログラムを実装します。
以下のプログラムは、回文をチェックするプログラムを実装しています。
import java.io.*; import java.util.*; public class Main { // check if num contains only one digit public static int oneDigit(int num) { if ((num >= 0) && (num <10)) return 1; else return 0; } //palindrome utility function public static int isPalindrome_util (int num, int revNum) throws Exception { // base condition; return if num=0 if (num == 0) { return revNum; } else { //call utility function recursively revNum = isPalindrome_util(num / 10, revNum); } // Check if first digit of num and revNum are equal if (num % 10 == revNum % 10) { // if yes, revNum will move with num return revNum / 10; } else { // exit throw new Exception(); } } //method to check if a given number is palindrome using palindrome utility function public static int isPalindrome(int num) throws Exception { if (num < 0) num = (-num); int revNum = (num); return isPalindrome_util(num, revNum); } public static void main(String args()) { int n = 1242; try { isPalindrome(n); System.out.println('Yes, the given number ' + n + ' is a palindrome.'); } catch (Exception e) { System.out.println('No, the given number ' + n + ' is not a palindrome.'); } n = 1221; try { isPalindrome(n); System.out.println('Yes, the given number ' + n + ' is a palindrome.'); } catch (Exception e) { System.out.println('No, the given number ' + n + ' is not a palindrome.'); } } }出力
＃3）逆文字列再帰Java
文字列「Hello」が与えられた場合、結果の文字列が「olleH」になるように逆にする必要があります。
これは再帰を使用して行われます。文字列の最後の文字から始めて、文字列のすべての文字がなくなるまで、各文字を再帰的に印刷します。
以下のプログラムは、再帰を使用して特定の文字列を逆にします。
class String_Reverse { //recursive method to reverse a given string void reverseString(String str) { //base condition; return if string is null or with 1 or less character if ((str==null)||(str.length() <= 1)) System.out.println(str); else { //recursively print each character in the string from the end System.out.print(str.charAt(str.length()-1)); reverseString(str.substring(0,str.length()-1)); } } } class Main{ public static void main(String() args) { String inputstr = 'SoftwareTestingHelp'; System.out.println('The given string: ' + inputstr); String_Reverse obj = new String_Reverse(); System.out.print('The reversed string: '); obj.reverseString(inputstr); } } 出力
＃4）二分探索Java再帰
二分探索アルゴリズムは、検索のための有名なアルゴリズムです。このアルゴリズムでは、n個の要素の並べ替えられた配列が与えられた場合、この配列で指定されたキー要素を検索します。最初に、配列の中央要素を見つけることによって、配列を2つに分割します。
次に、キーが中央にあるかどうかに応じて、配列の前半または後半で検索を制限します。このようにして、重要な要素の場所が見つかるまで同じプロセスが繰り返されます。
ここでは、再帰を使用してこのアルゴリズムを実装します。
import java.util.*; class Binary_Search { // recursive binary search int binarySearch(int numArray(), int left, int right, int key) { if (right >= left) { //calculate mid of the array int mid = left + (right - left) / 2; // if the key is at mid, return mid if (numArray(mid) == key) return mid; // if key key) return binarySearch(numArray, left, mid - 1, key); // Else recursively search in the right subarray return binarySearch(numArray, mid + 1, right, key); } // no elements in the array, return -1 return -1; } } class Main{ public static void main(String args()) { Binary_Search ob = new Binary_Search(); //declare and print the array int numArray() = { 4,6,12,16,22}; System.out.println('The given array : ' + Arrays.toString(numArray)); int len = numArray.length; //length of the array int key = 16; //key to be searched int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println('Element ' + key + ' not present'); else System.out.println('Element ' + key + ' found at index ' + result); } } 出力
＃5）再帰を使用して配列内の最小値を見つける
再帰を使用して、配列内の最小値を見つけることもできます。
配列内の最小値を見つけるJavaプログラムを以下に示します。
import java.util.*; class Main { static int getMin(int numArray(), int i, int n) { //return first element if only one element or minimum of the array elements return (n == 1) ? numArray(i) : Math.min(numArray(i), getMin(numArray,i + 1 , n - 1)); } public static void main(String() args) { int numArray() = { 7,32,64,2,10,23 }; System.out.println('Given Array : ' + Arrays.toString(numArray)); int n = numArray.length; System.out.print('Minimum element of array: ' + getMin(numArray, 0, n) + '
'); } }出力
これらは再帰の例の一部です。これらの例とは別に、ソフトウェアの他の多くの問題は、再帰的手法を使用して実装できます。
再帰タイプ
再帰には、再帰メソッドがいつ呼び出されるかに基づいて2つのタイプがあります。
彼らです：
＃1）末尾再帰
再帰メソッドの呼び出しが再帰メソッド内で実行される最後のステートメントである場合、それは「末尾再帰」と呼ばれます。
末尾再帰では、再帰呼び出しステートメントは通常、メソッドのreturnステートメントと一緒に実行されます。
末尾再帰の一般的な構文を以下に示します。
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } ＃2）ヘッド再帰
頭の再帰は、末尾の再帰ではない再帰的なアプローチです。したがって、一般的な再帰でさえ、再帰よりも先になります。
ヘッド再帰の構文は次のとおりです。
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Javaでの再帰と反復
| 再帰 | 反復 |
|---|---|
| 時間計算量は非常に高いです。 | 時間の複雑さは比較的低い側にあります。 |
| 再帰は、基本条件が満たされるまでメソッドがそれ自体を繰り返し呼び出すプロセスです。 | 反復は、コードの一部が有限回数、または条件が満たされるまで繰り返し実行されるプロセスです。 |
| 関数のアプリケーションです。 | ループに適用できます。 |
| コードサイズが小さい場合に適しています。 | コードサイズが大きい場合に適しています。 |
| 各再帰呼び出しがスタックにプッシュされると、より多くのメモリを使用します | 使用されるメモリは比較的少なくなります。 |
| デバッグと保守が難しい | デバッグと保守が容易 |
| 基本条件が指定されていないか、到達していない場合、スタックオーバーフローが発生します。 | 無限に実行される可能性がありますが、メモリエラーが発生すると最終的に実行が停止します |
よくある質問
Q＃1）Javaで再帰はどのように機能しますか？
回答： 再帰では、再帰関数は基本条件が満たされるまで自分自身を繰り返し呼び出します。呼び出された関数のメモリは、呼び出し元の関数のメモリの最上位にあるスタックにプッシュされます。関数呼び出しごとに、ローカル変数の個別のコピーが作成されます。
Q＃2） なぜ再帰が使用されるのですか？
回答： 再帰は、小さな問題に分解できる問題を解決するために使用され、問題全体を小さな問題で表すことができます。
再帰は、反復アプローチを使用して解決するには複雑すぎる問題にも使用されます。時間の複雑さが問題にならない問題に加えて、再帰を使用します。
Q＃3） 再帰の利点は何ですか？
回答：
再帰の利点は次のとおりです。
- 再帰は、関数の冗長な呼び出しを減らします。
- 再帰的アプローチを使用すると、反復アプローチと比較して問題を簡単に解決できます。
Q＃4）再帰と反復のどちらが良いですか？
回答： 再帰は、基本関数に到達するまで繰り返し呼び出しを行います。したがって、各関数呼び出しのメモリがスタックにプッシュされるため、メモリのオーバーヘッドが発生します。
Javaランタイム環境でjarファイルを開く方法
一方、反復にはメモリのオーバーヘッドはあまりありません。再帰の実行は、反復アプローチよりも遅くなります。再帰はコードのサイズを縮小しますが、反復アプローチはコードを大きくします。
Q＃5） 反復に対する再帰の利点は何ですか？
回答：
- 再帰により、コードがより明確で短くなります。
- 再帰は、ハノイの塔、ツリートラバーサルなどの問題に対する反復アプローチよりも優れています。
- すべての関数呼び出しでメモリがスタックにプッシュされるため、再帰はより多くのメモリを使用します。
- 再帰のパフォーマンスは、反復アプローチよりも遅くなります。
結論
再帰は、プログラミング言語に関係なく、ソフトウェアで非常に重要な概念です。再帰は主に、ハノイの塔、ツリートラバーサル、リンクリストなどのデータ構造の問題を解決するために使用されます。より多くのメモリが必要ですが、再帰によってコードがより単純で明確になります。
このチュートリアルでは、再帰についてすべて説明しました。また、概念をよりよく理解するために、多数のプログラミング例を実装しました。
=> EasyJavaトレーニングシリーズをお読みください。
推奨読書
- C ++での再帰
- Javaイテレータ：例を使用してJavaでイテレータを使用する方法を学ぶ
- 例を使用したJavaのListIteratorインターフェイス
- 初心者向けのJAVAチュートリアル：100以上の実践的なJavaビデオチュートリアル
- プログラム例を含むJavaForループチュートリアル
- JavaWhileループ-プログラミング例を含むチュートリアル
- Java DoWhileループ-例を含むチュートリアル
- Javaのギザギザの配列-例を含むチュートリアル