木構造　フィボナッチ数列を例に

フィボナッチ数列

フィボナッチ数列のn番目の数を求めるプログラムを以下とします

test.js

function fib(n){
    // ベースケース
    if(n == 0) {
        return 0;
    } else if(n == 1) {
        return 1;
    }

    return fib(n - 1) + fib(n - 2);
}

console.log(fib(4))

https://zenn.dev/417yr/articles/f732588bd043da
https://zenn.dev/417yr/articles/fa4001ca84dd08
https://zenn.dev/417yr/articles/80cf5ba2dae627

木構造とコールスタック

• 木構造を用いて、コールスタックを図示することができる
  • コールスタックを図示しているだけなので当然、関数が優先され演算子が後回しとなる
• 1つの丸から2つに枝分かれしていることから分かるように、
  フィボナッチ数列は2つの再帰関数を呼び出している

• 木の高さと、
  コールスタックの積み上がった高さは一致する
  

アルゴリズムの種類

• 深さ優先探索（depth-first search, DFS）

  • 木の末端から処理が実行されるアルゴリズム
  • コールスタックのデータ構造である、LIFO（Last In First Out）に基づいている
    ↕︎

• 幅優先探索（breadth first search）

  • 木の頂点から近い順に処理が実行されるアルゴリズム