2024.12.19
再帰呼び出し
再帰呼び出しとは
再帰呼び出しは、メソッドの中で、そのメソッドを呼び出すことです。リカーシブコール(recursive call)とも呼ばれます。
「木構造の探索」、「迷路の探索」、「チェス／オセロゲームなどで最善の手を見つける」などデータをたどっていくような処理や、「クイックソート」などのように処理するグループを分割していくなどの処理に有効です。
それでは、具体例でみていきましょう。
004 005 006 007 008 009 010 011 012
// 1～nの和を再帰呼び出しで求める private static int sum( int n ) { // nが1以下の場合、nを戻す if ( 1 >= n ) return n; // 再帰呼び出しで、 nと1～(n-1)の和を求める return n + sum( n - 1 ); }
010 011
// 再帰呼び出しで、 nと1～(n-1)の和を求める return n + sum( n - 1 );
例えば「n = 5」の場合、「1～5の合計」は、
「1～5の合計」 = 5 + 「1～4の合計」
と考えることができます。
「1～4の合計」 = 4 + 「1～3の合計」 「1～3の合計」 = 3 + 「1～2の合計」 「1～2の合計」 = 2 + 「1」
になります。
「n = 5」のsumメソッドの呼び出しイメージは、
sum( 5 ) = 5 + sum( 4 ) sum( 4 ) = 4 + sum( 3 ) sum( 3 ) = 3 + sum( 2 ) sum( 2 ) = 2 + sum( 1 ) sum( 1 ) = 1 ← 引数がnが1の場合、sumは1を戻します。
となります。
sum( 1 )の値が１で確定すると、sum( 2 )の値が2+1=3で確定します。
sum( 3 )～sum( 5 )も以下のように値が確定していきます。
sum( 1 ) = 1 sum( 2 ) = 2 + sum( 1 ) = 2 + 1 = 3 sum( 3 ) = 3 + sum( 2 ) = 3 + 3 = 6 sum( 4 ) = 4 + sum( 3 ) = 4 + 6 = 10 sum( 5 ) = 5 + sum( 4 ) = 5 + 10 = 15
処理が終わるとsum( 5 )は「15」になります。
これが、再起呼び出しを使った1～Nの和の計算方法です。
再帰呼び出しのメリット・デメリット
ここでは、再帰呼び出しを使うメリットとデメリットについて記載します。
メリット
デメリット
・メモリの消費量が大きい。
Javaソースコード - １～Nのを求める
Recursion1.java
001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036
import java.util.Scanner; public class Recursion1 { // 1～nの和を再帰呼び出しで求める private static int sum( int n ) { // nが1以下の場合、nを戻す if ( 1 >= n ) return n; // 再帰呼び出しで、 nと1～(n-1)の和を求める return n + sum( n - 1 ); } // メイン public static void main( String[] args ) { // Scannerを作成 Scanner scan = new Scanner( System.in ); // 文字数の入力 System.out.println( "nを入力してください" ); int n = scan.nextInt(); // nが1以上かをチェック if ( 1 > n ) { System.out.println( "1以上のnを入力してください" ); return; } // 1～nの和を取得 int result = sum( n ); // 結果を出力 System.out.println( "1から" + n + "の和は、" + result ); } }
コンパイル ソースコードが「ANSI」の場合
C:\talavax\javasample>javac -encoding sjis Recursion1.java
コンパイル ソースコードが「UTF-8」の場合
C:\talavax\javasample>javac Recursion1.java
実行
C:\talavax\javasample>java Recursion1
実行例(1～5の和を求める)
nを入力してください 5 1から5の和は、15
Javaソースコード - Nの階乗を求める
Nの階乗 = N! = N × ( N - 1 ) × ( N - 2 ) × ( N - 3 ) × … × 1
Recursion2.java
001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036
import java.util.Scanner; public class Recursion2 { // nの階乗を求める private static int factorial( int n ) { // nが0以下の場合、1を戻す if ( 0 >= n ) return 1; // 再帰呼び出しで、 nの階乗を求める return n * factorial( n - 1 ); } // メイン public static void main( String[] args ) { // Scannerを作成 Scanner scan = new Scanner( System.in ); // 文字数の入力 System.out.println( "nを入力してください" ); int n = scan.nextInt(); // nが1以上かをチェック if ( 1 > n ) { System.out.println( "1以上のnを入力してください" ); return; } // nの階乗を取得 int result = factorial( n ); // 結果を出力 System.out.println( " nの階乗は、" + result ); } }
コンパイル ソースコードが「ANSI」の場合
C:\talavax\javasample>javac -encoding sjis Recursion2.java
コンパイル ソースコードが「UTF-8」の場合
C:\talavax\javasample>javac Recursion2.java
実行
C:\talavax\javasample>java Recursion2
実行例(5の階乗を求める)
nを入力してください 5 nの階乗は、120
再帰呼び出しを使う処理
以下は、再帰呼び出しを使う処理についての記事です。興味のある方は参考にしてください。
以上です。
関連コンテンツ
広告
