関数の再帰呼び出しを入れ子で図示して理解を深める

関数の再帰呼び出しを理解するのは、なかなか難しいです。
関数が自分自身を再度呼び出すので、入れ子になっているような図を書いて理解を深めるとよいです。

ハノイの塔の解を求める関数と再帰呼び出しの入れ子イメージ

ハノイの塔の解の求め方は、

• なんにせよ円盤nより小さい円盤(n-1)はいったんfromからworkに退避させて、
• 一番大きな円盤nをfromからtoに移動させ、
• 退避させた円盤(n-1)をworkからtoに移動させる

これを円盤の大きさをどんどん小さくさせて、同じことを繰り返させて(自分自身を再帰的に呼び出す)解いていきます。

次のように入れ子の図を書いてみると理解が深まります。

ハノイの塔の解を求める

1:const _hanoi=(n, from, to, work)=>{
2:  if (n === 1) {
3:    console.log(`円盤:${n}を杭${from}から杭${to}へ。`);
4:  } else {
5:    _hanoi(n - 1, from, work, to);
6:    console.log(`円盤:${n}を杭${from}から杭${to}へ。`);
7:    _hanoi(n - 1, work, to, from);
8:  }
9:};

次に示す階乗の解を求める関数の再帰呼び出しに比べて、ハノイの塔の解を求める関数の再帰呼び出しの難しいところは、5行と7行の関数再帰呼び出しに挟まれる形で、6行目のconsole.logがあるところ。2回も再帰呼び出しがあるのと、間に挟まれたconsole.logがどうなるのかよくわからなくなるところだと思います。

関数呼び出しを入れ子の図にして、その時の引数の状態を書き出してみると理解が深まります。

階乗の解を求める関数と再帰呼び出しの入れ子イメージ

次の図はfactorial(2)を求めるときに、どのような入れ子になっているかを図示しています。
そして、下階層の戻り値を元に現在階層の計算をしているところを矢印で示しています。

階乗の解を求める

1:const factorial=(n)=>{
2:  if (n === 0) {
3:    return 1;
4:  } else {
5:    return n * factorial(n-1);
6:  }
7:};