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

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回続く理由がわかりません。

Accepted Answer

こんにちは。

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

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

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

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

Answer

以前、同じ構造の再帰関数の動作の流れを図示したことがあります。
C言語だし、関数名が違う、具体的な表示の仕方が違う…けれど関数の構造は同じです。見比べてください。
[C言語の関数再帰に関する疑問への私の回答](https://teratail.com/questions/249646#reply-361118)

処理の流れをイメージしてもらおうという回答は既にいくつかありますが、イメージの仕方は一つではないように思います。私のような描き方もある、ということで参考にしていただきたく、付け加えます。

Answer

もし下記のようにreturn;していれば、質問者のような動作になると思います。
```php
function test(n){
  console.log('Hello');

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

console.log('Bye');
}
```

Answer

このプログラムでは、`test`関数が自分自身を呼び出す「再帰」という仕組みを使っています。
具体的な流れを一つずつ説明します。

### 呼び出しの流れ

1. 最初に `test(2)` が呼ばれます。
2. 最初に `console.log('Hello')` が実行され、「Hello」と表示されます。
3. `n != 0` なので、`test(1)` がさらに呼ばれます。

---

今度は `test(1)` の中に入ります。

1. ここでも「Hello」が表示されます。
2. また `n != 0` なので、今度は `test(0)` が呼ばれます。

---

次に `test(0)` の中に入ります。

1. 再び「Hello」が表示されます。
2. 今度は `n == 0` なので、再帰呼び出しはありません。

この時点で初めて `console.log('Bye')` が実行され、「Bye」が出力されます。

`test(0)` の処理が終わると、ひとつ前の `test(1)` に戻ります。

---

`test(1)` に戻ったあとは、残っていた `console.log('Bye')` が実行されるので、また「Bye」が表示されます。その後、`test(1)` の処理も終わり、`test(2)` に戻ります。

最後に `test(2)` でも残っていた `console.log('Bye')` が実行され、再度「Bye」が表示されます。

---

### 図でまとめます

```
test(2)
├─ Hello
├─ test(1)
│   ├─ Hello
│   ├─ test(0)
│   │   ├─ Hello
│   │   ├─ Bye   <-- ここで1回目のBye
│   ├─ Bye       <-- ここで2回目のBye
├─ Bye           <-- ここで3回目のBye
```

---

### ポイント

- `test` 関数は、まず自分自身を呼び出し（再帰）、呼び出しから“戻ってきてから”「Bye」を出力する作りになっています。
- これにより、関数の呼び出しが終了（戻る）するたびに、その時の「Bye」が出力されます。
- このため、３回呼び出されているので「Bye」も３回出力される仕組みです。

---

### なぜ「Bye」が複数回出るのか？

「test」関数は、呼び出されるたびに必ず最後で「Bye」を出力します。
再帰によって何度も呼ばれているため、終了したときの回数だけ「Bye」が出力される、ということになります。

---

もし他にも気になることがあれば、どうぞご質問ください。

Answer

再帰というのは現在の処理を中断して関数内の最初の命令に戻ることを繰り返す動作を指すので、毎回残りの処理が”蓄積”されます
これは```test```を他の関数に置き換えれば理解できるでしょう
```
function test(n){
console.log('Hello');

if (n != 0) {
console.log(n - 1);
}

console.log('Bye');
}
```
```’Bye’```が表示されるのは```if```内の```console.log```が実行された後です
ではこの```console.log```が内部で複雑な演算を行い、実行が終了しない場合はどうでしょうか
当然```’Bye’```の表示は遅延します

再帰ではこれと同等のことが起きています
再帰の各ステップで、```if```内の```test```は演算を完了していません
そして```if```の後には```’Bye’```が待ち構えています

この中断が```n!=0```を満たして```if```をスキップし、```test```の演算を完全に終了させるまでに2回起きているので、蓄積された各ステップの消費毎に```console.log(‘Bye’)```が実行されます

Answer

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

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

二重再帰ではないのでシンプルですが、
関数としては、
```
Helloを出力して右へ(右からこちらに戻ってきたらByeを出力) -> Helloを出力して右へ(右からこちらに戻ってきたらByeを出力) -> Helloを出力してByeを出力
```

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

Answer

関数は 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

こんな感じでnをあわせて表示するとわかりやすいかもしれません
```javascript
function test(n){
  console.log(`Hello ${n}`);
if (n != 0) {
  test(n - 1);
}
console.log(`Bye ${n}`);
}
test(2);
```
子ネストから抜けたあと親のbyeに処理が流れる感じですね

呼び出しの流れ

図でまとめます

ポイント

なぜ「Bye」が複数回出るのか？

関連した質問