■ はじめに
http://blogs.yahoo.co.jp/dk521123/34536714.html
で再帰を使ったフィボナッチ数列の処理は、同じ処理を何度か呼び出すといった無駄な部分がある
例：再帰処理で、5番目のフィボナッチ数を計算した場合
calculateFibonacci(5) => 3 + 2
|
+-> calculateFibonacci(4) => 2 + 1
| |
| +-> calculateFibonacci(3) => 1 + 1（★1）
| | |
| | +-> calculateFibonacci(2) => 1 + 0（★）
| | | |
| | | +-> calculateFibonacci(1) => 1（★）
| | | +-> calculateFibonacci(0) => 0（★）
| | +-> calculateFibonacci(1) => 1（★）
| +-> calculateFibonacci(2) => 1 + 0（★）
|
+-> calculateFibonacci(3) => 1 + 1（★2）
|
+-> calculateFibonacci(2) => 1 + 0（★）
| |
| +-> calculateFibonacci(1) => 1（★）
| +-> calculateFibonacci(0) => 0 （★）
+-> calculateFibonacci(1) => 1（★）
* 注目すべき、calculateFibonacci(3)～calculateFibonacci(0)は同じ処理を行っている。
1回処理すれば、後は使いまわせばいい。
例えば、calculateFibonacci(3)の計算を（★1）で行って結果を保持していたら、
（★2）で計算するときにそのままその計算結果を使えば、以降の呼び出しはしなくてすむ。
■ サンプル
* 動的計画法 と 再帰 を組み合わせて、フィナボッチ数列を実装してみる
フィナボッチ数列（Fibonacci Number）
import java.util.ArrayList;
import java.util.List;
public class FibonacciEx {
/** まだ計算していない事を示す値 */
private static final int NOT_RESULT_YET = -1;
private int valueOfFibonacci;
/** 結果をため込んで置くリスト */
private List<Integer> resultsOfFibonacci;
public FibonacciEx(int value) {
this.valueOfFibonacci = value;
this.resultsOfFibonacci = new ArrayList<>(value);
for (int i = 0; i <= value; i++) {
// 値を予め初期化しておく
this.resultsOfFibonacci.add(NOT_RESULT_YET);
}
}
public static void main(String[] args) {
FibonacciEx fibonacci = new FibonacciEx(7);
System.out.println("Result : " + fibonacci.calculate());
}
private int calculate() {
return this.calculate(this.valueOfFibonacci);
}
private int calculate(int value) {
int result = this.resultsOfFibonacci.get(value);
if (result == NOT_RESULT_YET) {
// ここはもう再帰処理で行った事と同じ
if (value == 0) {
result = 0;
} else if (value == 1) {
result = 1;
} else {
result = this.calculate(value - 1) + this.calculate(value - 2);
}
// 結果を保持しておく
this.resultsOfFibonacci.set(value, result);
}
return result;
}
}
