このチュートリアルでは、Javaの再帰について、例、型、および関連する概念で再帰とは何ですか説明します。 また、再帰と反復をカバーしています：
これまでのJavaのチュートリアルで、ループを宣言し、一度に1つの要素を取ることでデータ構造を反復的に走査する反復アプローチについて見てきましたが、今回は、ループを宣言し、データ構造を反復的に走査する反復アプローチを紹介します。
また、条件付きフローでは、1つのループ変数を保持し、そのループ変数が条件を満たすまでコードを繰り返します。 関数呼び出しに関しては、関数呼び出しの反復的アプローチも検討しました。
このチュートリアルでは、プログラミングの異なるアプローチ、すなわちRecursiveアプローチについて説明します。
Javaにおける再帰とは？
再帰とは、関数やメソッドが自分自身を何度も呼び出すことであり、このように直接または間接的に何度も呼び出される関数を「再帰関数」と呼びます。
再帰を理解するために、様々な例を見ていきます。 では、再帰の構文を見ていきましょう。
再帰の構文
Recursionを実装したメソッドは、基本的に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) // 基本条件 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）が基本条件で、この条件に達すると関数が1を返すことがわかります。 関数のelse部分は再帰呼び出しです。 しかし、再帰メソッドを呼び出すたびにnは1ずつデクリメントされています。
したがって、最終的にnの値は1以下になり、この時点でメソッドは値1を返すと結論づけることができます。 この基本条件に達して、関数は停止します。 nの値は、基本条件を満たす限り、何でもよいことに注意してください。
再帰を用いた問題解決
再帰の基本的な考え方は、大きな問題を小さな問題で表現することです。 また、再帰から抜け出せるように、1つ以上の基本条件を追加する必要があります。
このことは、上記の階乗の例ですでに実証済みである。 このプログラムでは、nの階乗（n！）を小さい値で表現し、nが1になったら再帰法をやめるように、基本条件（n <=1） を設けていた。
再帰のスタックオーバーフローエラー
私たちは、何らかのメソッドや関数が呼び出されると、その状態がスタックに保存され、関数が戻るときに取り出されることを認識しています。 スタックは、再帰的メソッドにも使用されます。
しかし、再帰の場合、基本条件を定義していなかったり、何らかの原因で基本条件に到達しなかったり、実行されなかったりすると、スタックオーバーフローが発生する可能性があります。
以下、階乗表記の例で考えてみましょう。
ここでは、n==100という間違った基本条件を与えています。
public class Main { static int fact(int n) { if (n == 100) // スタックオーバーフローを引き起こす基本条件 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の値は、他に止める条件がないため、無限に減り続けます。 これは、スタックが溢れるまで続くでしょう。
この場合も、基本条件が実行されず、スタックオーバーフローとなります。
Javaでの再帰の例
本節では、以下の例題を再帰を使って実装する。
#その1）再帰を利用したフィボナッチ級数
フィボナッチ級数は次式で与えられる、
1,1,2,3,5,8,13,21,34,55,…
上記の配列は、現在の要素が前の2つの要素の合計であることを示しています。 また、フィボナッチ級数の最初の要素は、1であることを示しています。
つまり、一般にnを現在の数とすると、（n-1）と（n-2）の和で与えられる。 現在の要素は以前の要素で表されるので、この問題を再帰を使って表現することができる。
フィボナッチ級数を実現するプログラムを以下に示します：
public class Main { //フィボナッチ級数の計算方法 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; //フィボナッチ級数の最初の10個をプリント System.out.println ("Fibonacci Series: First 10 numbers:"); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i)+" ")； 出力
#その2）再帰を使って数字が回文であるかどうかを調べる
回文とは、左から右に読んでも、右から左に読んでも同じになる配列のことです。
121という数字があったとき、左から右へ、右から左へ読むと同じになることがわかります。 したがって、121という数字は回文であることがわかります。
左から右に読むと1242、右から左に読むと2421となり、これは回文ではない。
数字の桁を反転させ、与えられた数字とその反転表現を再帰的に比較することで、回文プログラムを実現する。
以下のプログラムは、回文をチェックするプログラムを実装したものです。
import java.io.*; import java.util.*; public class Main { // numが1桁しか含まないかチェック public static int oneDigit(int num) { if ((num>= 0) && (num <10)) return 1; else return 0; } //パリンドロームユーティリティ関数 public static int isPalindrome_util (int num, int revNum) throws Exception { // ベース条件； return if num=0 if (num == 0) { return revNum; } else { //コールユーティリティ関数 revNum = isPalindrome_util(num / 10, revNum); } // num と revNum の一桁目が等しいかどうかをチェック if (num % 10 == revNum % 10) { // yes なら revNum は num とともに移動 return revNum / 10; } else { // exit throw new Exception(); } } //回文ユーティリティ関数を使って与えられた数が回文かどうかを調べるメソッド public static int isPalindrome(int num) throwsException { 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, given number " + n + " is a palindrome."); } catch (Exception e) { System.out.println( "No, given number " + n + " is not a palindrome."); } n = 1221; try { isPalindrome(n)；System.out.println("Yes, given number " + n + " is a palindrome."); } catch (Exception e) { System.out.println("No, given number " + n + " is not a palindrome."); } } }. 出力
#その3）文字列の逆再生 Java
文字列 "Hello "が与えられたら、それを反転させて、結果の文字列が "olleH "になるようにしなければなりません。
文字列の最後の文字から始めて、文字列のすべての文字を使い切るまで、再帰的に各文字を表示します。
次のプログラムは、再帰を使って与えられた文字列を反転させるものです。
class String_Reverse { //与えられた文字列を反転させる再帰的メソッド void reverseString(String str) { //基本条件; 文字列がNULLか1文字以下の場合に返す if ((str==null))} } 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 { // 再帰的バイナリ検索 int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { //配列の中点を計算 int mid = left + (right - left) / 2; // midにキーが入っていれば、midを返す if (numArray[mid] == key) return mid; // if key キー） return binarySearch(numArray, left, mid - 1, key); // Else recursively search in this case.右のサブ配列 return binarySearch(numArray, mid + 1, right, key); } // 配列に要素がない場合は -1 return -1; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //配列を宣言して表示 int numArray[] = { 4,6,12,16,22}; System.out.println("The given array : " + Arrays.toString(numArray)); int len = numArray.length; //配列の長さを表すint key = 16; //検索するキー 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) { //要素が1つだけの場合は最初の要素を返し、配列要素の最小値を返す 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) + "\n"); } } }. 出力
これらの例以外にも、ソフトウェアにおける様々な問題を再帰的な手法で実装することができます。
再帰の種類
再帰は、再帰メソッドを呼び出すタイミングによって2種類に分かれる。
それらは
#その1）テールリカーシオン
再帰メソッドの呼び出しが、再帰メソッド内部で実行される最後の文である場合、「テール再帰」と呼ばれます。
末尾再帰では、通常、メソッドのreturn文とともに再帰呼び出し文が実行される。
尾部再帰の一般的な構文を以下に示します：
methodName ( T parameters ...){ { if (base_condition == true) { return result; } return methodName (T parameters ...) //tail recursion }. #その2）ヘッドリカーシオン
頭再帰とは、末尾再帰でない再帰的手法のこと。 つまり、一般再帰も頭再帰である。
頭部再帰の構文は以下の通りです：
methodName (Tパラメータ...){ if (some_condition == true) { return methodName (Tパラメータ...); } return result; }. Javaにおける再帰と反復の比較
| リカーシオン | イテレーション |
|---|---|
| 再帰とは、あるメソッドが基本的な条件が満たされるまで、繰り返し自分自身を呼び出す処理のことです。 | イテレーションとは、あるコードの一部を有限の回数、またはある条件が満たされるまで繰り返し実行する処理のことです。 |
| 機能に関するアプリケーションか。 | ループに適用されます。 |
| コードサイズを小さくしてもうまくいく。 | 大きなコードサイズでも問題なく動作します。 |
| 再帰呼び出しのたびにスタックにプッシュされるため、より多くのメモリを使用します。 | 比較的少ないメモリ使用量で済みます。 |
| デバッグやメンテナンスが難しい | デバッグやメンテナンスがしやすい |
| 基本条件が指定されていない、または到達していない場合、スタックオーバーフローになる。 | 無限に実行可能だが、メモリエラーが発生した場合は最終的に実行を停止する。 |
| 時間的な複雑さは非常に高い。 | 時間の複雑さは比較的低い方だと思います。 |
よくある質問
Q #1）Javaで再帰はどのように機能するのですか？
答えてください： 再帰では、基本条件が満たされるまで、再帰関数が自分自身を繰り返し呼び出します。 呼び出された関数のメモリは、呼び出し関数のメモリの一番上にあるスタックに押し込まれます。 関数呼び出しごとに、ローカル変数の個別のコピーが作成されます。
Q #2) なぜ再帰が使われるのか？
答えてください： 再帰は、問題をより小さな問題に分解することができ、問題全体がより小さな問題で表現できるような問題を解くために使われます。
再帰は、反復的なアプローチで解くには複雑すぎる問題にも使われます。 時間の複雑さが問題にならない問題以外にも、再帰を使いましょう。
Q #3) Recursionの利点は何ですか？
答えてください：
Recursionの利点は以下の通りです：
- 再帰は、関数の冗長な呼び出しを減らすことができます。
- 再帰は、反復的なアプローチと比較すると、簡単に問題を解決することができます。
Q #4) RecursionとIterationはどちらが優れていますか？
答えてください： 再帰では、ベースとなる関数に到達するまで繰り返し呼び出すため、関数呼び出しごとにメモリがスタックにプッシュされ、メモリのオーバーヘッドが発生します。
一方、反復はメモリのオーバーヘッドがあまりありません。 再帰の実行は反復アプローチより遅いです。 再帰はコードのサイズを小さくしますが、反復アプローチはコードを大きくします。
Q #5) 反復処理に対する再帰処理の利点は何ですか？
答えてください：
- 再帰は、コードをより明確に、より短くします。
- ハノイの塔や木のトラバーサルなどの問題では、反復的なアプローチよりも再帰の方が優れています。
- 関数呼び出しのたびにメモリがスタックにプッシュされるため、再帰はより多くのメモリを使用します。
- 再帰の性能は反復のアプローチより遅いです。
結論
再帰は、プログラミング言語に関係なく、ソフトウェアにおいて非常に重要な概念です。 再帰は、ハノイの塔、木のトラバーサル、リンクリストなどのデータ構造の問題を解く際に主に使われます。 より多くのメモリを消費しますが、再帰はコードをよりシンプルでクリアにします。
このチュートリアルでは、Recursion（再帰）の概念をより深く理解するために、数多くのプログラミングの例を挙げています。