Rainbow U

(ver0.5)

再帰関数の使いどころ、考え方がよくわからんかったけど、これのp35と36読んでぼんやりわかったような気がしたのでメモ。
動的計画法を使わずに再帰関数を使ったときの計算量は、O(再帰関数の中で呼ばれている再帰関数の数^n)の予感。
想定されるケースのうち、適当に具体的な1つのケースを思い浮かべて、そこから遷移、変化できるケースへの橋渡しに再帰関数の引数を変えて呼び出すイメージで考える。
動的計画法は、再帰関数の引数と添字を対応した配列を用意して、そこに保存したり呼び出したりする。
下記は例。普段javaを書かないので間違ってるかもしれない。

memo = new int[n];
public Integer fibo(int n){
  if (a <= 1) {
    return n;
  }
  if(memo[n] != 0){
    return memo[n];
  }
  memo[n] = fibo(n-1) + fibo(n-2);
  return memo[n];
}