■ 再帰処理(Recursive processing)
* 繰り返し処理をスマートに実現するプログラミング・テクニック
勘所
1) 特定の引数(階乗の場合「0」、フィナボッチ数列の場合「先頭は0、次は1」)の場合は戻り値を確定しておく 2) 1) でない場合は、引数の値を変えて同じ関数を呼び出す →まずは、その処理の法則性を整理し、繰り返しの法則を見出し、その繰り返しを再帰にする
デメリット
関数を何度も呼び出すため... 1) For/While文と比較して処理が遅い 2) スタックオーバーフローのエラーを起こす可能性がある(関数の引数をスタックに積まれるので) (スタックについては、以下の関連記事を参照のこと)http://blogs.yahoo.co.jp/dk521123/34569082.html
スタックオーバーフローのエラー例
* 以下のプログラムのサンプルで「10000」を入力した際のエラー。割と簡単に起こるんだなー。。。http://blogs.yahoo.co.jp/dk521123/34536896.html
Exception in thread "main" java.lang.StackOverflowError at com.sample.recursive.FibonacciEx.calculate(FibonacciEx.java:32) at com.sample.recursive.FibonacciEx.calculate(FibonacciEx.java:40) at com.sample.recursive.FibonacciEx.calculate(FibonacciEx.java:40) ...
■ 階乗(factorial / ファクトリアル)
* 例:5 x 4 x 3 x 2 x 1 = 120 * 特徴「0の階乗は、1」「nの階乗は、n x (n - 1の階乗)」
サンプル
public class Factorial { public static void main(String[] args) { System.out.println("Result : " + Factorial.calculateFactorial(5)); } private static int calculateFactorial(int value) { if (value == 0) { return 1; } return value * Factorial.calculateFactorial(value - 1); } }
出力結果
Result : 120
■ フィナボッチ数列(Fibonacci Number)
* 例:0, 1, 1, 2, 3, 5, 8, 13, 21, ... * 特徴「先頭は0、次は1、以降は一つ前と二つ前の数を加算した数」
サンプル
public class Fibonacci { public static void main(String[] args) { System.out.println("Result : " + Fibonacci.calculateFibonacci(7)); } private static int calculateFibonacci(int value) { if (value == 0) { return 0; } else if (value == 1) { return 1; } return Fibonacci.calculateFibonacci(value - 1) + Fibonacci.calculateFibonacci(value - 2); } }
出力結果
Result : 13