■ 再帰処理（Recursive processing）

 * 繰り返し処理をスマートに実現するプログラミング・テクニック

勘所

1) 特定の引数（階乗の場合「0」、フィナボッチ数列の場合「先頭は0、次は1」）の場合は戻り値を確定しておく
2) 1) でない場合は、引数の値を変えて同じ関数を呼び出す
　→まずは、その処理の法則性を整理し、繰り返しの法則を見出し、その繰り返しを再帰にする

デメリット

関数を何度も呼び出すため...

1) For/While文と比較して処理が遅い
2) スタックオーバーフローのエラーを起こす可能性がある(関数の引数をスタックに積まれるので)
　（スタックについては、以下の関連記事を参照のこと）

 * 以下のプログラムのサンプルで「10000」を入力した際のエラー。割と簡単に起こるんだなー。。。

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

関連記事

【プログラム】 動的計画法 ～ フィボナッチ数列 を例にして～