Pythonで〇×ゲームのAIを一から作成する　その103　複数の項で表される漸化式のトップダウンな再帰呼び出しによる計算

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/8432194829a4c6cc95f0

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

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

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

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

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

# 漸化式に対する繰り返し処理の説明の訂正

[前回の記事](https://qiita.com/ysgeso/items/8432194829a4c6cc95f0#%E7%9B%B4%E5%89%8D%E3%81%AE%E8%A8%88%E7%AE%97%E7%B5%90%E6%9E%9C%E3%81%AE%E3%81%BF%E3%81%8C%E4%BD%BF%E3%82%8F%E3%82%8C%E3%82%8B%E6%BC%B8%E5%8C%96%E5%BC%8F%E3%81%AE%E6%80%A7%E8%B3%AA)では、以下のような説明を行いましたが、__正確ではなかったので訂正__ します。なお、深刻な間違いではないような気がするので、過去の記事の内容はそのままにします。

* __直前の計算結果のみ__ で表される __漸化式__ の計算は、ボトムアップとトップダウンの __どちらの手順でも[直線的な繰り返し処理](https://qiita.com/ysgeso/items/8432194829a4c6cc95f0#%E7%9B%B4%E7%B7%9A%E7%9A%84%E3%81%AA%E7%B9%B0%E3%82%8A%E8%BF%94%E3%81%97%E5%87%A6%E7%90%86%E3%82%92%E8%A1%8C%E3%81%86%E5%86%8D%E5%B8%B0%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97)__ によって計算を行うことができる

* __漸化式__ の計算は、__ボトムアップ__ な手順で __必ず直線的な繰り返し処理__ によって計算を行うことができる
* __直前以外__ の計算結果を利用する漸化式を、__トップダウン__ な手順で計算すると、 __[繰り返し処理が分岐](https://qiita.com/ysgeso/items/8432194829a4c6cc95f0#%E7%9B%B4%E7%B7%9A%E7%9A%84%E3%81%AA%E7%B9%B0%E3%82%8A%E8%BF%94%E3%81%97%E5%87%A6%E7%90%86%E3%82%92%E8%A1%8C%E3%81%86%E5%86%8D%E5%B8%B0%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97)する__

上記では、__直前の計算結果のみ__ で表されるかどうかで分類していますが、厳密には __直前__ である必要はなく、__以前の 1 つの計算結果のみ__ で表されるかどうかがで分類します。

例えば、下記は以下のような計算を行う漸化式です。

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

* $n$ が偶数の場合は 0 から $n$ までの偶数の合計を計算する
* $n$ が奇数の場合は 1 から $n$ までの奇数の合計を計算する

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


従って、上記の説明を下記のように訂正することにします。なお、$x_n$ のような、漸化式で計算されるもののことを __項__ と呼び、漸化式は __以前の項を使った式__ で記述されるので、以後は __以前の計算結果__ を単に __項__ と表記することにします。

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

* __漸化式__ の計算は、__ボトムアップ__ な手順で __必ず直線的な繰り返し処理__ によって計算を行うことができる
* __複数の項__ で表される漸化式を __トップダウン__ な手順で計算すると、 __繰り返し処理が分岐する__
:::

# 分岐する繰り返し処理を行う再帰呼び出し

前回の記事では直線的な繰り返し処理を行う再帰呼び出しを紹介しましたので、次に __分岐する繰り返し処理__ を行う __再帰呼び出し__ を紹介します。

今回の記事では、分岐する繰り返し処理の中で、複数の項で表される漸化式を、トップダウンな再帰呼び出しによる計算で行う方法について説明します。

# 複数の項で表される漸化式の、トップダウンな再帰呼び出しによる計算

__分岐する繰り返し処理__ を __再帰呼び出しで記述する例__ として __良く取り上げられる__ のが、下記の漸化式で表される __[フィボナッチ数](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 = F_{n-1}+F_{n-2}$、$F_0 = 0$、$F_1 = 1$

[前回の記事]()では $F_n$ をボトムアップな再帰呼び出しによって、直線的な繰り返し処理で計算する方法を紹介しました。一方、$F_n$ を __トップダウン__ な再帰呼び出しで計算すると __分岐する繰り返し処理__ になります。そのことを以下で示します。

## `fib_by_tr` の定義

まず、__トップダウン__ な再帰呼び出しで $F_n$ を計算する関数を定義することにします。関数の名前は、再帰呼び出し（recursive call）をトップダウン（topdown）で行うことから、__`fib_by_tr`__ とします。

`fib_by_tr` で行う処理は、[前回の記事](https://qiita.com/ysgeso/items/8432194829a4c6cc95f0#%E3%83%88%E3%83%83%E3%83%97%E3%83%80%E3%82%A6%E3%83%B3%E3%81%AA%E5%86%8D%E5%B8%B0%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97%E3%82%92%E8%A1%8C%E3%81%86%E9%96%A2%E6%95%B0%E3%81%AE%E5%AE%9A%E7%BE%A9)で定義した __`sum_by_tr`__ と __同様__ で、$F_n$ を計算する漸化式を表す処理をそのまま記述します。

具体的には、`fib_by_tr` を `sum_by_tr` と同様の、以下のような考え方で定義します。

* `fib_by_tr` が正しく定義できていれば、`fib_by_tr(n)` によって $F_n$ が計算できる
* 同様に $F_{n - 1}$ は `fib_by_tr(n - 1)` で計算できる
* 同様に $F_{n - 2}$ は `fib_by_tr(n - 2)` で計算できる
* $F_n$ は、$F_n = F_{n-1}+F_{n-2}$ という式で計算できるので、`fib_by_tr` の中では、`fib_by_tr(n - 1) + fib_by_tr(n - 2)` を計算し、返り値として返す処理を行う
* ただし、$F_0 = 0$、$F_1 = 1$ から、`n` が 0 と 1 の場合は、それぞれ 0 と 1 を返す

下記は、そのように `fib_by_tr` を定義したプログラムです。プログラムを見ればわかるように、この関数では、__漸化式を表す処理をそのまま記述__ しているので、for 文やボトムアップな再帰呼び出しと比較して、__簡潔にプログラムを記述__ することができます。

* __2 ~ 5 行目__：`n` が `0` と `1` の場合は $F_0 = 0$、$F_1 = 1$ なので、その値を返す
* __7 行目__：$F_n = F_{n-1} + F_{n-2}$ を表す式を計算し、その計算結果を返り値として返す

```python
1  def fib_by_tr(n):
2      if n == 0:
3          return 0
4      elif n == 1:
5          return 1   
6
7      return fib_by_tr(n - 1) + fib_by_tr(n - 2)
```

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

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

下記の for 文を使った __[`fib_by_f`](https://qiita.com/ysgeso/items/3a693c2f189845c01f4f#for-%E6%96%87%E3%81%AB%E3%82%88%E3%82%8B%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0%E3%81%AE%E8%A8%88%E7%AE%97)__ の定義と比較してみて下さい。__共通する 2 ~ 5 行目__ の `n` が 0 と 1 の場合の処理を __除いた処理__ は、圧倒的に __`fib_by_tr` のほうが簡潔__ です。

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

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

```python
for i in range(10):
    print(f"fib({i}) = {fib_by_f(i)}, {fib_by_tr(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
```

## `fib_by_f` との違い

[前回の記事](https://qiita.com/ysgeso/items/8432194829a4c6cc95f0#forwhile-%E6%96%87%E3%81%A8%E5%86%8D%E5%B8%B0%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97%E3%81%A7%E3%81%AE%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AE%E7%AE%A1%E7%90%86%E3%81%AE%E6%96%B9%E6%B3%95%E3%81%AE%E9%81%95%E3%81%84)の再掲になりますが、__for 文や while 文__ と、__再帰呼び出し__ では、__データの管理の方法__ が下記のように __異なります__。__管理すべきデータを減らすことができる__ 分だけ、再帰呼び出しでは __処理の記述を減らす__ ことができます。

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

$F_n$ を計算するトップダウンな再帰呼び出しでは、$F_n = F_{n-1}+F_{n-2}$ を __計算するために必要な__  $F_{n-1}$ と $F_{n-2}$ の計算を、__再帰呼び出しによって別の関数に委託__ し、その __結果を返り値で受け取ることで計算を行う__ ため、$F_{n-1}$ と $F_{n-2}$ を計算するためのデータを __管理する必要はありません__。それが、プログラムを簡潔に記述できる理由です。

## `fib_by_br` の違い

下記のプログラムのように、トップダウンな再帰呼び出しを行う `fib_by_tr` は、ボトムアップな再帰呼び出しを行う `fib_by_br` と比べても __簡潔に__、見た目が __わかりやすく__ プログラムを記述することができます。その理由について少し考えてみて下さい。

```python
def fib_by_tr(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1   
        
    return fib_by_tr(n - 1) + fib_by_tr(n - 2)
    
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_by_tr` のほうが __わかりやすく見える理由__ は、`return fib_by_tr(n - 1) + fib_by_tr(n - 2)` のように、プログラムの中に __漸化式と同じ式をそのまま記述できる点__ でしょう。また、__この式__ が $F_n = F_{n-1} + F_{n-2}$ を __計算している__ ことは、__一目瞭然__ でしょう。

一方、`fib_by_br` では、再帰呼び出しを表す `fib_by_br(n, i + 1, fib_p1 + fib_p2, fib_p1)` の実引数の中の __`fib_p1 + fib_p2`__ が $F_n = F_{n-1} + F_{n-2}$ を __計算しています__ が、そのことは __実引数が 4 つもある__ ため直観的には __わかりづらい__ のではないかと思います。

### 仮引数が 1 つだけで済む

`fib_by_br` の仮引数が 4 つ必要になる理由は、以下の通りです。なお、$F_0$ と $F_1$ の計算は両者で同じなので、下記は $n$ が 2 以上の $F_n$ を計算する場合の説明です。

* ボトムアップな処理では、$F_2$ から順番に $F_n$ までの計算を行うが、その際に、__何番目を計算しているかを記録__ する必要がある。それが `i` という仮引数である
* 再帰呼び出しの処理を $F_n$ で __終わらせるため__ には、__$n$ の値が必要__ になる。それが `n` という仮引数と、`if i <= n:` という条件分岐である。なお、`fib_by_tr` と異なり、`fib_by_br` の再帰呼び出しの処理の中で __`n` の値は変化しない__ 点に注意すること
* $F_n$ を計算するためには、$F_{n-1}$ と $F_{n-2}$ の値が必要になる。それが `fib_p1` と `fib_p2` という仮引数である

一方、`fib_by_tr` の仮引数が 1 だけで済む理由は、以下の通りです。

* トップダウンな処理では、$F_n$ から順番に計算を行うが、その際に $F_{n-1}$ と $F_{n-2}$ を計算する再帰呼び出しの処理を行う
* 上記から __`n` が小さくなりながら__ 再帰呼び出しが行われるが、$F_0 = 0$ と $F_1 = 1$ なので、`n` が `0` または `1` になった時点で __再帰呼び出しを行う必要がなくなる__。そのため、`fib_by_br` のように、再帰呼び出しを終わらせるための仮引数は必要がない
* $F_n = F_{n-1} + F_{n-2}$ の計算は、`fib_by_br` のように仮引数に代入されたデータを使うのではなく、$F_{n-1}$ と $F_{n-2}$ を計算する __再帰呼び出しの返り値を使って行う__ ので、そのための仮引数は必要がない

上記のように、__`fib_by_tr`__ では、$F_n$ を計算する際に必要となる $F_{n-1}$ と $F_{n-2}$ の計算結果を __直接管理していない__ ことが、簡潔に記述できる理由です。

### 再帰呼び出しの末端の処理の違い

他にも、`fib_by_tr` では、`if i <= n:` という __条件文によって__、再帰呼び出しを行うかどうかを __判定している__ 点がわかりづらく見えるかもしれません。このような違いが生じるのは、__[再帰呼び出しの末端](https://qiita.com/ysgeso/items/8432194829a4c6cc95f0#%E5%86%8D%E5%B8%B0%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97%E3%81%AE%E6%B7%B1%E3%81%95%E3%81%A8%E6%9C%AB%E7%AB%AF)で行われる処理__ が、`fib_by_tr` と `fib_by_br` で __異なる__ からです。

`fib_by_tr` では、再帰呼び出しを行うたびに、__仮引数 `n`__ に代入される値が __減っていきます__。そのため、再帰呼び出しの __末端__ では、`n` が 0 または 1 になり、再帰呼び出しではない __`return 0`__ または __`return 1`__ が実行されます。従って、`n` が 0 または 1 の場合の処理は、再帰呼び出しの計算の中で __必ず実行されます__。

`fib_by_br` では、再帰呼び出しを行うたびに、__仮引数 `i`__ に代入される値が __増えていきます__。そのため、`n` が 2 以上の場合は、__再帰呼び出しを止めるための条件式を記述__ する必要があります。それが、`if i <= n:` という条件文で、再帰呼び出しの __末端__ ではこの条件式が `False` になるため、再帰呼び出しではない __`return total`__ が実行されます。また、__`n` が 2 以上__ の場合は __`return 0` と `return 1` は決して実行されません__。

## 計算速度の問題

`fib_by_tr` にはプログラムを簡潔に記述できるという利点がありますが、その一方で __重大な欠点__ があります。それは $n$ が __大きくなる__ と、$F_n$ 数を計算する __処理時間が急激に増える__ という問題です。

例えば、$F_{40}$ を下記のプログラムで `fib_by_tr` で計算すると、筆者のパソコンでは約 20 秒の時間がかかりました。また、もっと大きな $n$ で $F_n$ を計算すると、具体的な処理時間についてはこの後で説明しますが、__急激に処理時間が増える__ ようになります。

```python
print(fib_by_tr(40))
```

実行結果

```
102334155
```

一方、同じ $F_{40}$ を下記のプログラムで `fib_by_f` や `fib_by_bf` で計算すると、同じ結果が表示されますが、どちらも一瞬で計算が終了します。


```python
print(fib_by_f(40))
print(fib_by_br(40))
```

実行結果

```
102334155
102334155
```

## `fib_by_tr` の処理の流れ

このような大きな差が生じる理由を理解するためには、$F_n$ をトップダウンな再帰呼び出しで計算を行った際の __処理の流れを理解する__ 必要があります。そこで、処理の流れを `print` で表示するように `fib_by_tr` を修正することにします。この修正は、[前回の記事](https://qiita.com/ysgeso/items/8432194829a4c6cc95f0#%E5%87%A6%E7%90%86%E3%81%AE%E6%B5%81%E3%82%8C%E3%81%AE%E7%A2%BA%E8%AA%8D)で `sum_by_tr` に対して行ったものとほぼ同じです。

ただし、今回は以下のような工夫を行いました。

* `fib_by_tr` と表記するのは長いので、メッセージでは `fib` と表記する
* 再帰呼び出しの __深さだけ__ メッセージを __2 文字ずつインデント__ して右にずらして表示する。インデントを行うことで、メッセージを表示した __再帰呼び出しの深さが明確になる__
* __`+`__ 演算子は __先頭から計算が行われる__ ので、`fib_by_tr(n-1) + fib_by_tr(n-2)` という式は、先頭の __`fib_by_tr(n-1)` から順__ に再帰呼び出しが行われる。そこで `fib_by_tr(n-1)` と `fib_by_tr(n-2)` の再帰呼び出しを __順番に別々に行い__、__その前後__ に計算の __途中経過と結果を表すメッセージを表示__ するようにした


再帰呼び出しで __深さを考慮に入れた計算__ を行う場合は、__深さを表す仮引数を用意__ し、再帰呼び出しを行う際に、__深さに 1 を足した実引数を記述__ することで行います。

下記はそのように `fib_by_tr` を修正したプログラムです。

* __1 行目__：再帰呼び出しの深さを表す仮引数 `depth` を追加する。最初に呼び出された関数の深さは `0` なので、デフォルト値を `0` とするデフォルト引数とした
* __2 行目__：__2 文字の半角の空白__ に `* depth` を計算することで、インデントを表す __深さの数 * 2 文字分の半角の空白__ を計算し、`indent` に代入する
* __4、7 行目__：`n` が `0` と `1` の場合の計算結果をインデントの後に表示する
* __10、12 行目__：`fib_by_tr` の再帰呼び出しを行う際に、次の深さを表す `depth + 1` を実引数に記述するようにする
* __10、12、13 行目__：計算の途中経過を表示できるように、`fib_by_tr(n-1)` と `fib_by_tr(n-2)` のそれぞれの返り値と、合計の計算結果を変数に代入する
* __9、11、14 行目__：計算の途中経過と結果を、インデントの後に表示する

```python
 1  def fib_by_tr(n, depth=0):
 2      indent = "  " * depth
 3      if n == 0:
 4          print(f"{indent}fib(0) = 0")
 5          return 0
 6      elif n == 1:
 7          print(f"{indent}fib(1) = 1")
 8          return 1   
 9      print(f"{indent}fib({n}) = fib({n - 1}) + fib({n - 2})")
10      r1 = fib_by_tr(n - 1, depth + 1)
11      print(f"{indent}fib({n}) = {r1} + fib({n - 2})")
12      r2 = fib_by_tr(n - 2, depth + 1)
13      retval = r1 + r2
14      print(f"{indent}fib({n}) = {r1} + {r2} = {retval}")
15      return retval
```

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

```python
def fib_by_tr(n, depth=0):
    indent = "  " * depth
    if n == 0:
        print(f"{indent}fib(0) = 0")
        return 0
    elif n == 1:
        print(f"{indent}fib(1) = 1")
        return 1   
    print(f"{indent}fib({n}) = fib({n - 1}) + fib({n - 2})")
    r1 = fib_by_tr(n - 1, depth + 1)
    print(f"{indent}fib({n}) = {r1} + fib({n - 2})")
    r2 = fib_by_tr(n - 2, depth + 1)
    retval = r1 + r2
    print(f"{indent}fib({n}) = {r1} + {r2} = {retval}")
    return retval
```
</details>

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

```diff_python
-def fib_by_tr(n):
+def fib_by_tr(n, depth=0):
+   indent = "  " * depth
    if n == 0:
+       print(f"{indent}fib(0) = 0")
        return 0
    elif n == 1:
+       print(f"{indent}fib(1) = 1")
        return 1   
-   return fib_by_tr(n - 1) + fib_by_tr(n - 2)
+   print(f"{indent}fib({n}) = fib({n - 1}) + fib({n - 2})")
+   r1 = fib_by_tr(n - 1, depth + 1)
+   print(f"{indent}fib({n}) = {r1} + fib({n - 2})")
+   r2 = fib_by_tr(n - 2, depth + 1)
+   retval = r1 + r2
+   print(f"{indent}fib({n}) = {r1} + {r2} = {retval}")
+   return retval
```
</details>

下記は、上記の `fib_by_tr` を使って $F_4$ を計算するプログラムで、実行結果のように計算の途中経過が表示されます。なお、コメントの部分は筆者が加筆したものです。

```python
print(fib_by_tr(4))
```

実行結果

```
fib(4) = fib(3) + fib(2)       # fib(4) の 9 行目の表示
  fib(3) = fib(2) + fib(1)     # fib(4) から呼び出された fib(3) の 9 行目の表示 
    fib(2) = fib(1) + fib(0)
      fib(1) = 1
    fib(2) = 1 + fib(0)
      fib(0) = 0
    fib(2) = 1 + 0 = 1
  fib(3) = 1 + fib(1)          # fib(4) から呼び出された fib(3) の 11 行目の表示 
    fib(1) = 1
  fib(3) = 1 + 1 = 2           # fib(4) から呼び出された fib(3) の 13 行目の表示 
fib(4) = 2 + fib(2)            # fib(4) の 11 行目の表示
  fib(2) = fib(1) + fib(0)     # fib(4) から呼び出された fib(2) の 9 行目の表示 
    fib(1) = 1
  fib(2) = 1 + fib(0)          # fib(4) から呼び出された fib(2) の 11 行目の表示 
    fib(0) = 0
  fib(2) = 1 + 0 = 1           # fib(4) から呼び出された fib(2) の 13 行目の表示 
fib(4) = 2 + 1 = 3             # fib(4) の 13 行目の表示
```

実行結果では、__同じ深さ__ の再帰呼び出しの __メッセージのインデントは同じ__ になります。また、再帰呼び出しが行われるたびに、2 文字分の半角の空白のインデントが追加され、再帰呼び出しの処理が終了するたびにインデントが戻ります。従って、例えば `fib(4)` から呼び出された __再帰呼び出しの処理__ では、`fib(4)` のメッセージよりも __インデントが多いメッセージが表示__ され、再帰呼び出しの処理がすべて終了した時点で、次の `fib(4)` のメッセージが表示されます。

上記の実行結果の処理の流れは以下のようになります。

* `fib(4)` が呼び出され、`fib(3) + fib(2)` の計算を開始する。__+ 演算子は先頭から処理が行われる__ ので、__`fib(3)` を先に計算する__
    * `fib(3)` が呼び出され、`fib(2) + fib(1)` の計算を開始する。`fib(2)` を先に計算する
        * `fib(2)` が呼び出され、`fib(1) + fib(0)` の計算を開始する。`fib(1)` を先に計算する
            * `fib(1)` が呼び出され、`1` が返る（__再帰呼び出しの末端__）
        * `fib(2)` の `fib(1) + fib(0)` が `1 + fib(0)` になる。残りの `fib(0)` を計算する
            * `fib(0)` が呼び出され、`0` が返る（__再帰呼び出しの末端__）
        * `fib(2)` の `1 + fib(0)` が `1 + 0 = 1` になり、`1` が返る
    * `fib(3)` の `fib(2) + fib(1)` が `1 + fib(1)` になる。残りの `fib(1)` を計算する
        * `fib(1)` が呼び出され、`1` が返る（__再帰呼び出しの末端__）
    * `fib(3)` の `1 + fib(1)` が `1 + 1 = 2` になり、`2` が返る
* `fib(4)` の `fib(3) + fib(2)` が `2 + fib(2)` になる。残りの `fib(2)` を計算する
    * 上記と同様の手順で `fib(2)` が計算され、`1` が返る
* `fib(4)` の `2 + fib(2)` が `2 + 1 = 3` になり、`3` が返る

`fib_by_tr` で複数の再帰呼び出しが行われる際には、下記のような処理が行われます。

* 複数の再帰呼び出しが、__記述された順番__ に行われる
* 行われた再帰呼び出しの __処理がすべて完了してから__ 、次の再帰呼び出しが行われる

また、`fib_by_tr` の再帰呼び出しの処理では、`fib_by_tr(1)` と `fib_by_tr(0)` が呼び出された場合に __再帰呼び出しが行われない__ ので、それらは __再帰呼び出しの末端__ になります。上記のように、`fib_by_tr` で行われる再帰呼び出しの処理には、__複数の末端が存在__ します。

行われた処理の流れを式だけで表すと以下のようになります。下記では、関数が呼び出された場合に計算される式を、その下に () で囲って記述しました。例えば、1 行目の `fib(3)` によって計算される式は、2 行目の () で囲った `(fib(2) + fib(1))` です。

```
fib(4) =   fib(3)                     + fib(2)
       =  (fib(2)           + fib(1)) + fib(2)              
       = ((fib(1) + fib(0)) + fib(1)) + fib(2)
       = ((1      + fib(0)) + fib(1)) + fib(2)
       = ((1      + 0     ) + fib(1)) + fib(2)
       = ( 1                + fib(1)) + fib(2)
       = ( 1                + 1     ) + fib(2)
       =   2                          + fib(2)
       =   2                          + (fib(1) + fib(0))
       =   2                          + (1      + fib(0))
       =   2                          + (1      + 0     )
       =   2                          +  1
       =   3
```

下図は、処理の流れを図に表したものです。赤い矢印が関数呼び出しを、青い矢印が返り値を返す処理を、数字が処理が行われた順番を表します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b2c67133-236a-063f-a58f-8caf97d21bb4.png" width="500">

上図のように、トップダウンな再帰呼び出しによる $F_n$ の計算は、関数内で $F_{n-1}$ と $F_{n-2}$ を計算する __2 つの再帰呼び出しが行われる__ ので、__分岐する繰り返し処理__ が行われます。

:::note warn
同様の理由で、__複数の項で表される漸化式__ を __トップダウンな再帰呼び出しで計算__ すると、__分岐する繰り返し処理__ が行われます。
:::

## 分岐する繰り返し処理の処理時間

一般的に、__分岐する繰り返し処理__ では、繰り返しの __回数が増える__ と __処理の数が爆発的に増える__ という性質があります。例えば、繰り返しのたびに __2 つに分岐__ する場合は、1 回目の繰り返しで 2 回の処理が、2 回目の繰り返しで 2 * 2 = 4 回の処理が、__n 回目の繰り返しで $2^n$ 回__ の処理が必要になります。このような __$x$ を $y$ 回乗算する $x^y$__ という計算を __指数関数__ と呼び、指数関数は $x > 1$ の場合に $y$ が増加すると、__爆発的に増えていく__ という性質があります[^1]。例えば $2^{10} = 約 1000$、$2^{20} = 約 100 万$、$2^{30} = 約 10 憶$ になります。

下図は $0 ≦ x ≦ 9$ の整数の範囲で $y=x$、$y=2^x$、$y=3^x$ をグラフにしたものです。グラフから $y=x$ と比較して、$y=2^x$ や $y=3^x$ が爆発的に増えていく様子がわかります。


<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/150377ad-f5eb-0786-0281-09a9c580f25d.png" width="350">

:::note
上記のグラフは matplotlib を使って下記のプログラムで描画しました。なお、matplotlib でのグラフの描画方法については今後の記事で説明する予定なので、今回の記事では下記のプログラムの説明は行いません。

また、numpy というモジュールを使えばもっと簡潔にプログラムを記述することができますが、numpy はまだ説明していないので利用していません。

```python
import matplotlib.pyplot as plt
import japanize_matplotlib

x_list = [x for x in range(10)]
exp2_list = [ 2 ** x  for x in range(10)]
exp3_list = [ 3 ** x  for x in range(10)]

plt.plot(x_list, x_list, label="$y=x$")
plt.plot(x_list, exp2_list, label="$y=2^x$")
plt.plot(x_list, exp3_list, label="$y=3^x$")
plt.ylim(0, 1000)
plt.legend()
plt.show()
```
:::

何故そのようになるかについての説明は省略しますが、$F_n$ の計算に必要な処理は __n が 1 つ増える__ と __約 1.6 倍__ になります。従って、__$n$ が $k$ 増えると処理時間は約 $1.6^k$ 倍__ になります。先ほどの $F_{40}$ の計算に 2 分もの時間がかかったのは、$1.6^{40} = 1.5 億$ という非常に大きな数になるからです。$n$ を増やしていくと、すぐに $F_n$ の計算が数年かけても計算が終わらないようになります。

別の分岐する繰り返し処理の例として、〇× ゲームの __ゲーム木を作成する処理__ が挙げられます。[ゲーム木の作成](https://qiita.com/ysgeso/items/db7cfe4a1f14d9cb9368#%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%81%AB%E3%82%88%E3%82%8B%E3%82%B2%E3%83%BC%E3%83%A0%E6%9C%A8%E3%81%AE%E4%BD%9C%E6%88%90)では、深さ 0 のルートノードからはじめ、「深さ d のすべてのノードに対して子ノードを作成し、d に 1 を足す」という繰り返し処理を行います。そのため、__複数の子ノードが存在するノード__ では、この __繰り返し処理は分岐します__。そのため、〇×ゲームのゲーム木の __深さは 9__ しかありませんが、全体の __[ノードの数は 50 万以上](https://qiita.com/ysgeso/items/949d18e60939d510c931#%E6%AD%A3%E3%81%97%E3%81%84%E5%90%84%E6%B7%B1%E3%81%95%E3%81%AE%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E6%95%B0%E3%81%AE%E8%A8%88%E7%AE%97%E6%96%B9%E6%B3%95)__ にもなります。

一方、__直線的な繰り返し処理__ の場合は、一般的に繰り返しの __回数に比例した処理時間__ がかかります。そのため、`fib_by_f` を使って $F_{40}$ を計算した際にかかる時間は、$F_1$ の __約 40 倍__ にしかなりません。そのため、__`fib_by_f`__ では、下記のプログラムのように、__かなり大きな $n$ でも $F_n$ を計算することができます__。なお、`fib_by_br` では、再帰呼び出しの繰り返しの回数に制限があるという別の理由から、大きな $n$ の $F_n$ を計算することはできません。

```python
print(fib_by_f(10000))
```

実行結果（とてつもなく大きな数字になります）

```
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
```

:::note warn
* __直線的な繰り返し処理__ の場合は、繰り返しの __回数に比例した処理時間__ がかかる
* __分岐する繰り返し処理__ の場合は、繰り返しの回数が増えると、__指数関数__ に従って処理時間が __爆発的に増える__
:::

:::note
プログラムの処理時間は、計算量という概念で表現されます。ただし、計算量の話をすると長くなるので、その話は今後の記事で紹介しようと思います。
:::

## 計算時間に差が出る理由

__同じ計算を行っている__ にも関わらず `sum_by_f` や `sum_by_br` と `sum_by_tr` の __処理時間が大きく異なる__ 点が気になっている人がいるかもしれません。このような差は、`sum_by_tr` が __無駄な計算を大量に行っている__ ことが原因です。

先程の下記の実行結果を見て下さい。__3 ~ 7 行目__ で `fib(2)` の計算が行われていますが、__全く同じ__ `fib(2)` の計算が __12 ~ 16 行目__ で行われていることがわかります。

```
 1  fib(4) = fib(3) + fib(2)
 2    fib(3) = fib(2) + fib(1)
 3      fib(2) = fib(1) + fib(0)
 4        fib(1) = 1
 5      fib(2) = 1 + fib(0)
 6        fib(0) = 0
 7      fib(2) = 1 + 0 = 1
 8    fib(3) = 1 + fib(1)
 9      fib(1) = 1
10    fib(3) = 1 + 1 = 2
11  fib(4) = 2 + fib(2)
12    fib(2) = fib(1) + fib(0)
13      fib(1) = 1
14    fib(2) = 1 + fib(0)
15      fib(0) = 0
16    fib(2) = 1 + 0 = 1
17  fib(4) = 2 + 1 = 3
```

先程の図を使ってそのことを表すと下図のようになります。下図の __紫色の枠__ で囲まれた部分が __`fib(2)` を計算する処理__ で、__全く同じ処理が 2 回行われている__ ことがわかります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/1e5d5e47-8bb5-753a-c013-10db289e986c.png" width="500">

このような無駄な処理が行われる理由は、[以前の記事](https://qiita.com/ysgeso/items/9d5e9a56f5fe004dafee#%E8%87%AA%E5%88%86%E8%87%AA%E8%BA%AB%E3%82%92%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%99%E3%81%93%E3%81%A8%E3%81%AE%E6%84%8F%E5%91%B3)で説明したように、再帰呼び出しでは自分自身と同じ処理を行う、__新しい別の関数を呼び出す__ という処理が行われるからです。従って、再帰呼び出しで呼び出された `fib_by_tr` は、それぞれが __独立した処理__ を行います。例えば、再帰呼び出しが行われている過程で、__`fib_by_tr(2)` が複数回呼び出された__ としても、それらは独立して処理を行うため、過去に `fib_by_tr(2)` が呼び出されて $F_2$ が __計算済であったとしても__、その値を __別の `fib_by_tr(2)` が利用することはできません__。そのため、`fib_by_tr(2)` が呼び出されるたびに、__同じ計算が何度も行われる__ という無駄が生じます。現実の世界に例えると、__協力して仕事を行わない 2 人の部下に全く同じ指示を与える__ ことに相当します。

[以前の記事](https://qiita.com/ysgeso/items/51c2eba867aa560808c6#%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%81%AF%E4%BD%95%E3%81%8B)で説明したように、__全く同じ計算を行う__ 場合でも、計算の手順を表す __アルゴリズムによって__、計算の速度などの __性質が大きく変わる__ ことが __良くあります__。

再帰呼び出しの計算を行う例として、フィボナッチ数 $F_n$ の計算が良く取り上げられますが、$F_n$ は確かに __プログラムの記述__ は `fib_by_tr` のようにトップダウンな再帰呼び出しで __簡潔に行えます__ が、$n$ が 40 を超えたあたりから __計算時間が長くなりすぎる__ という重大な欠点があります。そのため、実際には $F_n$ を計算するアルゴリズムとして、__トップダウンな再帰呼び出しは向いていない__ と言えます。これは、$F_n$ に限った話ではなく、__複数の項で表される漸化式__ でも同様です。

:::note warn
複数の項で表される漸化式は、ボトムアップな方法で計算したほうが効率が良い。
:::

## メモ化による処理の効率化

上記で説明した重大な欠点があるとはいえ、漸化式をトップダウンな再帰呼び出しで __簡潔に記述できる__ という点は __便利__ です。そこで、同じ処理を大量に行うトップダウンな再帰呼び出しの処理を、__効率的に行う手法__ について紹介します。

問題の原因は、再帰呼び出しによって呼び出された関数の処理が __独立して行われる__ という点なので、再帰呼び出しで行われる処理が、__過去に行われた計算の結果を共有__ することができれば、この問題を解決することができるようになります。

そのような手法の一つに __メモ化（memoization）__[^2]という手法があります。メモ化とは、後から利用される可能性がある計算を行った際に、その __計算結果を記録しておき、再利用する__ という手法です。

:::note
メモ化は、後で利用する可能性があるデータを記憶して取っておく、__キャッシュ__（cache）という __処理の高速化の技術の一種__ です。
:::

メモ化を行う方法の一つに、list や dict などの __ミュータブルなデータに計算結果を記録__ し、そのデータを再帰呼び出しの関数の __仮引数に代入して共有する__ という方法があります[^3]。

:::note
メモ化で利用する dict や list のように、ある値を、別の値に置換（変換）するための表のようなデータの事を、置換表（transposition table）と呼びます。
:::

$F_n$ の場合は、メモ化を行う dict には、キーに $F_n$ の $n$ を、そのキーの値に $F_n$ を記録します。下記は、メモ化を行うように `fib_by_tr` を修正するプログラムです。

下記は、メモ化を利用するように `fib_by_tr` を修正したプログラムです。

* __1 行目__：計算済の $F_n$ を記録する仮引数 `memo` を追加する。デフォルト値を空の dict にすることで、再帰呼び出しの処理を開始する際に、実引数を記述せずに `fib_by_tr` を呼び出すことで、`memo` が空の dict で初期化される
* __3 ~ 8 行目__：`n` が 0 または 1 の場合は、0 または 1 を返すだけで良いので、__メモ化を利用したほうが処理が多くなる__。そのため、この部分は __元のプログラムから変更しない__
* __9 ~ 11 行目__：`memo` に `n` をキーとする要素が存在する場合は、$F_n$ は計算済で `memo[n]` に代入されているので、それを返り値として返す。その際に、`memo` からデータを取り出したことを明確にするためにメッセージに (memo) を表示するようにした
* __13, 15 行目__：`fib_by_tr` を呼び出す際にキーワード引数 `memo=memo` を追加する
* __19 行目__：新しく計算した $F_n$ を `memo[n]` に代入して記録する

```python
 1  def fib_by_tr(n, depth=0, memo={}):
 2      indent = "  " * depth
 3      if n == 0:
 4          print(f"{indent}fib(0) = 0")
 5          return 0
 6      elif n == 1:
 7          print(f"{indent}fib(1) = 1")
 8          return 1   
 9      if n in memo:
10          print(f"{indent}fib({n}) = {memo[n]} (memo)")
11          return memo[n]
12      print(f"{indent}fib({n}) = fib({n - 1}) + fib({n - 2})")
13      r1 = fib_by_tr(n - 1, depth + 1, memo=memo)
14      print(f"{indent}fib({n}) = {r1} + fib({n - 2})")
15      r2 = fib_by_tr(n - 2, depth + 1, memo=memo)
16      retval = r1 + r2
17      print(f"{indent}fib({n}) = {r1} + {r2} = {retval}")
18      memo[n] = retval
19      return retval
```

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

```python
def fib_by_tr(n, depth=0, memo={}):
    indent = "  " * depth
    if n == 0:
        print(f"{indent}fib(0) = 0")
        return 0
    elif n == 1:
        print(f"{indent}fib(1) = 1")
        return 1   
    if n in memo:
        print(f"{indent}fib({n}) = {memo[n]} (memo)")
        return memo[n]
    print(f"{indent}fib({n}) = fib({n - 1}) + fib({n - 2})")
    r1 = fib_by_tr(n - 1, depth + 1, memo=memo)
    print(f"{indent}fib({n}) = {r1} + fib({n - 2})")
    r2 = fib_by_tr(n - 2, depth + 1, memo=memo)
    retval = r1 + r2
    print(f"{indent}fib({n}) = {r1} + {r2} = {retval}")
    memo[n] = retval
    return retval
```
</details>

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

```diff_python
-def fib_by_tr(n, depth=0):
+def fib_by_tr(n, depth=0, memo={}):
    indent = "  " * depth
    if n == 0:
        print(f"{indent}fib(0) = 0")
        return 0
    elif n == 1:
        print(f"{indent}fib(1) = 1")
        return 1   
+   if n in memo:
+       print(f"{indent}fib({n}) = {memo[n]} (memo)")
+       return memo[n]
    print(f"{indent}fib({n}) = fib({n - 1}) + fib({n - 2})")
    r1 = fib_by_tr(n - 1, depth + 1, memo=memo)
    print(f"{indent}fib({n}) = {r1} + fib({n - 2})")
    r2 = fib_by_tr(n - 2, depth + 1, memo=memo)
    retval = r1 + r2
    print(f"{indent}fib({n}) = {r1} + {r2} = {retval}")
+   memo[n] = retval
    return retval
```
</details>

上記の修正後に、下記のプログラムで $F_4$ を計算すると、実行結果の 12 行目のように、一度計算された `fib(2)` を `memo` から取り出すようになったことが確認できます。

```python
print(fib_by_tr(4))
```

実行結果（行番号とコメントを追記しました）

```
 1  fib(4) = fib(3) + fib(2)
 2    fib(3) = fib(2) + fib(1)
 3      fib(2) = fib(1) + fib(0)
 4        fib(1) = 1
 5      fib(2) = 1 + fib(0)
 6        fib(0) = 0
 7      fib(2) = 1 + 0 = 1
 8    fib(3) = 1 + fib(1)
 9      fib(1) = 1
10    fib(3) = 1 + 1 = 2
11  fib(4) = 2 + fib(2)
12    fib(2) = 1 (memo)          # ここでの fib(2) の値はメモ化されたデータを利用している
13  fib(4) = 2 + 1 = 3
```

また、下記のプログラムで $F_{40}$ を計算すると、メッセージからメモ化の利用が何度も行われることが確認できます。また、先程と異なり一瞬で計算が行われることが確認できます。

```python
print(fib_by_tr(40))
```

実行結果

```
fib(40) = fib(39) + fib(38)
  fib(39) = fib(38) + fib(37)
    fib(38) = fib(37) + fib(36)
      fib(37) = fib(36) + fib(35)
        fib(36) = fib(35) + fib(34)
略
                                                          fib(6) = fib(5) + fib(4)
                                                            fib(5) = fib(4) + fib(3)
                                                              fib(4) = 3 (memo)
                                                            fib(5) = 3 + fib(3)
                                                              fib(3) = 2 (memo)
略
    fib(37) = 24157817 (memo)
  fib(39) = 39088169 + 24157817 = 63245986
fib(40) = 63245986 + fib(38)
  fib(38) = 39088169 (memo)
fib(40) = 63245986 + 39088169 = 102334155
102334155
```

### 仮引数 `memo` に関する補足

[以前の記事](https://qiita.com/ysgeso/items/c5dbe62b329f7936181a#%E3%83%87%E3%83%95%E3%82%A9%E3%83%AB%E3%83%88%E5%BC%95%E6%95%B0%E3%81%AB%E9%96%A2%E3%81%99%E3%82%8B%E6%B3%A8%E6%84%8F%E7%82%B9)で、__デフォルト引数のデフォルト値__ を、list や dict のような __ミュータブルなデータにするのは避けたほうが良い__ と説明しました。また、[以前の記事](https://qiita.com/ysgeso/items/1dbfec99a08b8996f53c#%E3%83%90%E3%82%B0%E3%81%AE%E5%8E%9F%E5%9B%A0%E3%81%AE%E6%A4%9C%E8%A8%BC)ではデフォルト値をミュータブルなデータにしたことによるバグを紹介しました。その理由は、ミュータブルなデータをデフォルト値に設定すると、その __仮引数に要素を追加__ したり、__要素の内容を変更__ すると、__デフォルト値が変更されてしまう__ からです。

ただし、`fib_by_tr` の仮引数 `memo` の場合は、この性質が __逆に有効__ になります。その理由は、`fib_by_tr` で __$F_n$ の計算を何度も行う場合__ は、__過去の `fib_by_tr`__ で行った計算の結果を __再利用できると効率が良い__ からです。例えば、先程 `fib_by_tr(40)` を計算した際に、__2 ~ 40 まで__ の $F_n$ を計算したので、__`memo` のデフォルト値にはそれらのデータが記録__ されています。そのため、下記のプログラムのようにもう一度 `fib_by_tr(40)` を実行すると、実行結果から `memo` からデータを取り出すことで計算が行われたことが確認できます。

```python
print(fib_by_tr(40))
```

実行結果

```
fib(40) = 102334155 (memo)
102334155
```

また、下記のプログラムでまだ計算していない $F_{41}$ を計算した場合は、`memo` のデフォルト値に記録された $F_{40}$ と $F_{39}$ を使って、すぐに計算を行うことができることが確認できます。

```python
print(fib_by_tr(41))
```

実行結果

```
fib(41) = fib(40) + fib(39)
  fib(40) = 102334155 (memo)
fib(41) = 102334155 + fib(39)
  fib(39) = 63245986 (memo)
fib(41) = 102334155 + 63245986 = 165580141
165580141
```

:::note
`fib_by_tr` の `memo` のデフォルト値に大量のデータが記録してしまうと、メモリの消費が問題となる場合があります。そのような問題が起きることを防ぎたい場合は、下記のプログラムのように `fib_by_tr` を修正して下さい。



```python
def fib_by_tr(n, depth=0, memo=None):
     if memo is None:
         memo = {}
元と同じなので省略
```

<details><summary><strong>プログラム全体</strong></summary>

```python
def fib_by_tr(n, depth=0, memo=None):
     if memo is None:
         memo = {}
    indent = "  " * depth
    if n == 0:
        print(f"{indent}fib(0) = 0")
        return 0
    elif n == 1:
        print(f"{indent}fib(1) = 1")
        return 1   
    if n in memo:
        print(f"{indent}fib({n}) = {memo[n]} (memo)")
        return memo[n]
    print(f"{indent}fib({n}) = fib({n - 1}) + fib({n - 2})")
    r1 = fib_by_tr(n - 1, depth + 1, memo=memo)
    print(f"{indent}fib({n}) = {r1} + fib({n - 2})")
    r2 = fib_by_tr(n - 2, depth + 1, memo=memo)
    retval = r1 + r2
    print(f"{indent}fib({n}) = {r1} + {r2} = {retval}")
    memo[n] = retval
    return retval
```
</details>

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

```diff_python
-def fib_by_tr(n, depth=0, memo={}):
+def fib_by_tr(n, depth=0, memo=None):
+    if memo is None:
+        memo = {}
元と同じなので省略
```
</details>

:::


### メモ化を行った場合の計算速度

メモ化を行うことで `fib_by_tr` の計算速度は劇的に向上しますが、それでも __メモ化の処理を行わなければならない分だけ__、ボトムアップな繰り返し処理を行う `fib_by_f` や `fib_by_bf` よりも __計算に時間がかかります__。

そのことを確認するために、実際に計算速度を `%%timeit` で比較することにします。

まず、`print` があると `%%timeit` でうまく計測を行えないので、下記のプログラムのように `fib_by_tr` から `print` を削除してメッセージの表示を行わないように修正します。

```python
def fib_by_tr(n, memo={}):
    if n == 0:
        return 0
    elif n == 1:
        return 1   
    if n in memo:
        return memo[n]
        
    memo[n] = fib_by_tr(n - 1, memo=memo) + fib_by_tr(n - 2, memo=memo)
    return memo[n]
```

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

```diff_python
def fib_by_tr(n, depth=0, memo={}):
-   indent = "  " * depth
    if n == 0:
-       print(f"{indent}fib(0) = 0")
        return 0
    elif n == 1:
-       print(f"{indent}fib(1) = 1")
        return 1   
    if n in memo:
-       print(f"{indent}fib({n}) = {memo[n]} (memo)")
        return memo[n]
-   print(f"{indent}fib({n}) = fib({n - 1}) + fib({n - 2})")
-   r1 = fib_by_tr(n - 1, depth + 1, memo=memo)
-   print(f"{indent}fib({n}) = {r1} + fib({n - 2})")
-   r2 = fib_by_tr(n - 2, depth + 1, memo=memo)
-   retval = r1 + r2
-   print(f"{indent}fib({n}) = {r1} + {r2} = {retval}")
-   return retval
+   memo[n] = fib_by_tr(n - 1, memo=memo) + fib_by_tr(n - 2, memo=memo)
+   return memo[n]
```
</details>

:::note
`fib_by_tr` は今後はもう利用しないので上記のように修正しましたが、途中経過を表示する `fib_by_tr` を今後も利用したい場合は、[以前の記事](https://qiita.com/ysgeso/items/24a604d82249f61e199d#test_judge-%E3%81%AE%E6%94%B9%E8%89%AF-%E3%81%9D%E3%81%AE-1%E3%82%B2%E3%83%BC%E3%83%A0%E7%9B%A4%E3%81%AE%E8%A1%A8%E7%A4%BA%E3%81%AE%E6%9C%89%E7%84%A1%E3%81%AE%E9%81%B8%E6%8A%9E)で紹介した方法で、途中経過を表示するかどうかを表す仮引数 `debug` を追加すると良いでしょう。
:::

下記は、`fib_by_f`、`fib_by_br`、`fib_by_tr` のそれぞれで $F_{40}$ の計算時間を `%%timeit` で計測するプログラムです。なお、`fib_by_tr` では、メモ化を最初から行った場合の処理時間を計測したいので、`memo={}` を記述して、`memo` の値を空の dict で初期化しています。

```python
%%timeit
fib_by_f(40)
```

実行結果

```python
1.57 µs ± 28.9 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
```

```python
%%timeit
fib_by_br(40)
```

実行結果

```python
4 µs ± 22.4 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
```

```python
%%timeit
fib_by_tr(40, memo={})
```

実行結果

```python
11.6 µs ± 87.5 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
```

下記は実行結果をまとめたものです。実行結果から、実際に `fib_by_tr` が最も計算時間がかかることがわかります。なお、`fib_by_br` のほうが `fib_by_f` よりも時間がかかっているのは、関数呼び出しの処理に時間がかかるからです。

|  | 計算時間の平均 |
|:--|--:|
| `fib_by_f`  | 1.57 μs  |
| `fib_by_br`  | 4.00 μs  |
| `fib_by_tr`  | 11.60 μs  |

### メモ化の欠点

既に気づいている人がいるかもしれませんが、メモ化は、[以前の記事](https://qiita.com/ysgeso/items/3a693c2f189845c01f4f#dict-%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%9F%E8%A8%98%E8%BF%B0)で 0 から 5 までの整数の合計を表す $x_5$ 計算する下記のプログラムで、$x_0$ から $x_5$ を __dict に記録__ していたのと __同様の処理を行っています__。そのため、__大きな__ $n$ の $F_n$ を計算すると __メモリが大量に消費される__ という欠点が生じます。特に、同様の計算を何度も行うことが明らかでない場合は、メモ化によるメモリの消費が大きなデメリットになる場合があるので、__常にメモ化を行えば良いというわけではありません__。

```python
x = {}
x[0] = 0
for n in range(1, 6):
    x[n] = x[n - 1] + n
```

:::note
上記のように、メモ化の処理はボトムアップによる $F_n$ の計算でも利用できます。
:::

:::note
[以前の記事](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)で説明したように、再帰呼び出しによる繰り返し処理は、繰り返しの回数に制限があるため、`fib_by_tf` で $F_{10000}$ のような計算を行おうとすると RecursionError が発生します。そのため、`fib_by_tf` の場合はメモ化で記録できる $F_n$ の数が少ないので、メモリが大量に消費されることはありません。

ただし、メモ化を行う際に大量のメモリが消費されることは実際に良くあります。そのため、メモ化を行う際には、どれくらいの量のデータがメモ化されるかについて考慮する必要がある点に注意して下さい。
:::

メモ化の他の欠点としては、__メモ化の処理を記述__ する分だけ、__プログラムが複雑になる__ 点です。人によっては、メモ化の処理を含めた場合は、ボトムアップな再帰呼び出しの処理のほうが簡潔に記述できると感じる人がいるかもしれません。


## 漸化式を計算するアルゴリズムの選択

ここまでで扱った __複数の項で表される漸化式__ の計算は以下のような性質を持ちます。

* __ボトムアップな__ 繰り返し処理の場合は、__直線的__ な繰り返し処理で行える
* __トップダウンな__ 繰り返し処理の場合は、__分岐__ する繰り返し処理で行える

このように、__アルゴリズム__ によって直線的な繰り返し処理と、分岐する繰り返し処理を __選択できる場合__ は、基本的に __直線的な繰り返し処理を選んだほうが処理が高速__ になります。

従って、__漸化式__ を計算するアルゴリズムは、以下の性質を考えて選択すると良いでしょう。

:::note warn
* for 文や while 文で記述すると、記述が少し面倒だが、最も計算時間が短くなる。また、$n$ の大きさに制限はない
* ボトムアップな再帰呼び出しで記述すると、for 文や while 文よりも少し簡潔に記述を行えるが、再帰呼び出しの性質から処理が若干遅くなり、大きな $ n$ に対する $x_n$ の計算もできない
* トップダウンな再帰呼び出しで記述すると、プログラムの記述は最も簡単だが、処理が分岐する場合はメモ化などの工夫を行わないと処理時間が非常に長くなる。また再帰呼び出しの性質から、大きな $n$ に対する $x_n$ の計算もできない
:::

上記のように、トップダウンな再帰呼び出しには欠点が多いですが、プログラムを簡潔に記述できるという点は確かに魅力的ではあるので、小さい $n$ でしか計算しないことがあらかじめわかっている場合などでは利用しても良いのではないかと思います。

# 分岐が必須となる繰り返し処理

ここまでで説明した漸化式の性質から、直線的な繰り返し処理になるかどうかは、ボトムアップであるかトップダウンであるかによって決まると誤解した人がいるかもしれませんが、__そのような決まりはありません__。例えば、〇×ゲームのゲーム木を作成する処理は、ルートノードからボトムアップな繰り返し処理で行う必要がありますが、その際に繰り返しの処理が分岐します。

漸化式の場合はそうではありませんが、世の中には __分岐が必須となる繰り返し処理__ が __多数あります__。その代表例としては、〇×ゲームのゲーム木のような、__木構造で表現されるデータに対する処理__ が挙げられます。そのようなデータに対する処理は、ボトムアップ、トップダウンのいずれの方法でも分岐する繰り返し処理を記述する必要があります。

そこで、次回の記事では分岐が必須となる繰り返し処理について説明することにします。

# `fib_by_f` の記述の簡略化


最後に、__`fib_by_f`__ を __もう少し簡潔に記述できる__ ことに気が付きましたので紹介します。

下記は、元の `fib_by_f` の定義です。

このプログラムでは、for 文のブロックで以下のような手順で処理を行います。

1. $F_i$ を `fib_p1 + fib_p2` で計算し、`fib` に代入する
2. $F_{i-1}$ を表す `fib_p1` は、次の繰り返し処理で計算する $F_{i+1}$ の 2 つ前の項なので、`fib_p2` に代入する
3. $F_{i}$ を表す `fib` は、次の繰り返し処理で計算する $F_{i+1}$ の 1 つ前の項なので、`fib_p1` に代入する

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

## `fib_by_f` の修正

上記のプログラムは、下記のように修正できます。修正された箇所は 10、11 行目です。

```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_p1, fib_p2 = fib_p1 + fib_p2, fib_p1
11      return fib_p1
```

<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_p2, fib_p1 = fib_p1, fib_p1 + fib_p2
    return fib_p1
```
</details>

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

```diff_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
+       fib_p2, fib_p1 = fib_p1, fib_p1 + fib_p2
-   return fib
+   return fib_p1
```
</details>

下記は、修正後のプログラムの 10 行目のプログラムです。このプログラムは、元のプログラムから __`fib` に $F_n$ を代入する処理を省略__ したのと同じ処理が行われます。

```python
fib_p2, fib_p1 = fib_p1, fib_p1 + fib_p2
```

### よくある勘違い

上記のプログラムは、下記のプログラムと同じ処理が行われるように見えるかもしれませんが、そうではありません。下記のプログラムでは、1 行目で __`fib_p2` に `fib_p1` が代入される__ ので、__2 行目__ の式では __`fib_p1 = fib_p1 + fib_p1`__ が計算されることになります。

```python
fib_p2 = fib_p1
fib_p1 = fib_p1 + fib_p2
```

一方、下記の修正前のプログラムの 2 行目では、上記の 1 行目と同じ処理が行われますが、__3 行目__ では、2 行目で __`fib_p1` が代入される前の `fib_p2`__ の値を使って `fib_p1 + fib_p2` を計算した値が代入される点が異なります。1 行目で __`fib`__ という変数に __`fib_p1 + fib_p2` の式の結果を代入した理由__ は、__2 行目の計算で `fib_p1` の値が必要になる__ からです。

```python
fib = fib_p1 + fib_p2
fib_p2 = fib_p1
fib_p1 = fib
```

### 修正後の 10 行目で行われる処理

修正後のプログラムの 10 行目の処理の __右辺は tuple__ を表しており、下記のプログラムの __tuple の () が省略された__ ものです。従って、右辺の計算を行うと、0 番の要素に `fib_p1` が、`1` 番の要素に `fib_p1 + fib_p2` が代入された __tuple が作成__ されます。 

その後、[以前の記事](https://qiita.com/ysgeso/items/51c2eba867aa560808c6#%E5%8F%8D%E5%BE%A9%E5%8F%AF%E8%83%BD%E3%82%AA%E3%83%96%E3%82%B8%E3%82%A7%E3%82%AF%E3%83%88%E3%81%AE%E5%B1%95%E9%96%8B)で説明した __反復可能オブジェクトの展開__ が行われ、`fib_p2` と `fib_p1` に上記で作成された tuple の 0 番の要素と 1 番の要素の値が代入されます。 
```python
fib_p2, fib_p1 = (fib_p1, fib_p1 + fib_p2)
```

従って上記のプログラムは、`fib_p2` と `fib_p1` に、修正前のプログラムと同様に、この代入文の計算が行われる前の `fib_p1` と `fib_p2` の値で計算された式の計算結果が代入されます。その際に __tuple に必要なデータが記録__ されているため、元のプログラムの __`fib` は必要ありません__。

元の式では、`fib` に $F_n$ の計算結果を代入していましたが、上記のプログラムでは __`fib_p1` にその値が代入される__ ようになりました。そのため、最後の 11 行目の return 文は、下記のプログラムのように `fib` の代わりに __`fib_p1` を返す__ ように修正する必要があります。

```python 
return fib_p1
```

## さらなる修正

最後の文が `return fib_p1` なのはわかりづらいので、`fib_p2` と `fib_p1` の名前をそれぞれ `fib_p1` と `fib` に変更することにします。変更した名前は以下のような意味を表します。

* 修正前は `fib_p1 + fib_p2` を計算する前の値の意味を表す
    * __`fib_p2`__：$F_i$ を計算する際に必要な 2 つ前の $F_{i-2}$ の値
    * __`fib_p1`__：$F_i$ を計算する際に必要な 1 つ前の $F_{i-1}$ の値
* 修正後は `fib_p1 + fib_p2` を計算した後の値の意味を表す
    * __`fib_p1`__：次の $F_{i+1}$ を計算する際に必要な 2 つ前の $F_{i-1}$ の値
    * __`fib`__：次の $F_{i+1}$ を計算する際に必要な 1 つ前の $F_{i}$ の値

下記は、そのように `fib_by_f` を修正したプログラムです。最後の行が `return fib` になる点が少しわかりやすくなっています。

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

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

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

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

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

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

```python
for i in range(10):
    print(f"fib({i}) = {fib_by_f(i)}, {fib_by_tr(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
```

上記の `fib_by_f` であれば、__ボトムアップな再帰呼び出し__ の `fib_by_br` とプログラムの __複雑さはほぼ同じになる__ ので、ボトムアップな再帰呼び出しで記述するメリットはほとんどないかもしれません。

## 変数の値の交換

上記のような __tuple と反復可能オブジェクトの展開の利用__ は、__2 つの変数の値を交換（swap）__ するプログラムを記述する際にも良く使われます。

例えば、`a` と `b` の変数の値を交換する際に、下記のようなプログラムを記述すると、__4 行目__ の処理で __`a` に代入されていた値がなくなってしまう__ ためうまくいきません。下記のプログラムを実行すると、`a` と `b` の値が実行結果のように __どちらも 2 になってしまいます__。
 

```python
1  a = 1
2  b = 2
3
4  a = b
5  b = a
6  print(a)
7  print(b)
```

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

```python
a = 1
b = 2

a = b
b = a
print(a)
print(b)
```
</details>

実行結果

```
2
2
```

下記のプログラムの 4、6 行目のように、__片方の変数を別の変数に代入して取っておき__、後でもう __片方の変数に代入する__ ことでうまく交換できるようになります。なお、__一時的（temporary）__ にデータを取っておく変数の名前には __`tmp`__ や __`temp`__ が良く使われます。

```python
1  a = 1
2  b = 2
3
4  tmp = a
5  a = b
6  b = tmp
7  print(a)
8  print(b)
```

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

```python
a = 1
b = 2

tmp = a
a = b
b = tmp
print(a)
print(b)
```
</details>

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

```diff_python
a = 1
b = 2

+tmp = a
a = b
-b = a
+b = tmp
print(a)
print(b)
```
</details>

実行結果

```
2
1
```

Python では、先程説明した __tuple と 反復可能オブジェクトの展開__ を利用すること、下記のプログラムの 4 行目のように __変数の値の交換__ を __1 行で簡潔に記述__ することができるので __良く使われます__。__tuple でデータを記録する__ ことで、__`tmp` を用意する必要が無くなります__。

```python
1  a = 1
2  b = 2
3
4  a, b = b, a
5  print(a)
6  print(b)
```

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

```python
a = 1
b = 2

a, b = b, a
print(a)
print(b)
```
</details>

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

```diff_python
a = 1
b = 2

-tmp = a
-a = b
-b = tmp
+a, b = b, a
print(a)
print(b)
```
</details>

実行結果

```
2
1
```

# 今回の記事のまとめ

今回の記事では、複数の項で表される漸化式をトップダウンな再帰呼び出しによる計算すると繰り返し処理が分岐することを説明しました。また、その際に行われる処理の性質について説明し、処理を効率化するためのメモ化という手法について説明しました。

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

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

# 次回の記事

https://qiita.com/ysgeso/items/38f2c8167a14eb99d86c

[^1]:$0 < x < 1$ の場合は急激に 0 に近づいていきます  
[^2]:[Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%A2%E5%8C%96) によると memorization は、大事なことをメモするという memo の正式名称である memorandom から作られた造語とのことです
[^3]:数値型や文字列型などのイミュータブルなデータを仮引数に代入して共有することはできますが、その場合は仮引数の値を変更した場合に、共有した他の関数の仮引数の値が変化しません