日記: 再帰関数練習

// 再帰法は、再帰終了条件を持たなければならない。
// 再帰法は、状態を変えながら再帰終了条件に進んでいかなければならない。
// 再帰法は、再帰的に関数自身を呼び出さなければならない。

// 再帰呼び出しを行ったときの問題が、
//元の問題よりも小さな問題となるように再帰呼び出しを行い、
//そのような「より小さい問題の系列」が最終的にベースケースに辿り着くようにする

// 数を引きながらすべて足し合わせる再帰関数
function recAdd(n) {
  if (n == 0) return 0;
  return n + recAdd(n - 1);
}

console.log("n = 10", recAdd(10));

// フィボナッチ数を出す再帰関数
function fibo(n) {
  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  }
  return fibo(n - 1) + fibo(n - 2);
}

// メモ化したフィボナッチ数関数
let memo = [];

function fiboMemo(n) {
  if (memo[n] != null) {
    return memo[n];
  }

  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  }

  memo[n] = fiboMemo(n - 1) + fiboMemo(n - 2);

  return memo[n];
}

// かかった時間計測
let time = performance.now();
// 40項目までのフィボナッチ数列
for (let i = 0; i < 40; i++) {
  console.log("fiboMemo(" + i + ")", fiboMemo(i));
}
console.log("fiboMemo time", performance.now() - time);

// 部分和問題の関数
function bubun(i, x, a) {
  if (i === 0) {
    if (x === 0) return true;
    else return false;
  }

  // 選ばない場合
  if (bubun(i - 1, x, a)) return true;

  // 選んだ場合 選んだ数字をxから引く
  if (bubun(i - 1, x - a[i - 1], a)) return true;

  return false;
}

// メモ化
function bubunMemo(i, x, a, memo) {
  if (memo[i][x] != null) return memo[i][x];
  // 最終番の数字を引いたとき、ちょうど0ならtrue
  if (i === 0) {
    if (x === 0) return true;
    else return false;
  }

  // 選ばない場合
  if (bubunMemo(i - 1, x, a, memo)) {
    memo[i][x] = true;
    return memo[i][x];
  }

  // 選んだ場合
  if (bubunMemo(i - 1, x - a[i - 1], a, memo)) {
    memo[i][x] = true;
    return memo[i][x];
  }

  memo[i][x] = false;

  return memo[i][x];
}

time = performance.now();
let a = [3, 5, 1, 2, 9];
let x = 8;
console.log("a = ", a, " x = ", x, "bubun = ", bubun(a.length, x, a));
console.log("bubun time", performance.now() - time);

time = performance.now();
let memoB = new Array(x + 1).fill().map(() => []);
console.log("bubunMemo = ", bubunMemo(a.length, x, a, memoB));
console.log("bubunMemo time", performance.now() - time);


// グラフ

let graph;

function recG(v, graph, seen) {
  seen[v] = true;
  for (const next of graph[v]) {
    if (seen[next]) continue;
    recG(next, graph, seen);
  }
}
let N = 8; // 頂点数
graph = new Array(N);

// 例: graph[0] = [5]  0ノードから行けるノードは5
graph[0] = [5];
graph[1] = [3, 6];
graph[2] = [5, 7];
graph[3] = [0, 7];
graph[4] = [1, 2, 6];
graph[5] = [];
graph[6] = [7];
graph[7] = [0];

let seen = new Array(N).fill();

for (let v = 0; v < N; v++) {
  if (seen[v]) continue;
  recG(v, graph, seen);
}

// トポロジカルソート

function topo(v, graph, seen, order) {
  seen[v] = true;
  for (const next of graph[v]) {
    if (seen[next]) continue;

    topo(next, graph, seen, order);
  }
  order.push(v);
}

let seen2 = new Array(N).fill();
let order = [];

for (let v = 0; v < N; v++) {
  if (seen2[v]) continue;
  topo(v, graph, seen2, order);
}

console.log("トポロジカルソート:", order.reverse());