Python の nonlocal を使うことでグローバル変数を使わずに再帰処理を行う

`nonlocal` 文が役に立つ場面に遭遇したのでご紹介します。

※この記事の Google Colab 版は[こちら](https://colab.research.google.com/drive/1_C3GNVeGLoMXdohdd8sVFTP_F4dzLLMj?usp=sharing)。

まずは、これから説明する内容をイメージしやすくするために問題を設定してみます。

# 解決したい問題

手元に12個のピーマンがあり、その中からいくつか取り出して、150g入りの袋詰めで販売したいとします[^1]。つまりこれら12個のピーマンのどれを選べば良いのかを求める必要があります。

```python
bell_peppers = [47, 36, 29, 24, 32, 24, 47, 51, 45, 20, 53, 37]
```

前提条件として、ピーマンを販売するにあたって表示されている内容量よりも実際の内容量が少ないということがあってはいけないので、150g以上の、150gに最も近い値を目指します。

これを実現するために、リストを引数として与えたら、そのリスト内の組み合わせで作れる150以上かつ150に最も近い値、およびその値を得るために選ぶべきピーマンの位置を返してくれる関数を作ります。

```python
bell_pepper_search(bell_peppers)
# 返り値：(150, '000010001110')
# リスト内の5、9、10、11番目のピーマンを選ぶと150gとなることがわかる。
```
この問題は部分和問題と呼ばれていて、複数の解法がありますがここでは再帰を使った枝刈り全探索を行います[^2]。

# グローバル変数を使った再帰関数

再帰処理を行う際、再帰処理の中で計算した値などを一時的に保存したい場合があります。しかし関数の中で変数を宣言すると、関数が呼び出されるたびに新たなスコープで変数が宣言されるため、各再帰処理間での変数の共有はできません。値を各再帰処理間で共有する手段としてはグローバル変数を使うのが直感的かと思います。

```python
overall_closest = sum(bell_peppers)  # 最終的に150以上の150に最も近い値が入る変数。
overall_closest_mask_bit_string = "1" * len(bell_peppers)  # 150以上の150に最も近い値を得るためのピーマンの位置を示してくれる文字列が入る変数。
def recursive_search_with_global(
    item_list,
    temp_sum=0,
    item_index=0,
    current_mask_bit_string="",
):
    global overall_closest
    global overall_closest_mask_bit_string
    if overall_closest == 150:  # ぴったり150となる組み合わせがすでに見つかっている場合は何もしない。
        pass
    elif item_index == len(item_list):  # リストの最後まで行った場合。
        if temp_sum >= 150:
            if abs(temp_sum - 150) <= abs(overall_closest - 150):  # 150により近い値を保持する。
                overall_closest = temp_sum
                overall_closest_mask_bit_string = current_mask_bit_string
            elif abs(temp_sum - 150) > abs(overall_closest - 150):
                pass
            else:
                raise Warning("You've missed something!")  # 再帰処理を書くにあたって条件を網羅できているかを確認するのに役立つ。
        elif temp_sum < 150:
            pass
        else:
            raise Warning("You've missed something!")
    elif item_index < len(item_list):  # リストの最後まで行っていない場合。
        if temp_sum >= 150:
            if abs(temp_sum - 150) <= abs(overall_closest - 150):
                overall_closest = temp_sum
                overall_closest_mask_bit_string = current_mask_bit_string
            elif abs(temp_sum - 150) > abs(overall_closest - 150):
                pass
            else:
                raise Warning("You've missed something!")
        elif temp_sum < 150:
            recursive_search_with_global(item_list, temp_sum, item_index + 1, current_mask_bit_string+"0")
            recursive_search_with_global(item_list, temp_sum+item_list[item_index], item_index + 1, current_mask_bit_string+"1")
        else:
            raise Warning("You've missed something!")
    else:
        raise Warning("You've missed something!")
    while len(overall_closest_mask_bit_string) < len(item_list):
        # リスト内の最後の要素にたどり着く前に150を超えた場合、末尾の0が抜けてしまうので0を足していく。
        overall_closest_mask_bit_string += "0"
    return overall_closest, overall_closest_mask_bit_string
```

ピーマンのリストを引数としてこの関数を呼び出してみます。

```python
recursive_search_with_global(bell_peppers)
# (150, '000010001110')
```

ちょうど150gとなるピーマンの組み合わせが求まりました。これで1回目のピーマンの袋詰めは終わりです。

続けて2回目の袋詰めを行います。

```python
bell_peppers_2 = [40, 40, 40, 40, 40]
```

連続して `recursive_search_with_global` 関数を呼び出してしまうと下のようになります。

```python
recursive_search_with_global(bell_peppers_2)
# (150, '000010001110')
```

これはなぜかというと `overall_closest` および `overall_closest_mask_bit_string` には1回目の袋詰めで関数を呼び出した際の値が残っているからです。正しい結果を得るためにはこれらの変数に新しいリストを使った値を再代入してから関数を呼び出す必要があります。

```python
overall_closest = sum(bell_peppers_2)
overall_closest_mask_bit_string = "1" * len(bell_peppers_2)
recursive_search_with_global(bell_peppers_2)
# (160, '11110')
```

また、今回のようにグローバル変数を操作している関数がひと目で分かるうちは大丈夫ですが、プログラム内の関数が増えてくると、どの関数が各グローバル変数をどの段階で操作しているのかがわかりにくくなります。このような理由から大きなプログラムでグローバル変数を使うことは bad practice とされていますので使用は極力避けたいものです。

# `nonlocal` 文を使った再帰関数
Python の `nonlocal` 文の詳細については[公式ドキュメント](https://docs.python.org/ja/3/reference/simple_stmts.html#the-nonlocal-statement)および[PEP3104](https://www.python.org/dev/peps/pep-3104/)に書かれています。

`nonlocal` 文は、指定された変数を `nonlocal` があるスコープから外側に向かって、グローバルスコープにたどり着くまで探します（グローバルスコープそのものは含みません）。

```python
def nonlocal_example():
    foo1 = "123"
    foo3 = "789"
    foo4 = "def"
    def my_inner_func():
        foo2 = "456"
        foo3 = "abc"
        nonlocal foo4  # 再帰関数の場合はこのfoo4のような動きになる。
        def my_inner_func_2():
            nonlocal foo1
            nonlocal foo2
            nonlocal foo3
            nonlocal foo4
            foo1 = foo1 + "000"
            foo2 = foo2 + "000"
            foo3 = foo3 + "000"
            foo4 = foo4 + "000"
            print(foo1)
            print(foo2)
            print(foo3)
            print(foo4)
        my_inner_func_2()
    my_inner_func()

nonlocal_example()
# 123000
# 456000
# abc000
# def000
```

この `nonlocal` 文を使ったピーマンの袋詰めのための再帰関数は以下のようになります。

```python
def recursive_search_nonlocal_outer(item_list):
    overall_closest = sum(item_list)
    overall_closest_mask_bit_string = "1" * len(item_list)
    def recursive_search_nonlocal_inner(
        item_list,
        temp_sum=0,
        item_index=0,
        current_mask_bit_string="",
    ):
        nonlocal overall_closest
        nonlocal overall_closest_mask_bit_string
        if overall_closest == 150:
            pass
        elif item_index == len(item_list):
            # ...中略...
        elif item_index < len(item_list):
            # ...中略...
            elif temp_sum < 150:
                recursive_search_nonlocal_inner(item_list, temp_sum, item_index + 1, current_mask_bit_string+"0")
                recursive_search_nonlocal_inner(item_list, temp_sum+item_list[item_index], item_index + 1, current_mask_bit_string+"1")
            else:
                raise Warning("You've missed something!")
        else:
            raise Warning("You've missed something!")
        while len(overall_closest_mask_bit_string) < len(item_list):
            overall_closest_mask_bit_string += "0"
        return overall_closest, overall_closest_mask_bit_string
    return recursive_search_nonlocal_inner(item_list)
```

最初の例ではグローバル変数として宣言した `overall_closest` と `overall_closest_mask_bit_string` を、ここでは `recursive_search_nonlocal_outer` という関数の中で宣言し、`nonlocal` を使って `recursive_search_nonlocal_inner` の中からそれらを参照しています。そして最後に `recursive_search_nonlocal_outer`の返り値が `recursive_search_nonlocal_inner` の返り値となるよう `recursive_search_nonlocal_inner` を最後の `return` の中で呼び出しています。

この関数を使ってみましょう。

```python
recursive_search_nonlocal_outer(bell_peppers)
# (150, '000010001110')

recursive_search_nonlocal_outer(bell_peppers_2)
# (160, '11110')
```

どちらも正しい結果が得られましたね。この書き方によって関数を[純粋関数](https://zenn.dev/riku/books/36d9873ee1c0e6/viewer/026276)として書くことができているので、関数としても使いやすくなりました。

このように `nonlocal` を使うことでグローバル変数を使うことなく再帰処理を行うことができます。

# 補足

せっかくなので150g以外の重さでも袋詰めを行えるように、目標の重量を指定できるように関数を変えてみます。

```python
def recursive_search_with_nonlocal_2(item_list, target_weight):
    overall_closest = sum(item_list)
    overall_closest_mask_bit_string = "1" * len(item_list)
    def recursive_search_nonlocal_inner(
        item_list,
        temp_sum=0,
        item_index=0,
        current_mask_bit_string="",
    ):
        nonlocal overall_closest
        nonlocal overall_closest_mask_bit_string
        if overall_closest == target_weight:
            pass
        elif item_index == len(item_list):
            if temp_sum >= target_weight:
                if abs(temp_sum - target_weight) <= abs(overall_closest - target_weight):
                    overall_closest = temp_sum
                    overall_closest_mask_bit_string = current_mask_bit_string
                elif abs(temp_sum - target_weight) > abs(overall_closest - target_weight):
                    pass
                else:
                    raise Warning("You've missed something!")
            elif temp_sum < target_weight:
                pass
            else:
                raise Warning("You've missed something!")
        elif item_index < len(item_list):
            if temp_sum >= target_weight:
                if abs(temp_sum - target_weight) <= abs(overall_closest - target_weight):
                    overall_closest = temp_sum
                    overall_closest_mask_bit_string = current_mask_bit_string
                elif abs(temp_sum - target_weight) > abs(overall_closest - target_weight):
                    pass
                else:
                    raise Warning("You've missed something!")
            elif temp_sum < target_weight:
                recursive_search_nonlocal_inner(item_list, temp_sum, item_index + 1, current_mask_bit_string+"0")
                recursive_search_nonlocal_inner(item_list, temp_sum+item_list[item_index], item_index + 1, current_mask_bit_string+"1")
            else:
                raise Warning("You've missed something!")
        else:
            raise Warning("You've missed something!")
        while len(overall_closest_mask_bit_string) < len(item_list):
            overall_closest_mask_bit_string += "0"
        return overall_closest, overall_closest_mask_bit_string
    return recursive_search_nonlocal_inner(item_list)
```

180gの袋詰めを行ってみます。

```python
recursive_search_with_nonlocal_2(bell_peppers, 180)
# (180, '000000111001')
```

[^1]: このピーマンの袋詰めの例は2017年に放送された「[大人のピタゴラスイッチ ピーマンとハトと数学](https://www.nhk.or.jp/archives/teachers-l/list/id2021022/)」に出てきたものです。なぜかとても印象に残っていたのでここでも例として使わせていただきました。

[^2]: 枝刈り全探索のコードは増井敏克さんによる「[Pythonではじめるアルゴリズム入門](https://www.shoeisha.co.jp/book/detail/9784798163239)」の p.162 の問題2の解答（p.267）を参考にさせていただいています。