再帰関数の使い方でわからない記述がありました。

Question

function test(n){
console.log('Hello');

if (n != 0) {
test(n - 1);
}

console.log('Bye');
}

test(2);

このコードでどうして、

Hello
Hello
Hello
Bye
Bye
Bye

とByeが3回続くのでしょうか。
console.log('Bye')を1度実行してtest関数は終了かと思ったのですが、Byeが3回続く理由がわかりません。

Comments

[Lhankor_Mhy]

https://jsflow.info/?hl=ja
などのJS実行ビジュアル化ツールを使うといいかもしれません。

Answer 1

自分は再帰関数はスタックを強く頭に思い浮かべます。
言語化するならスタックされた処理は途中でふわっと消えることはありません。

書き起こすときは樹形図を書いて
左から右へ進み、returnで右から左に戻るように一つ一つ追います。

二重再帰ではないのでシンプルですが、
関数としては、

Helloを出力して右へ(右からこちらに戻ってきたらByeを出力) -> Helloを出力して右へ(右からこちらに戻ってきたらByeを出力) -> Helloを出力してByeを出力

というように、左の処理が右に行って最後まで行ったら左に一つずつ戻ります。
(これを樹形図と呼ぶのか知りませんが)

Answer 2

関数は console.log('Bye') を実行したら終了しますが、その関数を呼び出した親の関数はまだ終了していません。親の関数も自分の console.log('Bye') を実行する必要があります。これが「スタック」と呼ばれる仕組みで、関数呼び出しは後入れ先出し(LIFO)で処理されます。

1. test(2) 開始
   ├─ console.log('Hello')  → "Hello" 出力
   ├─ n=2なので test(1) を呼び出す
   │  
   │  2. test(1) 開始
   │     ├─ console.log('Hello')  → "Hello" 出力
   │     ├─ n=1なので test(0) を呼び出す
   │     │
   │     │  3. test(0) 開始
   │     │     ├─ console.log('Hello')  → "Hello" 出力
   │     │     ├─ n=0なので再帰呼び出しはしない
   │     │     └─ console.log('Bye')  → "Bye" 出力
   │     │  3. test(0) 終了 ← ここで test(1) に戻る
   │     │
   │     └─ console.log('Bye')  → "Bye" 出力
   │  2. test(1) 終了 ← ここで test(2) に戻る
   │
   └─ console.log('Bye')  → "Bye" 出力
1. test(2) 終了

Answer 3

こんにちは。

可能な限りシンプルに説明してみます。
test 関数の処理を言葉で表すと、

1. まず Hello を出力し、
2. (条件が合えば) test を呼び出し、
3. 最後に Bye を出力する

という一連の処理だと言えます。
つまり、test が呼び出されると、必ず Hello と Bye がペアで出力されるわけですね。
そして、その Hello と Bye の間に test 関数が呼ばれることがあるので、そこでも Hello と Bye のペアが出力されることになります。
なので、test 関数を再帰で呼んでいる限り、「Hello と Bye は同じ個数出力される」ことが分かるのです。

もしかしたら、test 関数の実装を「条件が合えば test 関数を呼び出す、そうでなければ Bye を出力する」と読み違えたのではないかなと勝手に想像しました。

Answer 4

こんな感じでnをあわせて表示するとわかりやすいかもしれません

function test(n){
  console.log(`Hello ${n}`);
if (n != 0) {
  test(n - 1);
}
console.log(`Bye ${n}`);
}
test(2);

子ネストから抜けたあと親のbyeに処理が流れる感じですね