日記: 再帰関数練習

その他,日記,雑談

Qiitaに再帰関数の記事が上がっていた。

再帰関数を学ぶと、どんな世界が広がるかhttps://qiita.com/drken/items/23a4f604fa3f505dd5ad

ちょうど知りたいことで、段階的でわかりやすいと思った。アルゴリズムについて濃厚な記事を過去にも書いておられるようで、リンク先も合わせて読んでいくととても勉強になりそうだ。

模写しようと思った。とりあえず、数独飛ばしてグラフの探索まで。続きや、過去記事部分はまたやりたい。

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

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

// 数を引きながらすべて足し合わせる再帰関数
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());