Pythonで〇×ゲームのAIを一から作成する　その100　再帰呼び出しによる繰り返し処理の性質

# 目次と前回の記事

https://qiita.com/ysgeso/items/2381dd4e3283cbed49a0

https://qiita.com/ysgeso/items/db7cfe4a1f14d9cb9368

## これまでに作成したモジュール

以下のリンクから、これまでに作成したモジュールを見ることができます。

| リンク | 説明 |
|:--|:--|
| [marubatsu.py](https://github.com/ysgeso/marubatsu/blob/master/100/marubatsu.py)  | Marubatsu、Marubatsu_GUI クラスの定義|
| [ai.py](https://github.com/ysgeso/marubatsu/blob/master/100/ai.py)  |  AI に関する関数 |
|  [util.py](https://github.com/ysgeso/marubatsu/blob/master/100/util.py) |  ユーティリティ関数の定義。現在は `gui_play` のみ定義されている |
| [tree.py](https://github.com/ysgeso/marubatsu/blob/master/100/tree.py)  | ゲーム木に関する Node、Mbtree クラスの定義  |
| [gui.py](https://github.com/ysgeso/marubatsu/blob/master/100/gui.py)  |  GUI に関する処理を行う基底クラスとなる GUI クラスの定義  |

## ルールベースの AI の一覧

ルールベースの AI の一覧については、下記の記事を参照して下さい。

https://qiita.com/ysgeso/items/10d1d01192c014173e4b

# 再帰呼び出し

[前回の記事](https://qiita.com/ysgeso/items/db7cfe4a1f14d9cb9368#%E5%86%8D%E8%B5%B7%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97%E3%82%92%E4%BD%BF%E7%94%A8%E3%81%97%E3%81%AA%E3%81%84%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E3%82%B2%E3%83%BC%E3%83%A0%E6%9C%A8%E3%81%AE%E4%BD%9C%E6%88%90)では、再帰呼び出しを使用せずに深さ優先アルゴリズムでゲーム木を作成する方法を紹介しましたが、__深さ優先アルゴリズム__ は __再帰呼び出しを使用するのが一般的__ です。

そこで、今回の記事では、再帰呼び出しとはどのような処理であるかについて説明します。

## 再帰呼び出しとは何か

__再帰呼び出し（recursive call）__ とは、__関数の中で自分自身を呼び出す処理__ の事です。

下記のプログラムは、関数 `f` の中で、自分自身を呼び出しているので再帰呼び出しです。

```python
def f():
    f()
```

下記のプログラムは、関数 `g` の中では直接自分自身を呼び出してはいませんが、`g` から呼び出された `h` の中で `g` を呼び出しているので、__`g` が行う処理__ によって、__自分自身が呼び出されています__。従って、__関数 `g` は再帰呼び出しを行っています__。

```python
def g():
    h()

def h():
    g()
```

なお、上記の関数 `f` や `g` を実際に実行するとどうなるかについては、後で説明します。

## 再帰呼び出しが行う処理の意味

関数の中で、自分自身を呼び出すということは、その関数の処理を __もう一度実行する__ ということを意味します。

例えば、先ほど定義した関数 `f` を呼び出すと、以下のような処理が行われます。

* 関数 f を呼び出すと、1 回目の関数 `f` のブロックの処理が開始される
* 1 回目の関数 `f` の処理の中で、2 回目の関数 `f` が呼び出される
* 2 回目の関数 `f` の処理の中で、3 回目の関数 `f` が呼び出される
* 3 回目の関数 `f` の処理の中で、4 回目の関数 `f` が呼び出される
* 上記の処理が無限に繰り返される

上記からわかるように、再帰呼び出しは、再帰呼び出しが行われる関数に対する __繰り返しの処理__ と考えることができます。先ほどの関数 `f` は無限ループを行う繰り返し処理です。

:::note warn
__再帰呼び出しは__ 、再帰呼び出しが行われる関数に対する __繰り返し処理__ である。
:::

## 再帰呼び出しを利用しない繰り返し処理

これまでの記事では、__for 文__ と __while 文__ を使った繰り返し処理を何度も記述してきました。それらの __繰り返し処理__ では、__共通して下記のような処理が行われます__。

* 繰り返し処理を行う前の __初期設定__ を行う
    * for 文の場合は、in の直後の反復可能オブジェクトの記述が初期設定に含まれる
* 特定の条件が満たされる間、for 文や while 文の __ブロックの処理を繰り返す__
    * for 文の場合は、in の直後の反復可能オブジェクトからデータを取り出す処理も、繰り返しの処理の中に含まれる
* 繰り返し処理の __続行の条件__ は以下の通りである
    * for 文の場合は in の直後の反復可能オブジェクトから取り出すデータが尽きるまで
    * while 文の場合は、while の直後の条件式が `True` であること
* 上記以外での繰り返し処理の __終了の条件__ は以下の通りである
    * ブロックの中で break 文が実行されると繰り返しの処理が終了する
    * 関数の中で繰り返し処理が記述されている場合は、return 文で関数の処理を終了することでも、繰り返しの処理が終了する

### for 文による繰り返し処理

下記は、__for 文__ を使って、__0 から 9 までの整数の合計を計算__ するプログラムです。2 行目には `range(10)` と記述しても構いませんが、0 から 10 未満までの整数を、1 ずつ増やしながら取り出すことを明確にするために `range(1, 10, 1)` と記述しました。

```python
total = 0
for i in range(0, 10, 1):
    total += i

print(total)
```

実行結果

```
45
```

上記では、__初期設定__ として、下記のような処理が行われます。`range(0, 10, 1)` の __最初の実引数 `0`__ は、初期設定として __`i` を `0` で初期化する__ という処理と考えることができます。

* 合計を計算するための変数 __`total` を `0` で初期化__ する
* __0 から整数を順番に数えるため__ に <code>range(<strong>0</strong>, 10, 1)</code> を for 文の in の直後に記述する

__繰り返して行われる処理__ は以下の通りです。

* __`total` に `i` を加算__ する
* `range(0, 10, 1)` から次の値を取り出して `i` に代入する。これは __`i` に 1 を加算するという処理__ に相当する

繰り返しが __続行する条件__ は以下の通りです。

* `range(0, 10, 1)` から __取り出す値がまだ残っている__。`range(0, 10, 1)` からは、0 ~ 9 の整数を順番に取り出すことができるので、`i` を 0 から順番に 1 つずつ増やした際に、__`i` が 10 未満の間繰り返し処理を続行する__ という処理に相当する

上記のプログラムでは break 文や return 文は記述されていないので、繰り返しが終了する条件は記述されていません。

`break` や `return` 文が記述されていない __for 文__ による繰り返し処理では、上記の `for i in range(0, 10, 1)` という記述のように、__for 文の中__ に __初期設定__、__繰り返して行われる処理__、繰り返しが __続行する条件__ が __含まれています__。

### while 文による繰り返し処理

__while 文__ の場合は、下記のように、__初期設定__、__繰り返して行われる処理__、繰り返しが __続行する条件__ を、for 文とは異なり、__独立して記述__ します。

* __初期設定__ は、__while 文の前に記述__ する
* __繰り返して行われる処理__ は、while 文の __条件式__ と、while 文の __ブロック__ である
* 繰り返しの __続行の条件__ は、while 文の __条件式の計算結果が `True`__ であることである

なお、break 文や return 文による繰り返しの終了に関しては for 文と同様です。

:::note
上記で、繰り返して行われる処理に __条件式が含まれている__ のは、__条件式の中に関数呼び出しなどが記述__ されている場合は、条件式を実行することで __変数の値が変化する__ 処理が行われる場合があるからです。
:::

先程の 0 から 9 までの整数の合計を計算するプログラムは、while 文を使った場合は下記のプログラムのように記述することができます。

* __1、2 行目__：合計を表す `total` と、次に加算を行う数を表す `i` を `0` で初期化する
* __3 行目__：`i` が `10` 未満の場合に繰り返し処理を行う（続行の条件）
* __4、5 行目__：繰り返し行う処理では、`total` に `i` を加算し、その後で `i` を `1` 増やす

```python
1  total = 0
2  i = 0
3  while i < 10:
4      total += i
5      i += 1
6
7  print(total)
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
total = 0
i = 0
while i < 10:
    total += i
    i += 1

print(total)
```
</details>

実行結果

```
45
```

### for 文と while 文の使い分け

__for 文__ は、繰り返し処理の中で「0 ~ 9 までの整数の合計を計算する」のように、__あらかじめ繰り返しを行う回数が決まっている__ ような処理を __簡潔に記述できる__ という性質があります。そのような処理を while 文を使って上記のように記述することはできますが、for 文より記述が複雑になります。

逆に、例えば「サイコロを 1 が出るまで振り続ける」のようにあらかじめ何回繰り返しの処理を行うかが __わからないような場合__ は __while 文を使う必要があります__。

このように、for 文と while 文はどちらも繰り返し処理を記述できますが、__利点と欠点がある__ ので、繰り返し処理の性質に応じて __適切に使い分ける必要があります__ 。これは、この後で説明する再帰呼び出しによる繰り返し処理についても同様です。今回の記事で、__それぞれの繰り返し処理の性質を説明__ しているのは、__使い分けを行うことができるようにするため__ です。

__for 文__ は様々な繰り返し処理の中で、__特定の性質__ を持った繰り返し処理を簡潔に記述するために用意された __専用の道具__ で、__while 文__ はどのような繰り返し処理でも記述できる __汎用的な道具__ だと考えると良いでしょう。

:::note
現実の世界でもそのようなものは数多くあります。例えば、物を切る道具として、ナイフは様々なものを切ることができる __汎用的な道具__ ですが、ハサミは紙を切るために用意された __専用の道具__ です。
:::

### 以後の説明の表記について

詳細は省略しますが、__for 文__ の処理は __while 文によって記述し直す__ ことができますが、__while 文__ で記述された処理を __for 文に記述し直す__ ことが __できるとは限りません__。

そこで、以後は再帰呼び出しと、for 文や while 文の __性質の比較の説明__ をする際に、for 文については言及せずに、__while 文のみを言及する__ ことにします。

:::note
下記の変換について詳しく説明するとかなり長くなるので、今回の記事では説明は省略しますが、具体的には、下記の for 文による繰り返し処理は、その下の while 文による繰り返し処理に変換することができます。

```python
for 変数 in 反復可能オブジェクト:
    繰り返し処理
```

```python
iterator = iter(反復可能オブジェクト)
while True:
    try:
        変数 = next(iterator)
        繰り返し処理
    except:
        break
```

具体例として、先程の下記の for 文は、その下の while 文に変換できます。実際には、for 文は下記の while 文を簡潔に記述するために用意されたものです。

```python
total = 0 
for i in range(0, 10, 1):
    total += i

print(total)
```

```python
total = 0
iterator = iter(range(0, 10, 1))
while True:
    try:
        i = next(iterator)
        total += i
    except:
        break
    
print(total)
```

実行結果

```
45
```

while 文で利用している `iter` と `next` は組み込み関数です。また、上記のプログラムはイテレータという仕組みを利用しています。これらに関しては、必要になった時点で紹介したいと思います。興味がある方は下記のリンク先を参照して下さい。
:::

https://docs.python.org/ja/3/library/functions.html#iter

https://docs.python.org/ja/3/library/functions.html#next

https://docs.python.org/ja/3/library/stdtypes.html#typeiter

### 計算結果の記録の方法

繰り返し処理では、基本的には __繰り返しのたび__ に、なんらかの計算を行い、その __計算結果を変数に代入して反映__ させます。例えば、下記の while 文による繰り返し処理では、繰り返しのたびに下記の変数の値が変化していきます。

* 次に加算する整数を表す変数 __`i`__
* それまでの整数の合計を表す変数 __`total`__

```python
total = 0
i = 0
while i < 10:
    total += i
    i += 1

print(total)
```


__while 文__ による繰り返し処理では、上記のような __計算結果を代入する変数__ は、この後で説明する再帰呼び出しによる繰り返し処理とは異なり、__同じ変数が使われる__ のが一般的です。

:::note
下記のプログラムのように、何の処理も行わない無限ループを記述することもできますが、これは一般的な繰り返し処理ではないでしょう。

```python
while True:
    pass
```
:::

## 再帰呼び出しによる繰り返し処理

__再帰呼び出し__ は __繰り返し処理の一種__ なので、while 文と同様に、下記の処理を記述しますが、その __記述方法は大きく異なります__。

* 繰り返し処理を行う前の初期設定を行う
* 特定の条件が満たされる間、処理を繰り返す

### 再帰呼び出しによる無限ループ

先程紹介した下記の関数 `f` では、そのブロックの中で __必ず `f` を呼び出している__ ので、`f` の呼び出しは無限に行われます。従って、関数 `f` を呼び出すと __無限ループが発生__ します。

```python
def f():
    f()
```

ただし、__再帰呼び出しによる無限ループ__ は、プログラムが本当に終了しない while 文による無限ループと異なり、実行すると下記のプログラムのように __エラーが発生してプログラムが終了__ します。このようなエラーが発生する理由については後で説明します。

```python
f()
```

実行結果

```
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
Cell In[6], line 1
----> 1 f()

Cell In[1], line 2
      1 def f():
----> 2     f()

Cell In[1], line 2
      1 def f():
----> 2     f()

    [... skipping similar frames: f at line 2 (2971 times)]

Cell In[1], line 2
      1 def f():
----> 2     f()

RecursionError: maximum recursion depth exceeded
```

:::note
上記のエラーメッセージは、以下のような意味を持ちます。

* __RecursionError__
再帰呼び出し（Recursion）に関するエラー
* __maximum recursion depth exceeded__
再帰呼び出し（recursion）が、最大（maximum）の深さ（depth）を超えて行われた（exceeded）
:::

:::note
途中に表示される下記のメッセージは、2 行目（line 2）で同じ（similar）内容が 2971 回（times）表示されるのを省略（skippiing）したという意味です。

```
    [... skipping similar frames: f at line 2 (2971 times)]
```
:::

実行結果は省略しますが、下記のプログラムのように、先程定義した `g` を呼び出しても同様のエラーが発生します。

```python
g()
```

:::note
具体的な条件は良くわからなかったのですが、Python のバージョンによっては、再帰呼び出しによる無限ループを実行すると、下記の実行結果のような表示が行われる場合があるようです。カーネルがクラッシュすると、Python のプログラムを続けて実行することができないので、JupyterLab 再起動する必要があります。再起動してもうまく動作しない場合は、VSCode を一旦終了して立ち上げなおしてください。

なお、筆者のパソコンでは、Python のバージョンが 3.10.13 の場合にカーネルがクラッシュし、3.11.4 の場合は RecursionError が発生しましたが、何か別の条件があるかもしれませんので知っている方はコメントしていただければ嬉しいです。

```python
f()
```

実行結果
```
現在のセルまたは前のセルでコードを実行中に、カーネル (Kernel) がクラッシュしました。
エラーの原因を特定するには、セル内のコードを確認してください。
詳細についてはこちらをクリックします。
詳細については、Jupyter ログ を参照してください。
```
:::

### 繰り返し処理の終了の記述方法

再帰呼び出しでは、__自分自身の関数を呼び出す__ ことで、同じ処理を何度も __繰り返す__ という処理を行うので、__if 文など__ を利用して、__特定の条件__ では __自分自身を呼び出さないようにする__ ことで、__繰り返し処理を終了__ することができます。

詳しい説明はこの後で行いますが、下記のプログラムでは `i < 10` という条件式が `False` になる場合に自分自身を呼び出さないようにすることで繰り返し処理を終了します。

```python
def sum9(i, total):
    if i < 10:
        total += i
        i += 1
        return sum9(i, total)
    else:
        return total
```

### 繰り返し処理の計算の結果の記録方法

__再帰呼び出し__ での、繰り返し処理の __計算結果の記録方法__ は、以下の点で __while 文__ による計算結果の記録方法と __大きく異なります__。

* 繰り返し処理が __行われている間__ は、__変数で記録__ する。ただし、while 文では一般的に同じ変数に記録するが、__再帰呼び出し__ では __関数の仮引数で記録する__ ため、再帰呼び出しが行われるたびに、__異なる変数で記録が行われる__。異なる変数については後で説明する
* 繰り返し処理が __終了する際__ には、関数の __返り値で計算結果を返す__

:::note
今回の記事の最後で説明しますが、仮引数に list などの、ミュータブルなデータが代入される場合などでは、関数の返り値ではなく、仮引数に代入したミュータブルなデータの内容を変化させることで計算結果を記録する場合があります。
:::

下記は、先程の while 文で 0 ~ 9 までの整数の合計を計算するプログラムで、__繰り返し処理の間__ は __常に同じ変数 `i`、`total`__[^1] に繰り返し処理の計算結果を代入します。

```python
total = 0
i = 0
while i < 10:
    total += i
    i += 1
```

このプログラムを再帰呼び出しで記述すると下記のようになります。なお、0 ~ 9 までの合計を計算するので、関数の名前を __`sum9`__ としました。

この関数の仮引数 `i` と `total` は下記のような意味を持ちます。

* __`total`__：0 から `i` 未満までの整数の合計
* __`i`__：次に `total` に加算する整数

なお、これらの __仮引数__ は、__while 文__ の `i` と `total` と __全く同じ意味__ を持ちます。

```python
1  def sum9(i, total):
2      if i < 10:
3          total += i
4          i += 1
5          return sum9(i, total)
6      else:
7          return total
8
9  print(sum9(i=0, total=0))
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
def sum9(i, total):
    if i < 10:
        total += i
        i += 1
        return sum9(i, total)
    else:
        return total

print(sum9(i=0, total=0))
```
</details>

実行結果

```
45
```

__while 文__ の繰り返し処理との __共通点__ と __違い__ は以下の通りです。なお、最後の 9 行目の `sum9` の関数呼び出しの処理の部分についてはこの後で説明します。

* __共通点__
    * `i < 10` が `True` の場合に、`total` と `i` の値を同じ式で更新する
* __違い__
    * `i`、`total` が `sum9` の仮引数になっている
    * `i < 10` が `True` の場合に、更新した `i` と `total` を実引数として `sum9` を呼び出し、その返り値をそのままこの関数の返り値として返す
    * `i < 10` が `False` の場合に `total` を返り値として返す

__`while`__ 文では、`i < 10` が `True` の場合に `while` 文の __ブロックの処理を実行する__ という方法で繰り返し処理を行っていますが、__再帰呼び出し__ の場合は `i < 10` が `True` の場合に __更新した `i` と `total` を実引数に記述__ して __自分自身を呼び出す__ ことで、__次の繰り返し処理を行う__ という方法を取ります。

また、再帰呼び出しでは __計算結果__ を、__関数の返り値で返す__ という点が __大きく異なります__。

### 初期設定の記述方法

__while 文__ による繰り返し処理では、下記のプログラムの 1、2 行目のように、__初期設定の処理__ を __while 文の前に記述__ します。

```python
total = 0
i = 0
while i < 10:
    total += i
    i += 1
```

一方、__再帰呼び出し__ では、関数の __仮引数__ に繰り返し処理の __計算結果を代入__ して処理を行うので、下記のプログラムの 9 行目のように、__初期設定の処理__ は、__最初に関数を呼び出した際__ の __実引数で行います__。なお、下記のプログラムの 9 行目を `sum9(0, 0)` のように記述しなかったのは、__初期設定の処理で `i` と `total` に `0` を代入することを明確にする__ ためです。

```python
1  def sum9(i, total):
2      if i < 10:
3          total += i
4          i += 1
5          return sum9(i, total)
6      else:
7          return total
8
9  print(sum9(i=0, total=0))
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
def sum9(i, total):
    if i < 10:
        total += i
        i += 1
        return sum9(i, total)
    else:
        return total

print(sum9(i=0, total=0))
```
</details>

### while 文と再帰呼び出しの記述の違い

while 文と再帰呼び出しの記述の違いをまとめると下記の表のようになります。

|  | while 文 | 再帰呼び出し |
|:--|:--|:--|
| __初期設定__  | while 文の前に記述  | 最初の関数の呼び出しの実引数に記述  |
| __繰り返す処理の記述場所__  | while 文の条件式と、while 文のブロック  | 関数のブロック  |
| __繰り返しの続行の制御__  | while 文の条件式と break、return 文  | 関数の中で自分自身を呼び出すかどうかを if 文などで制御する  |
| __計算結果の記録__ | 同じ変数に代入する | 繰り返しの途中では関数の仮引数に代入する。ただし、最後は return 文で返す| 

上記の性質を理解すれば、0 ~ 9 までの整数の合計を計算する処理のように、__while 文__ の繰り返し処理を __再帰呼び出しで記述し直す__ ことができます。

## 再帰呼び出しの処理の流れ

再帰呼び出しによる繰り返し処理の仕組みについて説明しましたが、処理の流れが良くわからない人や、自分自身を呼び出すという処理に違和感を感じている人が多いのではないかと思います。そこで、最初に再帰呼び出しが行う処理を人間で例えた例を説明し、その後で、再帰呼び出しの処理の流れを具体的なプログラムを使って説明することにします。

### 再帰呼び出しが行う処理の例え

__while 文__ による __0 から 9 までの整数の合計を計算__ する繰り返し処理を、人間が行う場合で例えると、__一人の人__ が、0 から 9 までの整数を、__途中経過をメモなどに記録しながら計算する__ ことに相当します。途中経過にメモした内容が `i` や `total` などの変数に相当します。

一方、再帰呼び出しで行われる処理を人間が行う場合で例えると、以下のようになります。

* 下記のような作業を行う __アルバイトを多数用意__ する。なお、アルバイトは、計算を行うために __必要な人数だけ用意できるものとする__。アルバイトに渡す作業のマニュアルが関数の定義、アルバイトの一人に指示を与えることが関数呼び出しに相当する
    * __0 から i 未満までの整数の合計__ を店長または他のアルバイトから __伝えてもらい__（仮引数 `i` と `total` に相当）、下記の作業を行う
    * __i が 10 未満の場合__ は以下の処理を行う（`if i < 10:` に相当） 
        * 伝えてもらった合計と i を足し算することで、__0 から i 以下までの整数の合計を計算__ する（`total += i` に相当）
        * i に 1 を足す（`i += 1` に相当）
        * __次のアルバイトを一人選び、__ 0 から i 未満までの整数の合計を伝えて __続きの計算を依頼__ し（`sum9(i, total)` に相当）答えを待つ
        * 答えが返ってきたら、__前の人に答えを伝える__（`return sum9(i, total)` に相当）
    * __n が 10 以上の場合__ は、前の人から伝えてもらった合計が、0 から 9 以下の整数の合計なので、__前の人にその値をそのまま伝える__（`return total` に相当）
* 店長が、アルバイトを一人選び、0 から 0 未満の整数の合計（まだ一つも計算していないという意味）を伝えて __計算を依頼__ し（最初の `sum9(i=0, total=0)` に相当）__返事を待つ__

上記によって、下記の手順で計算が行われます。なお、「1 人目のアルバイト」という表現は長いので、1 人目のアルバイトのこと「1 人目」のように表記することにします。

* 店長が 1 人目に「0 から 0 未満の合計が 0」であることを伝えて計算を依頼する
* 1 人目が計算を行い、「0 から 1 未満の合計が 0」を 2 人目に伝えて計算を依頼する
* 2 人目が計算を行い、「0 から 2 未満の合計が 1」を 3 人目に伝えて計算を依頼する
* 3 人目が計算を行い、「0 から 3 未満の合計が 3」を 4 人目に伝えて計算を依頼する
* 中略
* 10 人目が計算を行い、「0 から 10 未満の合計が 45」を 11 人目に伝えて計算を依頼する
* 11 人目は、0 から 9 以下の計算が行われたことが確認できたので、10 人目からもらった 45 が答えであることを、10 人目に伝える
* 10 人目は、11 人目から伝えられた答えである 45 を 9 人目にそのまま伝える
* 9 人目は、10 人目から伝えられた答えである 45 を 8 人目にそのまま伝える
* 中略
* 1 人目は、2 人目から伝えられた答えである 45 を 店長にそのまま伝える
* 店長は 45 という正しい答えを受け取る

上記の処理をまとめると以下のようになります。

* 0 から 9 までの整数を加算する処理を、__整数ごとに別のアルバイトが担当__ する
* 店長が、最初のアルバイトに計算を依頼する
* アルバイトは __自分の担当する計算を行った後__ で、次のアルバイトに __続きの計算を依頼__ し、答えが返ってくるのを待つ
* 上記の作業を続けることで、0 から 9 までの整数の合計を計算することができる
* 合計を計算できたアルバイトは、__その答えを前のアルバイトに伝える__
* 答えを受け取ったアルバイトは、その答えを前のアルバイトに伝える
* 上記の作業を続けることで、店長がアルバイトから答えを受け取ることができる

さらにまとめると、__店長からの指示が__ つぎつぎとアルバイトに __伝わっていき__、__結果を計算できたアルバイト__ から答えが __逆の順番で店長に伝わる__ という __伝言ゲームに似ています__。

上記の事から、再帰呼び出しは、以下のような処理を行うことがわかります

* 繰り返しの __個々の処理__ を __関数で記述する__
* 関数で行った __処理の結果__ を、関数呼び出しの __実引数に記述して渡す__ ことで、__処理の続き__ を __次の関数に依頼__ する
* 上記の処理を必要な回数だけ続けることで、処理を完了できる
* __処理の結果__ が必要な場合は、__返り値で返す__ ことで、伝言ゲームのような形で __最初の関数呼び出しの返り値に結果が戻る__

:::note
処理の結果を知る必要ない場合は返り値を返す必要はありません。また、上記の例では返り値をそのまま返していますが、戻ってきた返り値に何らかの計算を行った値を返すという場合もあります。具体例は次回の記事で紹介します。
:::

### 自分自身を呼び出すことの意味

再帰呼び出しでよくある誤解の原因の一つが、__自分自身を呼び出す__ という表現ではないかと思います。__自分自身を呼び出す__ ということは、自分自身が現在行っている処理に直接影響を及ぼすような新しい処理を行うように思えるかもしれませんが、実際には「自分自身と __同じ処理を行う__、__新しい別の関数を呼び出す__」という処理が行われます。

先程の例えで説明すると、同じマニュアルを学んだアルバイトを複数人用意し、その中から別の誰かを選んでマニュアル通りに作業を行ってもらうことに相当します。つまり、自分自身を呼び出すということは、__自分と同じマニュアルを学んだ__、自分と同じ作業を行うことができる __自分とは別の人に作業を依頼する__ という意味だと考えて下さい。

全く同じ作業ができる人間を思い浮かべることが直感的にわかりづらいと思った方は、全く同じ作業を行うことができるロボットを思い浮かべてみると良いでしょう。

### 再帰呼び出しの処理の流れの具体例

次に、先程の 0 から 9 以下の整数の合計を再帰呼び出しで計算するプログラムの処理の流れを説明します。まず、処理の流れがわかるように、`sum9` をいくつか `print` でメッセージを表示するように修正しました。


* __2 行目__：`sum9` の仮引数 `i` には、最初は `0` が代入され、`sum9` を呼び出すたびに `i` が 1 ずつ加算されるので、`sum9` が呼び出された回数は `i + 1` で計算できる。その値を `count` というローカル変数に代入する
* __3 行目__：`sum9` が呼び出された際に、何回目の呼び出しであるかと、仮引数 `i` と `total` の値を `print` で表示する。それぞれの値は最大 2 桁の数値になるので、数値の表示位置が縦に揃うように、[書式指定](https://qiita.com/ysgeso/items/bf42b7b578bc2d5da949#%E6%96%87%E5%AD%97%E5%B9%85)の `:2` を使って 2 文字で表示するようにした
* __7 ~ 9 行目__：元のプログラムでは `return sum9(i, total)` のように、呼び出した `sum9` の返り値を直接返していたが、それでは返り値を表示できないので、一旦 `retval`[^2] に `sum9` の返り値を代入し、`print` で表示してからその値を返すようにした
* __11 行目__：`i < 10` でない場合も返り値を表示するようにした

```python
 1  def sum9(i, total):
 2      count = i + 1
 3      print(f"{count:2} 回目の sum9 の呼び出し。i = {i:2}, total = {total:2}")
 4      if i < 10:
 5          total += i
 6          i += 1
 7          retval = sum9(i, total)
 8          print(f"{count:2} 回目の sum9 の返り値 {retval}")
 9          return retval
10      else:
11          print(f"{count:2} 回目の sum9 の返り値 {total}")
12          return total
13
14 print(sum9(i=0, total=0))
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
def sum9(i, total):
    count = i + 1
    print(f"{count:2} 回目の sum9 の呼び出し。i = {i:2}, total = {total:2}")
    if i < 10:
        total += i
        i += 1
        retval = sum9(i, total)
        print(f"{count:2} 回目の sum9 の返り値 {retval}")
        return retval
    else:
        print(f"{count:2} 回目の sum9 の返り値 {total}")
        return total

print(sum9(i=0, total=0))
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
def sum9(i, total):
+   count = i + 1
+   print(f"{count:2} 回目の sum9 の呼び出し。i = {i:2}, total = {total:2}")
    if i < 10:
        total += i
        i += 1
-       return sum9(i, total)
+       retval = sum9(i, total)
+       print(f"{count:2} 回目の sum9 の返り値 {retval}")
+       return retval
    else:
+       print(f"{count:2} 回目の sum9 の返り値 {total}")
        return total

print(sum9(i=0, total=0))
```
</details>

実行結果

```
 1 回目の sum9 の呼び出し。i =  0, total =  0
 2 回目の sum9 の呼び出し。i =  1, total =  0
 3 回目の sum9 の呼び出し。i =  2, total =  1
 4 回目の sum9 の呼び出し。i =  3, total =  3
 5 回目の sum9 の呼び出し。i =  4, total =  6
 6 回目の sum9 の呼び出し。i =  5, total = 10
 7 回目の sum9 の呼び出し。i =  6, total = 15
 8 回目の sum9 の呼び出し。i =  7, total = 21
 9 回目の sum9 の呼び出し。i =  8, total = 28
10 回目の sum9 の呼び出し。i =  9, total = 36
11 回目の sum9 の呼び出し。i = 10, total = 45
11 回目の sum9 の返り値 45
10 回目の sum9 の返り値 45
 9 回目の sum9 の返り値 45
 8 回目の sum9 の返り値 45
 7 回目の sum9 の返り値 45
 6 回目の sum9 の返り値 45
 5 回目の sum9 の返り値 45
 4 回目の sum9 の返り値 45
 3 回目の sum9 の返り値 45
 2 回目の sum9 の返り値 45
 1 回目の sum9 の返り値 45
45
```

実行結果から以下の事がわかります。これは、__先程の例えで説明した通りの手順__ です。

* 1 ~ 11 回目の `sum9` が次々と呼びだされる
* その際に仮引数 `i` が 1 ずつ増え、`total` には 0 以上 `i` 未満の合計が代入される
* 11 回目の `sum9` の呼び出しで、0 から 9 以下の整数の合計が計算され、45 が返される
* 10 ~ 1 回目の順で 45 が返され、最終的に 45 が `sum9(i=0, total=0)` の返り値となる

## 再帰呼び出しが行われる仮引数の扱い

再帰呼び出しでは、何か特別な処理が行われているように思えるかもしれませんが、__再帰呼び出しで行われる処理__ は、__通常の関数呼び出しと全く同じ__ です。その際に、直観的に __わかりづらい__ のが、__仮引数の扱い__ ではないかと思います。

例えば、__2 回目__ の `sum9` の呼び出しでは、__仮引数 `i` に `1`__ が、__`total` に `0`__ が代入されます。その際に __1 回目の__ `sum9` の呼び出しの __仮引数 `i` と `total`__ の値が __上書き__ されてしまうと __錯覚してしまう__ 人が多いのではないかと思いますが、__実際には違います__。

このような錯覚は、__同じ名前の関数を呼び出している__ ために起きるのではないかと思います。例えば、下記のプログラムのように、__同じ名前の仮引数__ を持つ __異なる関数を定義__ しても、__それぞれの仮引数__ は名前は同じですが、__別の変数である__ ことは、プログラミングにある程度慣れた方であれば理解できるのではないかと思います。

```python
def add(x, y):
    return x + y

def mul(x, y):
    return x * y
```

同じ名前の仮引数であっても、異なる関数であれば別の変数である理由は、[以前の記事](https://qiita.com/ysgeso/items/cd3e1c0731b859bf5e2c#%E3%83%AD%E3%83%BC%E3%82%AB%E3%83%AB%E5%90%8D%E5%89%8D%E7%A9%BA%E9%96%93)で説明したように、__関数呼び出しが行われた際__ に、その関数の __ローカル名前空間が作成__ され、その名前空間に、関数の仮引数などの __ローカル変数の名前が登録される__ からです。

自分自身を呼び出すという、__再帰呼び出し__ が行われた際も __同様の処理が行われる__ ので、1 回目の `sum9` が呼び出された際と、2 回目の `sum9` が呼び出された際には、それぞれ __別のローカル名前空間が作成__ され、そこに `i` と `total` という名前が __別々に登録__ されます。従って、1 回目の `sum9` と 2 回目の `sum9` の `i` と `total` は、名前が同じでも __異なる変数__ です。

先程のアルバイトの例えを思い出してください。再帰呼び出しは、同じマニュアルを学んだ別のアルバイトに作業の続きを依頼することに相当します。__異なるアルバイト__ はそれぞれ __別々に `i` と `total` の値を記憶__ しており、それらが __混同されることはありません__。

関数のブロックの中では、__別の関数のローカル名前空間の変数を直接記述して利用することはできません__[^3]。例えば、先程の `add` という関数の処理の中で、別の `mul` という関数のローカル変数 `x` と `y` の値を直接プログラムに記述して利用することはできません。同様に、再帰呼び出しでも、別の回数で呼び出された __同名の関数のローカル変数を直接利用することはできません__。

下記は、2 回目の `sum9` までに行われる処理で、`sum9` のローカル変数がどのように変更されるかを表したものです。表の「__ー__」は、まだその回の `sum9` の呼び出しが行われていないので、その __仮引数が存在しない__ ことを意味します。
1
 のように、取り消し線が表示されている数値については、__存在はしているが、直接利用できない__ ことを意味します。それらの変数は、__その変数を管理する関数に処理が戻った時点__ で、__再び利用できる__ ようになります。

ただし、そのことは __特別なことでは全くありません__。__通常の関数呼び出し__ でも、呼び出した側の関数のローカル変数は一時的に利用できなくなりますが、その関数に処理が戻った時点で再び利用できる点は __全く同じです__。

<table border>
<tr>
  <th colspan="2" rowspan="2"></th>
  <th colspan="2" style="text-align: center">1 回目</th>
  <th colspan="2" style="text-align: center">2 回目</th>
</tr>
<tr>
  <td style="text-align: center"><code>i</code></td>
  <td style="text-align: center"><code>total</code></td>
  <td style="text-align: center"><code>i</code></td>
  <td style="text-align: center"><code>total</code></td>
</tr>
<tr>
  <td rowspan="3">1 回目</td>
  <td>1 行目<br>(呼び出しの直後)</td>
  <td style="text-align: center">0</td>
  <td style="text-align: center">0</td>
  <td style="text-align: center">ー</td>
  <td style="text-align: center">ー</td>
</tr>
<tr>
  <td>3 行目<br>(<code>total += i</code>)</td>
  <td style="text-align: center">0</td>
  <td style="text-align: center">0</td>
  <td style="text-align: center">ー</td>
  <td style="text-align: center">ー</td>
</tr>
<tr>
  <td>4 行目<br>(<code>i += 1</code>)</td>
  <td style="text-align: center">1</td>
  <td style="text-align: center">0</td>
  <td style="text-align: center">ー</td>
  <td style="text-align: center">ー</td>
</tr>
<tr>
  <td rowspan="3">2 回目</td>
  <td>1 行目</td>
  <td style="text-align: center;">
1
</td>
  <td style="text-align: center">
0
</td>
  <td style="text-align: center">1</td>
  <td style="text-align: center">0</td>
</tr>
<tr>
  <td>3 行目</td>
  <td style="text-align: center;">
1
</td>
  <td style="text-align: center">
0
</td>
  <td style="text-align: center">1</td>
  <td style="text-align: center">1</td>
</tr>
<tr>
  <td>4 行目</td>
  <td style="text-align: center;">
1
</td>
  <td style="text-align: center">
0
</td>
  <td style="text-align: center">2</td>
  <td style="text-align: center">1</td>
</tr>
</table>


### 再帰呼び出しによる無限ループがエラーになる理由

下記のプログラムのような、__while 文による無限ループを実行__ すると、プログラムの処理が、無限ループから抜け出すことができないため、__プログラムが固まる__ ことになります。

```python
while True:
    pass
```

一方、下記のプログラムのような、__再帰呼び出しによる無限ループを実行__ すると、先程説明したように、RecursionError が発生して、__プログラムの処理が終了__ します。

```python
def f():
    f()

f()
```

同じ無限ループでも、このような違いが生じる原因は、上記の __while 文による無限ループ__ では、繰り返しの処理を行う際に、__新しい変数を利用する必要が生じない__ からです。例えば、while 文による数の合計の計算のような繰り返しの場合は、いくつまで計算したかを表す `i` と、それまでに計算した合計である `total` という 2 つの変数を用意し、その 2 つの変数の値を変化させていくことで、__新しい変数を用意することなく__、いくつまででも計算を続けていくことが可能です。

一方、__再帰呼び出し__ では、自分自身を呼び出す際に、呼び出した関数の __ローカル名前空間が作成__ されます。再帰呼び出しが行われるたびに、ローカル名前空間の中に、__仮引数の情報を記録する必要がある__ ので、コンピューターの __メモリがどんどん消費されていく__ ことになります。また、__ローカル名前空間を作成する際__ には、上記の関数 f のように、一つもローカル変数が存在しない場合でも、__コンピューターのメモリを一定量消費します__。

このように、再帰呼び出しによって、__自分自身の関数を呼び出すたび__ に、__コンピューターのメモリが少しずつ消費されていく__ ことになるため、__いつかはメモリが枯渇__ してしまい、無限に再帰呼び出しを行うことができなくなります。そのため、多くのプログラム言語では、__再帰呼び出しを行える回数が制限__ されており、Python ではその回数（おそらく数千回です）を超える再帰呼び出しの処理を行うと、RecursionError が発生するようになっています。

先程の例えで説明すると、再帰呼び出しは、全く同じ作業を行う別のロボットに処理の続きを依頼するということに似ています。その際に、依頼する数だけ別のロボットを実際に用意する必要があり、そのようなロボットを無限に用意することはできません。



## return 文を使わない再帰呼び出しの例

先程の例では、再帰呼び出しの計算結果を return 文で返しましたが、__処理の結果を知る必要がない__ 場合は、__return 文を記述する必要はありません__。

また、処理の結果を知る必要がある場合でも、再帰呼び出しを行う関数の __仮引数に、list などのミュータブルなデータを代入__ し、__その中身を変化させる__ という処理を行う場合は、__return 文を使わず__ 再帰呼び出しの処理の結果を利用することができます。

例えば、下記のプログラムは、0 から 任意の整数まで[^4]の要素を持つ list を再帰呼び出しで作成するプログラムです。なお、この例は、return 文を使わない再帰呼び出しの例として無理やり考えたものです。そのような list はリスト内包表記を使って `[i for i in range(10)]` のように簡潔に作成できるので、再帰呼び出しで作成する必要は全くありません。

下記の `create_list` の仮引数は以下のような意味を持ちます。

* __`i`__：次に `l` に追加する要素の値
* __`l`__[^5]：0 から `i` 未満の整数の要素を持つ list。ただし、`i` が 0 の場合は 空の list とする
* __`maxi`__[^5]：この関数では、`maxi` 未満の整数までの要素を追加する

また、プログラムは下記のような処理を行います。先ほどと同様に、処理の流れがわかるように `print` でメッセージを表示するようにしました。

* __2、3 行目__：`create_list` が呼び出された際に、何回目の呼び出しであるかと `i` と `l` の値を `print` で表示する
* __4 ~ 6 行目__：`i` が `maxi` 未満の場合は、`l` に `i` を追加し、`i` に `1` を足して、`create_list` を呼び出す。なお、`maxi` は変更する必要はない
* `i` が `maxi` 未満でない場合は、`else` を記述せずに __何も処理を行わない__ ことで、再帰呼び出しによる __繰り返し処理を終了__ する
* __9 行目__：`create_list` の処理が終了したことを表示する
* __11、12 行目__：`a` に空の list を代入して初期化し、`a` に 0 から 10 未満の要素を追加するように実引数を記述して `create_list` を呼び出す

```python
 1  def create_list(i, l, maxi):
 2      count = i + 1
 3      print(f"{count:2} 回目の呼び出し。i = {i:2}, l = {l}")
 4      if i < maxi:
 5          l.append(i)
 6          i += 1
 7          create_list(i, l, maxi)
 8
 9      print(f"{count:2} 回目の呼び出しの終了")
10        
11  a = []
12  create_list(0, a, 10)
13  print(a)
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
def create_list(i, l, maxi):
    count = i + 1
    print(f"{count:2} 回目の呼び出し。i = {i:2}, l = {l}")
    if i < maxi:
        l.append(i)
        i += 1
        create_list(i, l, maxi)

    print(f"{count:2} 回目の呼び出しの終了")
        
a = []
create_list(0, a, 10)
print(a)
```
</details>

実行結果

```
 1 回目の呼び出し。i =  0, l = []
 2 回目の呼び出し。i =  1, l = [0]
 3 回目の呼び出し。i =  2, l = [0, 1]
 4 回目の呼び出し。i =  3, l = [0, 1, 2]
 5 回目の呼び出し。i =  4, l = [0, 1, 2, 3]
 6 回目の呼び出し。i =  5, l = [0, 1, 2, 3, 4]
 7 回目の呼び出し。i =  6, l = [0, 1, 2, 3, 4, 5]
 8 回目の呼び出し。i =  7, l = [0, 1, 2, 3, 4, 5, 6]
 9 回目の呼び出し。i =  8, l = [0, 1, 2, 3, 4, 5, 6, 7]
10 回目の呼び出し。i =  9, l = [0, 1, 2, 3, 4, 5, 6, 7, 8]
11 回目の呼び出し。i = 10, l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
11 回目の呼び出しの終了
10 回目の呼び出しの終了
 9 回目の呼び出しの終了
 8 回目の呼び出しの終了
 7 回目の呼び出しの終了
 6 回目の呼び出しの終了
 5 回目の呼び出しの終了
 4 回目の呼び出しの終了
 3 回目の呼び出しの終了
 2 回目の呼び出しの終了
 1 回目の呼び出しの終了
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
```

実行結果から、1 ~ 11 回目の `create_list` の呼び出しで、__`l` に要素が 1 つづつ追加されていく__ ことがわかります。また、`l` の完成後は、__11 ~ 1 回の順で `create_list` の処理が終了する__ 様子が確認できます。このように、__return 文の記述の有無に関わらず__、再帰呼び出しで行われる __処理の流れは変わりません__。

11 行目の __`a`__ と、`create_list` の __仮引数 `l`__ は、__同じ list を共有__ しているので、`create_list` で __`l` に要素を追加すると__、__`a` にも同じ要素が追加__ されます。そのため、再帰呼び出しの処理の終了後には、`a` に 0 から 9 までの整数の要素を持つ list が代入されます。

:::note
下記のプログラムのように、上記のプログラムを return 文を使って記述してもかまいません。下記のように記述した場合は、`a` が必要なくなり、__直接空の list を `create_list` の実引数に記述できる__ ようになるという利点が生じます。

* __7 ~ 9 行目__：`create_list(i, l, maxi)` を返り値として返すように修正する。その際に、返り値を `print` で表示する
* __10 ~ 12 行目__：`i < maxi` が `false` の場合は完成した `l` を返り値として返すように修正する。その際に、返り値を `print` で表示する
* __14 行目__：初期設定として `l` に代入する実引数に、直接空の list を記述して `create_list` を呼び出すように修正する

```python
 1  def create_list(i, l, maxi):
 2      count = i + 1
 3      print(f"{count:2} 回目の呼び出し。i = {i:2}, l = {l}")
 4      if i < maxi:
 5          l.append(i)
 6          i += 1
 7          retval = create_list(i, l, maxi)
 8          print(f"{count:2} 回目の返り値 {retval}")
 9          return retval
10      else:
11          print(f"{count:2} 回目の返り値 {l}")
12          return l
13        
14  print(create_list(0, [], 10))
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
def create_list(i, l, maxi):
    count = i + 1
    print(f"{count:2} 回目の呼び出し。i = {i:2}, l = {l}")
    if i < maxi:
        l.append(i)
        i += 1
        retval = create_list(i, l, maxi)
        print(f"{count:2} 回目の返り値 {retval}")
        return retval
    else:
        print(f"{count:2} 回目の返り値 {l}")
        return l
        
print(create_list(0, [], 10))
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
def create_list(i, l, maxi):
    count = i + 1
    print(f"{count:2} 回目の呼び出し。i = {i:2}, l = {l}")
    if i < maxi:
        l.append(i)
        i += 1
-       create_list(i, l, maxi)
+       retval = create_list(i, l, maxi)
+       print(f"{count:2} 回目の返り値 {retval}")
+       return retval
+   else:
+       print(f"{count:2} 回目の返り値 {l}")
+       return l

-   print(f"{count:2} 回目の呼び出しの終了")

-a = []
-create_list(0, a, 10)
-print(a)
+print(create_list(0, [], 10))
```
</details>

実行結果

```
 1 回目の呼び出し。i =  0, l = []
 2 回目の呼び出し。i =  1, l = [0]
 3 回目の呼び出し。i =  2, l = [0, 1]
 4 回目の呼び出し。i =  3, l = [0, 1, 2]
 5 回目の呼び出し。i =  4, l = [0, 1, 2, 3]
 6 回目の呼び出し。i =  5, l = [0, 1, 2, 3, 4]
 7 回目の呼び出し。i =  6, l = [0, 1, 2, 3, 4, 5]
 8 回目の呼び出し。i =  7, l = [0, 1, 2, 3, 4, 5, 6]
 9 回目の呼び出し。i =  8, l = [0, 1, 2, 3, 4, 5, 6, 7]
10 回目の呼び出し。i =  9, l = [0, 1, 2, 3, 4, 5, 6, 7, 8]
11 回目の呼び出し。i = 10, l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
11 回目の返り値 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
10 回目の返り値 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 9 回目の返り値 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 8 回目の返り値 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 7 回目の返り値 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 6 回目の返り値 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 5 回目の返り値 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 4 回目の返り値 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 3 回目の返り値 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 2 回目の返り値 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 1 回目の返り値 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
```
:::

# while 文と、再帰呼び出しの使い分け

繰り返し処理は、while 文と再帰呼び出しのどちらを使っても記述することはできますが、それぞれ __一長一短がある__ ので、__適切に使い分ける__ 必要があります。

__再帰呼び出し__ による繰り返し処理は、以下のような __欠点__ があるため、再帰呼び出しによる繰り返し処理でなければ __記述しづらい場合を除いて__、__特に理由がなければ while 文や for 文__ による繰り返し処理を __記述したほうが良い__ でしょう。

なお、再帰呼び出しを使ったほうが良い場合については次回の記事で説明します。

## プログラムのわかりやすさの違い

__再帰呼び出し__ による繰り返し処理は、今回の記事で紹介したような、0 から 9 までの整数の合計を計算するような、__単純な繰り返し処理の場合__ は、プログラムが __わかりづらくなります__。下記の 2 つのプログラムを比較してみて下さい。再帰呼び出しの方がわかりやすいと思う人はほとんどいないのではないかと思います。

```python
# for 文による 0 ~ 9 までの合計を計算するプログラム
total = 0 
for i in range(10):
    total += i

print(total)

# 再帰呼び出しによる 0 ~ 9 までの合計を計算するプログラム
def sum9(i, total):
    if i < 10:
        total += i
        i += 1
        return sum9(i, total)
    else:
        return total

print(sum9(i=0, total=0))
```

実行結果

```
45
45
```

## 処理時間の違い

__while 文__ では、繰り返しの処理の __計算結果__ を __同じ変数に代入__ して上書きしながら処理を行いますが、__再帰呼び出し__ では、__関数を呼び出す__ ことで繰り返しの処理を行います。

変数への値の代入と、関数呼び出しでは、名前空間の作成などの処理が必要な分だけ __関数呼び出しのほうが時間がかかります__。そのため、__同じ内容の処理__ を行う場合では、一般的に __while 文__ による繰り返し処理の方が、__計算時間が短くなります__。

下記は、__['%%timeit'](https://qiita.com/ysgeso/items/10449c1d8e1465de1ed1#index-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E6%AC%A0%E7%82%B9%E3%81%A8timeit-%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%BC%E3%83%AB%E3%81%AB%E3%82%88%E3%82%8B%E5%87%A6%E7%90%86%E6%99%82%E9%96%93%E3%81%AE%E8%A8%88%E6%B8%AC)__ を使って for 文で 0 から 9 までの整数の合計の計算にかかる時間を計測するプログラムです。[以前の記事](https://qiita.com/ysgeso/items/10449c1d8e1465de1ed1#index-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E6%AC%A0%E7%82%B9%E3%81%A8timeit-%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%BC%E3%83%AB%E3%81%AB%E3%82%88%E3%82%8B%E5%87%A6%E7%90%86%E6%99%82%E9%96%93%E3%81%AE%E8%A8%88%E6%B8%AC)で説明したように、`%%timeit` で処理時間を計測する際には、`print` の処理を行うべきではないので、`print` による結果の表示は省略しています。

```python
%%timeit
total = 0 
for i in range(10):
    total += i
```

実行結果

```
361 ns ± 1.16 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
```

下記は再帰呼び出しの場合の計測を行うプログラムです。

```python
%%timeit
sum9(0, 0)
```

実行結果

```
805 ns ± 2.76 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
```

実行結果からわかるように、__再帰呼び出しの方が約 2 倍の処理時間__ がかかります。

# 今回の記事のまとめ

今回の記事では、再帰呼び出しによる繰り返し処理を、while 文による繰り返し処理と比較しながら説明を行いました。最後に説明したように、単純な繰り返し処理の場合は、再帰呼び出しによる繰り返し処理を記述するメリットはほとんどありません。そのため、これまでの記事では再帰呼び出しによる繰り返し処理は記述してきませんでした。

ただし、複雑な繰り返し処理を行う場合は、再帰呼び出しのほうが while 文による繰り返し処理よりも、プログラムを簡潔にわかりやすく記述することができます。具体例としては、深さ優先アルゴリズムでゲーム木を作成する場合などが挙げられます。

次回の記事では、再帰呼び出しによる繰り返し処理の利点について説明します。

最初は全部で 30 回くらいで終わるかなと思っていたのですが、気が付けば 100 回になってもまだゲーム木の説明すら終われませんでした。色々脱線しすぎているのではないかという自覚はあるのですが、大事なことは説明したほうが良い気がしますので、このペースで続けていきたいと思います。ペースや内容について何か意見がある方は、要望に応えることができるかどうかはわかりませんが、気軽にコメントして下さい。

# 本記事で入力したプログラム

| リンク | 説明 |
|:--|:--|
| [marubatsu.ipynb](https://github.com/ysgeso/marubatsu/blob/master/100/marubatsu.ipynb)  | 本記事で入力して実行した JupyterLab のファイル |

# 次回の記事

https://qiita.com/ysgeso/items/3a693c2f189845c01f4f

[^1]:合計を表す英単語には sum がありますが、`sum` という組み込み関数が存在するので、`total` という名前にしました
[^2]:`retval` は、返り値を表す return value の略です
[^3]:[ローカル関数](https://qiita.com/ysgeso/items/8f3d4b3d2c02ef51a70e#%E3%83%AD%E3%83%BC%E3%82%AB%E3%83%AB%E9%96%A2%E6%95%B0)のように、関数が別の関数のブロックの中に、入れ子で定義されている場合を除きます。例えば、Mbtree_GUI クラスの `on_left_button_clicked` 関数は、`create_event_handler` の中に定義されたローカル関数なので、`create_event_handler` のローカル変数である `self` を直接記述して利用できます
[^4]:先程の `sum9` に仮引数 `maxi` を加えて同様の処理を行うことで、0 から任意の整数未満の合計を計算するプログラムを記述することができます
[^5]:`list` や `max` という組み込み関数が存在するので、仮引数の名前を `l` や `maxi` としました