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

目次と前回の記事

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

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

リンク	説明
marubatsu.py	Marubatsu、Marubatsu_GUI クラスの定義
ai.py	AI に関する関数
util.py	ユーティリティ関数の定義。現在は gui_play のみ定義されている
tree.py	ゲーム木に関する Node、Mbtree クラスの定義
gui.py	GUI に関する処理を行う基底クラスとなる GUI クラスの定義

ルールベースの AI の一覧

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

再帰呼び出し

前回の記事では、再帰呼び出しを使用せずに深さ優先アルゴリズムでゲーム木を作成する方法を紹介しましたが、深さ優先アルゴリズム は 再帰呼び出しを使用するのが一般的 です。

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

再帰呼び出しとは何か

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

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

def f():
    f()

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

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 は無限ループを行う繰り返し処理です。

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

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

これまでの記事では、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) と記述しました。

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

print(total)

実行結果

45

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

• 合計を計算するための変数 total を 0 で初期化 する
• 0 から整数を順番に数えるため に range(0, 10, 1) を 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 文と同様です。

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

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

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

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

行番号のないプログラム

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

print(total)

実行結果

45

for 文と while 文の使い分け

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

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

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

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

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

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

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

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

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

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

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

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

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

print(total)

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

実行結果

45

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

計算結果の記録の方法

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

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

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

print(total)

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

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

while True:
    pass

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

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

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

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

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

def f():
    f()

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

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

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

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

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

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

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

g()

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

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

f()

実行結果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

行番号のないプログラム

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 文 の繰り返し処理との 共通点 と 違い は以下の通りです。なお、最後の 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 文の前に記述 します。

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

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

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

行番号のないプログラム

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

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

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 までの整数の合計を計算することができる
• 合計を計算できたアルバイトは、その答えを前のアルバイトに伝える
• 答えを受け取ったアルバイトは、その答えを前のアルバイトに伝える
• 上記の作業を続けることで、店長がアルバイトから答えを受け取ることができる

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

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

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

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

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

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

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

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

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

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

• 2 行目：sum9 の仮引数 i には、最初は 0 が代入され、sum9 を呼び出すたびに i が 1 ずつ加算されるので、sum9 が呼び出された回数は i + 1 で計算できる。その値を count というローカル変数に代入する
• 3 行目：sum9 が呼び出された際に、何回目の呼び出しであるかと、仮引数 i と total の値を print で表示する。それぞれの値は最大 2 桁の数値になるので、数値の表示位置が縦に揃うように、書式指定の :2 を使って 2 文字で表示するようにした
• 7 ~ 9 行目：元のプログラムでは return sum9(i, total) のように、呼び出した sum9 の返り値を直接返していたが、それでは返り値を表示できないので、一旦 retval² に sum9 の返り値を代入し、print で表示してからその値を返すようにした
• 11 行目：i < 10 でない場合も返り値を表示するようにした

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

行番号のないプログラム

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

修正箇所

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

実行結果

 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 の値が 上書き されてしまうと 錯覚してしまう 人が多いのではないかと思いますが、実際には違います。

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

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

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

同じ名前の仮引数であっても、異なる関数であれば別の変数である理由は、以前の記事で説明したように、関数呼び出しが行われた際 に、その関数の ローカル名前空間が作成 され、その名前空間に、関数の仮引数などの ローカル変数の名前が登録される からです。

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

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

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

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

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

		1 回目		2 回目
		i	total	i	total
1 回目	1 行目 (呼び出しの直後)	0	0	ー	ー
	3 行目 (total += i)	0	0	ー	ー
	4 行目 (i += 1)	1	0	ー	ー
2 回目	1 行目	1	0	1	0
	3 行目	1	0	1	1
	4 行目	1	0	2	1

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

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

while True:
    pass

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

def f():
    f()

f()

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

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

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

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

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

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

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

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

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

• i：次に l に追加する要素の値
• l⁵：0 から i 未満の整数の要素を持つ list。ただし、i が 0 の場合は 空の list とする
• maxi⁵：この関数では、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 を呼び出す

 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)

行番号のないプログラム

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)

実行結果

 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 が代入されます。

下記のプログラムのように、上記のプログラムを 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 を呼び出すように修正する

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

行番号のないプログラム

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

修正箇所

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

実行結果

 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 つのプログラムを比較してみて下さい。再帰呼び出しの方がわかりやすいと思う人はほとんどいないのではないかと思います。

# 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' を使って for 文で 0 から 9 までの整数の合計の計算にかかる時間を計測するプログラムです。以前の記事で説明したように、%%timeit で処理時間を計測する際には、print の処理を行うべきではないので、print による結果の表示は省略しています。

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

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

%%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	本記事で入力して実行した JupyterLab のファイル

次回の記事

1. 合計を表す英単語には sum がありますが、sum という組み込み関数が存在するので、total という名前にしました ↩

2. retval は、返り値を表す return value の略です ↩

3. ローカル関数のように、関数が別の関数のブロックの中に、入れ子で定義されている場合を除きます。例えば、Mbtree_GUI クラスの on_left_button_clicked 関数は、create_event_handler の中に定義されたローカル関数なので、create_event_handler のローカル変数である self を直接記述して利用できます ↩

4. 先程の sum9 に仮引数 maxi を加えて同様の処理を行うことで、0 から任意の整数未満の合計を計算するプログラムを記述することができます ↩

5. list や max という組み込み関数が存在するので、仮引数の名前を l や maxi としました ↩ ↩²