Pythonで〇×ゲームのAIを一から作成する　その102　直線的な繰り返し処理を行うボトムアップとトップダウンな再帰呼び出し

# 目次と前回の記事

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

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

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

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

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

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

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

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

# 直線的な繰り返し処理を行う再帰呼び出し

[前回の記事](https://qiita.com/ysgeso/items/3a693c2f189845c01f4f#for-%E6%96%87%E3%82%84-while-%E6%96%87%E3%81%AB%E5%90%91%E3%81%84%E3%81%A6%E3%81%84%E3%81%AA%E3%81%84%E7%B9%B0%E3%82%8A%E8%BF%94%E3%81%97%E5%87%A6%E7%90%86)で、繰り返し処理には、次の繰り返しの __処理の数が増えない__ ものと、次の繰り返しの処理が __分岐して増える__ ものがあるという説明をしました。本記事では以後は、繰り返しのたびに処理が増えないものを __直線的な繰り返し処理__、処理の数が増えるものを __分岐する繰り返し処理__ と表記することにします。

今回の記事では、__直線的な繰り返し処理__ を行う __再帰呼び出し__ について説明します。なお、分岐する繰り返し処理については次回の記事で説明します。

# 再帰呼び出しの深さと末端

今後の説明で使用する再帰呼び出しに関する用語を説明します。

再帰呼び出しの __処理の最中__ で、自分自身が呼び出された __回数__ の事を、再帰呼び出しの __深さ__ と呼びます。再帰呼び出しが行われる関数の名前を `f` とした場合、再帰呼び出しの深さには、下記の性質があります。

* 最初に呼び出された `f` の深さは 0である[^1]
* 深さが d の `f` から再帰呼び出しされた `f` の深さは d + 1 になる
* 深さが d の `f` の処理が終了すると、`f` を呼び出した深さが d - 1 の `f` に処理が戻る
* 深さが 0 の `f` の処理が終了した時点で、再起呼び出しの処理が完了する

再帰呼び出しの処理の最中で、__自分自身を呼び出さない `f`__ のことを再帰呼び出しの __末端__ と呼びます。__末端がない場合__ は `f` から必ず `f` が呼び出されるので __無限ループ__ になります。

:::note
再帰呼び出しの処理には、末端が複数ある場合があります。例えば、深さが 0、1、2、3、2、3、2、1、0 の順で `f` の処理が行われるような場合は、深さが 3 の末端が 2 つあります。なお、直線的な繰り返し処理に対する再帰呼び出しでは末端は 1 つですが、次回の記事で説明する分岐する繰り返し処理の場合は複数の末端があります。
:::

# 再帰呼び出しのアルゴリズムの種類

前回の記事では、for 文や while 文による繰り返し処理の性質と使い分けについて説明しました。その際に、for 文や while 文では以下のような繰り返し処理の記述が面倒であるという説明をしました。

* 独立ではない繰り返し処理で、[直前の計算結果以外](https://qiita.com/ysgeso/items/3a693c2f189845c01f4f#%E7%9B%B4%E5%89%8D%E3%81%AE-2-%E5%9B%9E%E5%88%86%E3%81%AE%E7%B9%B0%E3%82%8A%E8%BF%94%E3%81%97%E5%87%A6%E7%90%86%E3%81%AE%E7%B5%90%E6%9E%9C%E3%82%92%E4%BD%BF%E3%81%86%E4%BE%8B)の過去の計算結果を利用する場合
* 繰り返しのたびに 次に行う繰り返しの[処理の数が増えて分岐する](https://qiita.com/ysgeso/items/3a693c2f189845c01f4f#for-%E6%96%87%E3%82%84-while-%E6%96%87%E3%81%AB%E5%90%91%E3%81%84%E3%81%A6%E3%81%84%E3%81%AA%E3%81%84%E7%B9%B0%E3%82%8A%E8%BF%94%E3%81%97%E5%87%A6%E7%90%86)場合

今回の記事では分岐する繰り返し処理は扱わないので、前者の中で、直線的な繰り返し処理を再帰呼び出しで記述することで、より簡潔に記述できる場合がある例を示します。

再帰呼び出しのアルゴリズムには、__[ボトムアップ](https://qiita.com/ysgeso/items/3a693c2f189845c01f4f#for-%E6%96%87%E3%81%AB%E3%82%88%E3%82%8B%E3%83%9C%E3%83%88%E3%83%A0%E3%82%A2%E3%83%83%E3%83%97%E3%81%AA%E7%B9%B0%E3%82%8A%E8%BF%94%E3%81%97%E5%87%A6%E7%90%86%E3%81%AE%E8%A8%98%E8%BF%B0)__ な順番で計算を行うものと、__トップダウン__ な順番で計算を行うものがあり、上記のような繰り返し処理はトップダウンな再帰呼び出しを使って簡潔に記述できます。そこで、最初にその違いと使い分けについて説明します。

## ボトムアップな再帰呼び出し

[以前の記事](https://qiita.com/ysgeso/items/9d5e9a56f5fe004dafee#%E7%B9%B0%E3%82%8A%E8%BF%94%E3%81%97%E5%87%A6%E7%90%86%E3%81%AE%E7%B5%82%E4%BA%86%E3%81%AE%E8%A8%98%E8%BF%B0%E6%96%B9%E6%B3%95)で 0 から 9 までの合計を再帰呼び出しで計算する `sum9` を紹介しました。

下記は `sum9` の定義と、`sum9` で 0 から 9 までの合計を計算するプログラムです。

```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))
```

実行結果

```
45
```

上記の処理は、下記の __while 文__ を使って __ボトムアップな手順__ で 0 から 9 までの整数の合計を計算するプログラムを __元に作成したもの__ なので、__`sum9`__ は 0 から 9 までの順で整数の合計を計算するという、__ボトムアップな手順__ で繰り返し処理を行います。

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

print(total)
```

実行結果

```
45
```

### ボトムアップな再帰呼び出しの処理の流れ 

再帰呼び出しで行われる処理は、再帰呼び出しの __末端の深さを n__ とすると、以下のような手順で処理が行われます。

* 深さが 0、1、2・・・ n のように __末端の深さまで再帰呼び出しが行われる__。その際には、__実引数でデータが渡される__
* その後は __関数の処理が終了するたび__ に、深さが n、n - 1・・・1、0 のように __逆の順番__ で関数の処理が行われる。その際には、__返り値でデータが渡される__

上記の `sum9` では、__それまでに計算した合計__ が代入されている `total` を __実引数に記述__ して `sum9` を再帰呼び出ししています。そのため、再帰呼び出しのたびに実引数で合計が伝わっていき、__末端__ で呼び出された `sum9` の仮引数 __`total` には求める答えが代入されています__。

その後は __末端の再帰呼び出しから__、深さ 0 の再帰呼び出しへ __返り値__ という形で __計算結果が次々と戻されていき__、深さ 0 の再帰呼び出しが答えを返すことで処理が終了します。

その流れを見えるようにしたのが、[以前の記事](https://qiita.com/ysgeso/items/9d5e9a56f5fe004dafee#%E5%86%8D%E5%B8%B0%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97%E3%81%AE%E5%87%A6%E7%90%86%E3%81%AE%E6%B5%81%E3%82%8C%E3%81%AE%E5%85%B7%E4%BD%93%E4%BE%8B)で記述した、__処理の流れを表示__ するように修正した下記の `sum9` で、実行結果から下記のように、上記の処理の流れが確認できます。

* __再帰呼び出しが行われるたび__ に 0 から 順に __合計が計算されていき__、__末端__ の再帰呼び出しで __答えが求まる__
* __答え__ が return 文によって、__末端の再帰呼び出しから__ 逆の順番で最初の再帰呼び出しまで __返り値で伝えられる__

```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))
```

実行結果

```
 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
```

### 0 から n までの整数の合計の計算を行う関数の定義

`sum9` は、0 から 9 までの整数の合計を計算する処理しか行えないので、ボトムアップな再帰呼び出しで __0 から n までの整数の合計を計算__ する下記のような関数を定義する事にします。

なお、以後は 0 から n までの整数の合計を $x_n$ と表記することにします。  

__名前__：ボトムアップ（bottom up）な再帰呼び出し（recursive call）で合計（sum）を計算するので `sum_by_br` とする
__処理__：$x_n$ を計算する
__入力__：仮引数 `n` に $x_n$ の `n` を代入する。また、`sum9` と同じ方法で計算を行うので、仮引数 `i` と `total` が必要になる
__出力__：$x_n$ を返り値として返す

`sum_by_br` は下記のプログラムのように定義できます。仮引数 `n` を追加し、再帰呼び出しを行うかどうかの条件を `n` で判定する以外は、`sum9` の定義と同じです。

* __1 行目__：仮引数 `n` を追加する
* __2 行目__：`i` が `n` 以下かどうかを判定するように条件式を修正する。なお、元の `i < 10` に合わせて、`i < n + 1` と記述するとわかりづらいので、`i <= n` とした
* __5 行目__：呼び出す関数の名前を `sum_by_br` に修正し、実引数 n を追加する

```python
1  def sum_by_br(n, i, total):
2      if i <= n:
3          total += i
4          i += 1
5          return sum_by_br(n, i, total)
6      else:
7          return total
```

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

```python
def sum_by_br(n, i, total):
    if i <= n:
        total += i
        i += 1
        return sum_by_br(n, i, total)
    else:
        return total
```
</details>

<details><summary><strong><code>sum9</code>との違い</strong></summary>

```diff_python
-def sum9(i, total):
+def sum_by_br(n, i, total):
-   if i < 10:
+   if i <= n:
        total += i
        i += 1
-       return sum9(i, total)
+       return sum_by_br(n, i, total)
    else:
        return total
```
</details>

上記の修正後に、下記のプログラムを実行すると、実行結果から、正しい計算が行われることが確認できます。

```python
print(sum_by_br(n=9, i=0, total=0))
```

実行結果

```
45
```

ところで、上記の `sum_by_br(n=9, i=0, total=0)` で、__キーワード引数 `i=0` と `total=0` を記述__ する必要がある点が __面倒__ だと思った人はいないでしょうか。例えば、$x_9$ を計算する際に、単に `sum_by_br(9)` で計算できたほうが便利なので、これらのキーワード引数を省略できるようにすることにします。

一番簡単な方法は、下記のプログラムの 1 行目のように、初期設定である `0` をデフォルト値として設定したデフォルト引数にすることでしょう。

```python
def sum_by_br(n, i=0, total=0):
    if i <= n:
        total += i
        i += 1
        return sum_by_br(n, i, total)
    else:
        return total
```

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

```diff_python
-def sum_by_br(n, i, total):
+def sum_by_br(n, i=0, total=0):
    if i <= n:
        total += i
        i += 1
        return sum_by_br(n, i, total)
    else:
        return total
```
</details>

上記の修正後に、下記のプログラムを実行することで、`n` のみを記述して計算を行うことができるようになったことが確認できます。

```python
print(sum_by_br(9))
```

実行結果

```
45
```

:::note
他の方法として、下記のように `sum_by_br` を定義するという方法があります。

* 仮引数 `n` だけを持つ `sum_by_br` を定義する
* その中でローカル関数として、別の名前でこれまでの `sum_by_br` と同じ処理を行う関数を定義する
* `sum_by_br` では、$x_n$ を計算するローカル関数を呼び出す

下記はそのように `sum_by_br` を定義したプログラムです。

なお、`sum_by_br` とローカル関数は別の名前にする必要がありますが、ローカル関数の名前を考えるのは面倒です。そのような場合は、下記のプログラムのように `sum_by_br` の末尾に `_`（アンダースコア）[^2]つけて `sum_by_br_` という名前を付けるという方法があります。

```python
def sum_by_br(n):
    def sum_by_br_(n, i, total):
        if i <= n:
            total += i
            i += 1
            return sum_by_br_(n, i, total)
        else:
            return total
        
    return sum_by_br_(n, i=0, total=0)
```

上記の修正後に、下記のプログラムを実行すると、実行結果から正しい計算が行われることが確認できます。

```python
print(sum_by_br(9))
```

実行結果

```
45
```

:::

## トップダウンな再帰呼び出し

[前回の記事](https://qiita.com/ysgeso/items/3a693c2f189845c01f4f#%E6%BC%B8%E5%8C%96%E5%BC%8F)で説明したように、__0 から n までの整数の合計__ を $x_n$ と表記した場合、$x_n$ は、下記の __漸化式__ で表現できます。

$x_n = x_{n-1} + n$、$x_0=0$

$x_n$ の計算をボトムアップな手順で行う場合は、計算を行うことができる $x_0$ から、添え字の小さい順に計算を行います。

一方、__トップダウン__ な処理では、__求めたい値__ を表す $x_n$ __から順に__ 計算を行います。

### トップダウンな再帰呼び出しの処理の流れ

具体例として、$x_9$ をトップダウンな手順で計算する手順を以下に示します。

* $x_9 = x_8+9$ を最初に計算しようとする
* $x_9$ を計算するためには $x_8$ の値が必要なので、$x_8 = x_7+8$ を計算しようとする
* $x_8$ を計算するためには $x_7$ の値が必要なので、$x_7 = x_6+7$ を計算しようとする
* 略
* $x_2$ を計算するためには $x_1$ の値が必要なので、$x_1 = x_0 + 1$ を計算しようとする
* $x_1$ を計算するためには $x_0$ の値が必要で、$x_1 = 0$ である
* $x_0$ が計算できたので $x_1 = x_0 + 1$ が計算できるようになり、$x_1 = 0 + 1 = 1$ である
* $x_1$ が計算できたので $x_2 = x_1 + 2$ が計算できるようになり、$x_2 = 1 + 2 = 3$ である
* 略 
* $x_8$ が計算できたので $x_9 = x_8 + 9$ が計算できるようになり、$x_9 = 36 + 9 = 45$ である

:::note warn
ボトムアップとトップダウンな処理をまとめると以下のようになります。

* __ボトムアップ__ な処理では、__必要なデータが全て揃っている式から__ 計算をはじめる
* __トップダウン__ な処理では、以下のような手順で計算を行う
    * __求める答えを計算する式から__ 計算を試みる
    * その式を計算するために __必要なデータが揃っていない場合__ は、__そのデータを計算するための式の計算を試みる__ という手順を繰り返す
    * __必要なデータが揃った__ 式から順に計算を行う。その際には、後から作られた式から順番に計算が行われる
:::

### トップダウンな再帰呼び出しを行う関数の定義

処理の手順がわかったので、上記の手順でトップダウンな再帰呼び出しで 0 から n までの整数の合計を計算する、下記のような関数を定義する事にします。

__名前__：トップダウン（top down）な再帰呼び出し（recursive call）で合計（sum）を計算するので `sum_by_tr` とする
__処理__：$x_n$ を計算する
__入力__：仮引数 `n` に $x_n$ の `n` を代入する
__出力__：$x_n$ を返り値として返す

トップダウンな再帰呼び出しでは、下記の __漸化式を使って__ `sum_by_tr` を、以下のような考え方で定義します。

$x_n = x_{n-1} + n$、$x_0=0$

* `sum_by_tr` が正しく定義できていれば、`sum_by_tr(n)` によって $x_n$ が計算できる
* 同様に $x_{n - 1}$ は `sum_by_tr(n - 1)` で計算できる
* $x_n$ は、$x_n = x_{n-1}+ n$ という式で計算できるので、`sum_by_tr` は、`sum_by_tr(n - 1) + n` を計算し、返り値として返す処理を行う
* ただし、$x_0 = 0$ なので、`n` が 0 の場合は 0 を返すよう処理を行う

下記は、そのように `sum_by_tr` を定義したプログラムです。プログラムを見ればわかるように、この関数では、__漸化式をそのままプログラムに記述している__ ので、for 文と比較して、__簡潔にプログラムを記述__ することができます。

* __2、3 行目__：`n` が `0` の場合は $x_0 = 0$ なので、`0` を返す
* __4 行目__：$x_n = x_{n-1} + n$ を表す式を計算し、その計算結果を返す

```python
1  def sum_by_tr(n):
2      if n == 0:
3          return 0
4      return sum_by_tr(n - 1) + n
```

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

```python
def sum_by_tr(n):
    if n == 0:
        return 0
    return sum_by_tr(n - 1) + n
```
</details>

上記の実行後に、下記のプログラムを実行して $x_0$ ~ $x_9$ を計算すると、実行結果から正しい答えが計算されることが確認できます。

```python
for i in range(10):
    print(i, sum_by_tr(i))
```

実行結果

```
0 0
1 1
2 3
3 6
4 10
5 15
6 21
7 28
8 36
9 45
```

:::note warn
漸化式で表される計算は、__漸化式が表す処理をそのまま記述__ する関数を定義する事で、__トップダウンな再帰呼び出し__ の処理で計算することができる。
:::

### 処理の流れの確認

__トップダウンな再帰呼び出し__ の __処理の流れがわかる__ ように、下記のプログラムのように `sum_by_tr` の処理の途中経過を `print` で表示するように修正します。

* __1 行目__：`sum9` では、仮引数 `i` が呼び出した回数を表していたが、`sum_by_tr` では呼び出した回数を直接表す仮引数は存在しない。そこで、呼び出した回数の代わりに再帰呼び出しの __深さを代入する仮引数 `depth`__ をデフォルト値が 0 のデフォルト引数として追加した
* __2 行目__：`sum_by_tr` が呼び出された際に、深さと仮引数 `n` の値を表示する
* __4、7 行目__：`sum_by_tr` の返り値を表示する。なお、`sum_by_tr` の返り値は、仮引数 `n` に対応する $x_n$ を表すので、メッセージに x_n を表記した
* __6 行目__：返り値を表示できるように `retval` に代入する。また、`sum_by_tr` を __再帰呼び出しした際__ に、__その深さは `depth + 1` になる__ ので、実引数にその式を記述した 

なお、`sum_by_tr` には深さを表す仮引数 `depth` を追加しましたが、`depth` はメッセージの表示のみで利用し、返り値の計算では利用していないので、計算結果は変わりません。

```python
1  def sum_by_tr(n, depth=0):
2      print(f"深さ {depth} の呼び出し。n = {n}")   
3      if n == 0:
4          print(f"深さ {depth} の返り値(x_{n}) = 0")   
5          return 0
6      retval = sum_by_tr(n - 1, depth + 1) + n
7      print(f"深さ {depth} の返り値(x_{n}) = {retval}")   
8      return retval
```

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

```python
def sum_by_tr(n, depth=0):
    print(f"深さ {depth} の呼び出し。n = {n}")   
    if n == 0:
        print(f"深さ {depth} の返り値(x_{n}) = 0")   
        return 0
    retval = sum_by_tr(n - 1, depth + 1) + n
    print(f"深さ {depth} の返り値(x_{n}) = {retval}")   
    return retval
```
</details>

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

```diff_python
-def sum_by_tr(n):
+def sum_by_tr(n, depth=0):
+   print(f"深さ {depth} の呼び出し。n = {n}")   
    if n == 0:
+       print(f"深さ {depth} の返り値(x_{n}) = 0")   
        return 0
-   return sum_by_tr(n - 1) + n
+   retval = sum_by_tr(n - 1, depth + 1) + n
+   print(f"深さ {depth} の返り値(x_{n}) = {retval}")   
+   return retval
```
</details>

上記の修正後に、下記のプログラムを実行して $x_9$ の計算の処理の流れを表示します。

```python
print(sum_by_tr(9))
```

実行結果

```
深さ 0 の呼び出し。n = 9
深さ 1 の呼び出し。n = 8
深さ 2 の呼び出し。n = 7
深さ 3 の呼び出し。n = 6
深さ 4 の呼び出し。n = 5
深さ 5 の呼び出し。n = 4
深さ 6 の呼び出し。n = 3
深さ 7 の呼び出し。n = 2
深さ 8 の呼び出し。n = 1
深さ 9 の呼び出し。n = 0
深さ 9 の返り値(x_0) = 0
深さ 8 の返り値(x_1) = 1
深さ 7 の返り値(x_2) = 3
深さ 6 の返り値(x_3) = 6
深さ 5 の返り値(x_4) = 10
深さ 4 の返り値(x_5) = 15
深さ 3 の返り値(x_6) = 21
深さ 2 の返り値(x_7) = 28
深さ 1 の返り値(x_8) = 36
深さ 0 の返り値(x_9) = 45
45
```

実行結果から、$x_9$ を計算するトップダウンな再帰呼び出しの処理では、先程説明した通りの手順で、__末端の再帰呼び出しが行われた後__ で、再帰呼び出しの __返り値__ として __0 から 順番に整数の合計が計算されていく__ ことが確認できます。

また、実行結果から、__次の繰り返しの処理の数が増えない__ ので、この処理では __直線的な繰り返し処理__ が行われていることがわかります。

下記の、先程のボトムアップな再帰呼び出しの処理の実行結果と見比べて下さい。

```
 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
```

下記の表は、0 から n までの整数の合計の計算の、ボトムアップな再帰呼び出しと、トップダウンな再帰呼び出しの処理の流れを比較したものです。

|  | ボトムアップ | トップダウン |
|:--|:--|:--|
| 計算の順番  | $x_0$ から始める  | $x_n$ から始める  |
| 合計の計算  | 仮引数を使って行う  | 返り値を使って行う  |
| 計算の開始  | 深さ 0 の再帰呼び出しから行われる  | 末端の再帰呼び出しから行われる  |
| 計算の完了  | 末端の再帰呼び出し  | 深さ 0 の再帰呼び出し  |
| 返り値の意味| 全ての返り値が $x_n$ を表す | 計算の途中経過を表す |
| 関数の記述 | for 文、while 文と同様の内容 | 漸化式をそのまま記述する |

:::note warn
* __ボトムアップ__ な再帰呼び出しでは、計算の __途中経過__ を __実引数__ で次の再帰呼び出しの __関数に渡し__、渡されたデータが代入された __仮引数を使って計算を行う__。また、すべての再帰呼び出しでは、__最終的な計算結果__ を __返り値で返す__
* __トップダウン__ な再帰呼び出しでは、__必要なデータの計算__ を再帰呼び出しによって __依頼__ し、__その返り値を使って計算を行う__。関数の返り値にはその関数で行った __途中経過の計算結果を返す__
:::

:::note
for 文や while 文を使って $x_n$ をトップダウンな順番で繰り返し処理を記述することは可能ですが、かなり複雑なプログラムになるので、本記事では紹介しません。
:::

## 直前の計算結果のみが使われる漸化式の性質

0 から n までの合計を計算する下記の $x_n$ の漸化式では、$x_n$ を計算する際に、過去の計算結果は __直前の計算結果__ である $x_{n-1}$ __のみが使われています__。

$x_n = x_{n-1} + n$、$x_0 = 0$

このような __直前の計算結果のみ__ で表される __漸化式__ の計算は、ボトムアップとトップダウンの __どちらの手順でも直線的な繰り返し処理__ によって計算を行うことができます。その理由について少し考えてみて下さい。

__ボトムアップ__ な手順の場合は $x_0$ から始まり、$x_n$ まで順番に計算を行いますが、その際には過去に計算済の値を使って __即座に計算を行うことができる__ ので、__必ず n 回__ の __直線的な計算の繰り返し__ で $x_n$ を求めることができます。なお、ボトムアップな処理の場合は、[前回の記事](https://qiita.com/ysgeso/items/3a693c2f189845c01f4f#%E7%9B%B4%E5%89%8D%E3%81%AE-2-%E5%9B%9E%E5%88%86%E3%81%AE%E7%B9%B0%E3%82%8A%E8%BF%94%E3%81%97%E5%87%A6%E7%90%86%E3%81%AE%E7%B5%90%E6%9E%9C%E3%82%92%E4%BD%BF%E3%81%86%E4%BE%8B)で紹介した $F_n = F_{n-1} + F_{n -2}$ のような、__直前以外の計算結果を利用する漸化式__ でも、同様の理由で __直線的な繰り返し処理__ で答えを求めることができます。

__トップダウン__ な手順の場合は、$x_n$ から始まり $x_0$ まで __さかのぼって__ 式の計算を行いますが、その繰り返しの際に __計算する必要が生じる__ のは __一つ前の計算結果だけ__ です。従って、$x_n$ から $x_0$ までさかのぼる際には直線的な繰り返しによって __n 個の式__ が作られます。その後、$x_0$ の値がわかった時点で、その値を $x_1$ から $x_n$ までを計算する式に順番に当てはめながら __n 回の計算__ を行うことで $x_n$ を求めることができますが、その繰り返し処理も直線的です。従って、__直前の計算結果のみ__ で表される __漸化式__ の場合は __トップダウン__ な手順によっても __直線的な繰り返し処理__ で答えを求めることができます。

なお、次回の記事で説明しますが、__直前以外__ の計算結果を利用する漸化式を __トップダウン__ な手順で計算する場合は、__繰り返し処理が分岐__ します。

:::note warn
* __直前の計算結果のみ__ で表される __漸化式__ の計算は、ボトムアップとトップダウンの __どちらの手順でも直線的な繰り返し処理__ によって計算を行うことができる

* __漸化式__ の計算は、__ボトムアップ__ な手順で __必ず直線的な繰り返し処理__ によって計算を行うことができる
* __直前以外__ の計算結果を利用する漸化式を __トップダウン__ な手順で計算すると、 __繰り返し処理が分岐する__
:::

## どの繰り返し処理を利用すべきか

再帰呼び出しは、初心者にはわかりづらいので [以前の記事](https://qiita.com/ysgeso/items/9d5e9a56f5fe004dafee#%E5%86%8D%E5%B8%B0%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97)では、while 文で記述した 0 から 9 までの合計を計算する処理を、再帰呼び出しで書き換えるという方法で説明を行いました。そのため、その際に記述した `sum9` による再帰呼び出しでは、while 文と同様のボトムアップ手順で繰り返し処理が計算が行われます。

下記の while 文によるプログラムと、ボトムアップな再帰呼び出しによるプログラムを比較してみて下さい。おそらく、再帰呼び出しのほうがわかりづらいと思う人が多いのではないかと思います。また、[以前の記事](https://qiita.com/ysgeso/items/9d5e9a56f5fe004dafee#%E5%87%A6%E7%90%86%E6%99%82%E9%96%93%E3%81%AE%E9%81%95%E3%81%84)で説明したように、下記の 2 つのプログラムは、while 文で記述したほうが処理時間が短くなるという問題と、[以前の記事](https://qiita.com/ysgeso/items/9d5e9a56f5fe004dafee#%E5%86%8D%E5%B8%B0%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97%E3%81%AB%E3%82%88%E3%82%8B%E7%84%A1%E9%99%90%E3%83%AB%E3%83%BC%E3%83%97%E3%81%8C%E3%82%A8%E3%83%A9%E3%83%BC%E3%81%AB%E3%81%AA%E3%82%8B%E7%90%86%E7%94%B1) で説明したように、再帰呼び出しには繰り返しの回数に制限があるという問題があります。

従って、例外はあると思いますが、一般的には、__直前の計算結果のみ__ を使って、次の繰り返し処理の計算を行う場合は、ボトムアップな再帰呼び出しよりは、__for 文や while 文を使って記述したほうが良い__ と思います。

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

print(total)
```

```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))        
```

一方、トップダウンな再帰呼び出しの場合は、下記のプログラムのように漸化式をそのまま記述することで簡潔に記述できるという利点があります。

```python
def sum_by_tr(n):
    if n == 0:
        return 0
    return sum_by_tr(n - 1) + n
```

ただし、先程説明した計算速度と繰り返しの回数の問題がという欠点があるので、一般的には for 文や while 文で記述したほうが良いと思います。

# 直前以外の計算結果を利用する漸化式の計算

今回の記事の最初で、直前の計算結果以外を利用する繰り返し処理を、再帰呼び出しを使えば、簡潔に記述できる場合があると説明しました。そこで、直前以外の計算結果を利用する漸化式を例としてそのことを示します。

なお、今回の記事では直線的な繰り返し処理を扱います。先ほど説明したように、__漸化式はボトムアップな手順__ によって、__直線的な繰り返し処理__ で計算を行うことができるので、今回の記事ではボトムアップな再起呼び出しについて説明します。

:::note
直前以外の計算結果を利用する漸化式をトップダウンな手順によって計算すると、繰り返し処理が分岐するので、その方法については次回の記事で説明します。
:::

具体的には、[前回の記事](https://qiita.com/ysgeso/items/3a693c2f189845c01f4f#%E7%9B%B4%E5%89%8D%E3%81%AE-2-%E5%9B%9E%E5%88%86%E3%81%AE%E7%B9%B0%E3%82%8A%E8%BF%94%E3%81%97%E5%87%A6%E7%90%86%E3%81%AE%E7%B5%90%E6%9E%9C%E3%82%92%E4%BD%BF%E3%81%86%E4%BE%8B)で紹介した、__直前の 2 回分__ の繰り返し処理の結果を使う必要がある、フィボナッチ数 $F_n$ の計算を再帰呼び出しで記述します。

フィボナッチ数 $F_n$ は下記の漸化式で計算でき、[前回の記事](https://qiita.com/ysgeso/items/3a693c2f189845c01f4f#%E7%9B%B4%E5%89%8D%E3%81%AE-2-%E5%9B%9E%E5%88%86%E3%81%AE%E7%B9%B0%E3%82%8A%E8%BF%94%E3%81%97%E5%87%A6%E7%90%86%E3%81%AE%E7%B5%90%E6%9E%9C%E3%82%92%E4%BD%BF%E3%81%86%E4%BE%8B)では for 文 でボトムアップな手順で繰り返し処理を行う方法について説明しました。

$F_n = F_{n-1}+F_{n-2}$、$F_0 = 0$、$F_1 = 1$

## for 文で計算する方法のおさらい

下記は、$F_n$ を for 文で計算する `fib_by_f` の定義です。

```python
 1  def fib_by_f(n):
 2      if n == 0:
 3          return 0
 4      elif n == 1:
 5          return 1
 6    
 7      fib_p2 = 0
 8      fib_p1 = 1
 9      for i in range(2, n + 1):
10          fib = fib_p1 + fib_p2
11          fib_p2 = fib_p1
12          fib_p1 = fib
13      return fib
```

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

```python
def fib_by_f(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    
    fib_p2 = 0
    fib_p1 = 1
    for i in range(2, n + 1):
        fib = fib_p1 + fib_p2
        fib_p2 = fib_p1
        fib_p1 = fib
    return fib
```
</details>

このプログラムの __面倒な点__ は、以下の処理を記述する必要がある点です

* 1 つ前と 2 つ前の __計算結果__ を `fib_p1` と `fib_p2` という変数で __記録しておく必要がある__
* 繰り返しの処理を行うたびに、`fib_p1` と `fib_p2` の値を __更新する必要がある__

## ボトムアップな再帰呼び出しを行う関数の定義
ボトムアップな再帰呼び出しで $F_n$ を計算する方法を紹介します。__計算の手順__ は __`fib_by_f` と同じ__ です。また、関数の定義の記述は `sum_by_br` と似ています。そこで、上記の `fib_by_f` と下記の `sum_by_br` の定義を参考にしながら作業を進めることにします。

```python
def sum_by_br(n, i=0, total=0):
    if i <= n:
        total += i
        i += 1
        return sum_by_br(n, i, total)
    else:
        return total
```


まず、関数の名前を `sum_by_br` にならって、__`fib_by_br`__ と命名することにします。次に、関数の __仮引数__ を考える必要があります。$F_n$ を計算する場合は、計算を行う際に 1 つ前と 2 つ前の $F_n$ の値が必要になりますが、__ボトムアップな再帰呼び出し__ では、そのデータを __仮引数で受け取ります__。そのため、その __2 つのデータを代入する仮引数__ を用意する必要がある事がわかります。そこで、その仮引数の名前を `fib_by_f` と同様に `fib_p1` と `fib_p2` にします。他の仮引数としては、`sum_by_br` と同様の意味を持つ、`n` と `i` が必要になります。

下記は、`fib_by_br` の定義です。プログラムの説明はこの後で行います。

```python
 1  def fib_by_br(n, i=2, fib_p1=1, fib_p2=0):
 2      if n == 0:
 3          return 0
 4      elif n == 1:
 5          return 1
 6        
 7      if i <= n:
 8          fib = fib_p1 + fib_p2
 9          fib_p2 = fib_p1
10          fib_p1 = fib
11          i += 1
12          return fib_by_br(n, i, fib_p1, fib_p2)
13      else:
14          return fib
```

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

```python
def fib_by_br(n, i=2, fib_p1=1, fib_p2=0):
    if n == 0:
        return 0
    elif n == 1:
        return 1
        
    if i <= n:
        fib = fib_p1 + fib_p2
        fib_p2 = fib_p1
        fib_p1 = fib
        i += 1
        return fib_by_br(n, i, fib_p1, fib_p2)
    else:
        return fib_p1
```
</details>

上記のプログラムは、先程のボトムアップで $F_n$ を計算する __`fib_by_f`__ と __全く同じアルゴリズム__ で処理を行うので、`fib_by_f` と `fib_by_br` の処理は、下記の表のように完全に対応します。下記の `fib_by_f` と `fib_by_f` を並べたプログラムと見比べて下さい[^3]。

```python
 1  def fib_by_f(n):               |  def fib_by_br(n, i=2, fib_p1=1, fib_p2=0):
 2      if n == 0:                 |      if n == 0:
 3          return 0               |          return 0
 4      elif n == 1:               |      elif n == 1:
 5          return 1               |          return 1
 6                                 |  
 7      fib_p2 = 0                 |     
 8      fib_p1 = 1                 |     
 9      for i in range(2, n + 1):  |      if i <= n:
10          fib = fib_p1 + fib_p2  |          fib = fib_p1 + fib_p2     
11          fib_p2 = fib_p1        |          fib_p2 = fib_p1
12          fib_p1 = fib           |          fib_p1 = fib
13                                 |          i += 1
14                                 |          return fib_by_br(n, i, fib_p1, fib_p2)
15                                 |      else:
16      return fib                 |          return fib_p1
```

| `fib_by_f` | `fib_by_br` |
|:--|:--|
| 2 ~ 5 行目 の `n` が 0、1 の場合の処理 | 2 ~ 5 行目 |
| 7 行目の `fib_p2 = 0`  | 1 行目のデフォルト引数 `fib_p2=0`|
| 8 行目の `fib_p1 = 1`  | 1 行目のデフォルト引数 `fib_p1=1`|
| 9 行目の `range` の第一引数の `2`  | 1 行目のデフォルト引数 `i=2`  |
| 10 行目の `fib = fib_p1 + fib_p2`  | 10 行目  |
| 11 行目の `fib_p2 = fib_p1`  | 11 行目  |
| 12 行目の `fib_p1 = fib`  | 12 行目  |
| 9 行目の for 文の繰り返しでの `i` の増加  | 13 行目の `i += 1`  |
| 9 行目の for 文の返り値し| 14 行目の再帰呼び出し |
| 9 行目 `range` の第二引数の `n + 1` | 9 行目の `i <= n` | 
| 16 行目 `return fib` | 16 行目 `return fib_p1`| 

`fib_by_br` の 8 行目は `i < n + 1` のほうが `fib_by_f` のプログラムに対応しますが、わかりづらいので `i <= n` としました

`fib_by_br` の 16 行目が `return fib` になっていない点が気になっている人がいるかもしれません。`fib` は `i <= n` が `True` の場合に 10 行目で計算されますが、16 行目は `i <= n` が `False` の場合に実行されるので、__16 行目では `fib` は計算されていません__。そのため、16 行目を `return fib` とするとエラーが発生します。

また、`fib_by_br` の __仮引数 `i` に代入される値__ は、再帰呼び出しが行われるたびに __1 ずつ増えていく__ ので、`i <= n` が `False` の場合は __`i` に `n + 1` が代入__ されています。その場合は、仮引数 `fib_p1` には $F_{n + 1}$ の一つ前の $F_n$ が代入されているので、16 行目で `fib_p1` を返すことで、求める答えである $F_n$ が返されます。これは、`sum_by_br` の最後で、仮引数 `total` の値をそのまま返している点と同じです。

下記のプログラムを実行することで、$F_0$ ~ $F_9$ を `fib_by_f` と `fib_by_br` で計算し、計算結果が並べて表示されます。実行結果からどちらも同じ計算を行うことが確認できます。

```python
for i in range(10):
    print(f"fib({i}) = {fib_by_f(i)}, {fib_by_br(i)}")
```

実行結果

```
fib(0) = 0, 0
fib(1) = 1, 1
fib(2) = 1, 1
fib(3) = 2, 2
fib(4) = 3, 3
fib(5) = 5, 5
fib(6) = 8, 8
fib(7) = 13, 13
fib(8) = 21, 21
fib(9) = 34, 34
```

## for、while 文と再帰呼び出しでのデータの管理の方法の違い

`fib_by_f` では、__次の繰り返し処理で必要__ となる、`i`、`fib_p1`、`fib_p2` の値を __更新して記録しておく__ という処理が必要ですが、__再帰呼び出し__ では __特定の繰り返しの回の処理だけを行う__ ので、`fib_by_br` では関数の中で `i`、`fib_p1`、`fib_p2` の値を更新して __記録しておく必要はありません__。そのため、`fib_by_br` では下記のプログラムの 8 行目のように `fib_by_br` の再帰呼び出しの __実引数__ に直接 __次の計算に必要なデータを表す式を記述__ することができます。なお、下記のプログラムがわかりづらいと思った方は、無理に下記のように修正する必要はありません。

```python
 1  def fib_by_br(n, i=2, fib_p1=1, fib_p2=0):
 2      if n == 0:
 3          return 0
 4      elif n == 1:
 5          return 1
 6      
 7      if i <= n:
 8          return fib_by_br(n, i + 1, fib_p1 + fib_p2, fib_p1)
 9      else:
10          return fib_p1
```

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

```python
def fib_by_br(n, i=2, fib_p1=1, fib_p2=0):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    
    if i <= n:
        return fib_by_br(n, i + 1, fib_p1 + fib_p2, fib_p1)
    else:
        return fib_p1
```
</details>

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

```diff_python
def fib_by_br(n, i=2, fib_p1=1, fib_p2=0):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    
    if i <= n:
-       fib = fib_p1 + fib_p2
-       fib_p2 = fib_p1
-       fib_p1 = fib
-       i += 1
-       return fib_by_br(n, i, fib_p1, fib_p2)
+       return fib_by_br(n, i + 1, fib_p1 + fib_p2, fib_p1)
    else:
        return fib_p1
```
</details>

実行結果は同じなので省略しますが、下記のプログラムで修正したプログラムが正しく動作する事が確認できます。

```python
for i in range(10):
    print(f"fib({i}) = {fib_by_f(i)}, {fib_by_br(i)}")
```

上記のような修正を行う事ができるのは、__for 文や while 文__ と、__再帰呼び出し__ では、__データの管理の方法__ が下記のように __異なる__ からです。__管理すべきデータを減らすことができる__ 分だけ、再帰呼び出しでは __処理の記述を減らす__ ことができます。なお、下記の性質は、次回の記事で説明する、トップダウンな再帰呼び出しでも同様です。

* for 文や while 文では、__計算に必要なデータをすべて自分で管理する必要がある__
* __再帰呼び出し__ では、関数の中では __以下のデータのみを管理__ すれば良い
    * 仮引数で受け取った、その関数での繰り返し処理に必要なデータ
    * 再帰呼び出しで、次の繰り返し処理に実引数で渡すデータ
    * 再帰呼び出しからの返り値のデータ

ただし、再帰呼び出しによって、__全体として管理するデータが減るわけではありません__。確かに __一つ一つ__ の再帰呼び出しの __関数が管理するデータは減ります__ が、管理すべきデータは再帰呼び出しによって呼び出された __複数の関数で分散して管理される__ ため、__全体としては同じだけ__ のデータが扱われます。


上記で示したように、__`fib_by_f`__ と __`fib_by_br`__ は __本質的には同じ処理__ を行います。__`fib_by_br` のほうが__ 上記のように __若干簡潔に__ プログラムを記述できますが、再帰呼び出しの場合は __処理が若干遅くなる点__ と、__繰り返しの回数に制限がある__ という欠点があります。

$F_n$ を計算する場合は、わざわざボトムアップな再帰呼び出しで記述する必要はあまりないと思いますが、例えば $a_n = a_{n-1} + a_{n - 2} + 略 + a_{n - 10}$ のような、漸化式でもっと数多くの直前以外の計算結果を計算するような場合は、記録しておいたデータの更新の処理の記述が大変になるので、ボトムアップな再帰呼び出しを検討しても良いかもしれません。

:::note
少し専門的な話になるので意味が分からない人はこのノードは完全に無視して下さい。また、本記事では末尾再帰最適化は行いません。

再帰呼び出しには、繰り返しの回数の制限という欠点があると説明しましたが、最後の処理が自分自身の再帰呼び出しを行うという、末尾再帰という性質を持つ再帰呼び出しは、末尾再帰最適化という方法を用いることで繰り返しの回数の制限をなくすことができます。なお、`sum_by_br` や `fib_by_br` は末尾再帰の性質を持ちます。

プログラム言語によっては、末尾再帰の性質を持つ再帰呼び出しを記述した場合に、自動的に末尾再帰最適化が行われるようなものがありますが、Python には残念ながらそのような機能はありません。ただし、末尾再帰最適化を行うデコレータを定義する事ができるようです。その記事のリンクと、末尾再帰の Wikipedia のリンクを参考までに下記に記します。
:::

https://tanihito.hatenablog.com/entry/20110119/1295459297

https://blanktar.jp/blog/2013/06/python-tail-recurusion

https://ja.wikipedia.org/wiki/%E6%9C%AB%E5%B0%BE%E5%86%8D%E5%B8%B0

## `fib_by_br` の改良

先程定義した `fib_by_br` は、__`i` に `n` が代入されて呼び出された際__ に、$F_n$ の計算を __`fib_p1 + fib_p2` で行うことができます__ が、その値は実引数で次の再帰呼び出しに渡されて、次の再帰呼び出しの return 文で返されます。そのため、__一回分無駄な再帰呼び出しを行っている__ ことになります。

そのため、`fib_by_br` を下記のプログラムのように修正することで、無駄な再帰呼び出しが行われないように改良することができます。

* __7 行目__：`i <= n` を `i < n` に修正することで、`i` が `n` の場合に else のブロックが実行されるように修正する
* __10 行目__：`i` が `n` の場合は、$F_n$ を表す `fib_p1 + fib_p2` を計算して返すようにする

```python
 1  def fib_by_br(n, i=2, fib_p1=1, fib_p2=0):
 2      if n == 0:
 3          return 0
 4      elif n == 1:
 5          return 1
 6      
 7      if i < n:
 8          return fib_by_br(n, i + 1, fib_p1 + fib_p2, fib_p1)
 9      else:
10          return fib_p1 + fib_p2
```

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

```python
def fib_by_br(n, i=2, fib_p1=1, fib_p2=0):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    
    if i < n:
        return fib_by_br(n, i + 1, fib_p1 + fib_p2, fib_p1)
    else:
        return fib_p1 + fib_p2
```
</details>

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

```diff_python
def fib_by_br(n, i=2, fib_p1=1, fib_p2=0):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    
-   if i <= n:
+   if i < n:
        return fib_by_br(n, i + 1, fib_p1 + fib_p2, fib_p1)
    else:
-       return fib_p1
+       return fib_p1 + fib_p2
```
</details>

実行結果は同じなので省略しますが、下記のプログラムで修正したプログラムが正しく動作する事が確認できます。

```python
for i in range(10):
    print(f"fib({i}) = {fib_by_f(i)}, {fib_by_br(i)}")
```

# 今回の記事のまとめ

今回の記事では、下記の __直線的な繰り返し処理__ に対する __再帰呼び出し__ を紹介しました。

* 直前の計算結果のみが使われる漸化式に対する、ボトムアップな再帰呼び出し
* 直前の計算結果のみが使われる漸化式に対する、トップダウンな再帰呼び出し
* 直前以外の計算結果を利用する漸化式に対する、ボトムアップな再帰呼び出し

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

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

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

# 次回の記事

https://qiita.com/ysgeso/items/9303214ec798a920174e

[^1]:最初に呼び出された `f` は、`f` から呼び出されていないので、再帰呼び出しではありません。そのため、再帰呼び出しの回数を表す深さは 0 になります
[^2]:Python では名前の先頭に `_` をつけると特別な意味を持つようになるので、単に名前を区別するためだけに `_` を使う場合は、末尾に付けたほうが良いでしょう。`_` を先頭に付けた場合の特別な意味については、必要があれば今後の記事で説明します
[^3]:このプログラムは、比較するために同じ行に異なる関数の処理を横に並べて記述したものなので、実際に実行することはできません