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

目次と前回の記事

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

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

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

ルールベースの AI の一覧

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

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

前回の記事で、繰り返し処理には、次の繰り返しの 処理の数が増えない ものと、次の繰り返しの処理が 分岐して増える ものがあるという説明をしました。本記事では以後は、繰り返しのたびに処理が増えないものを 直線的な繰り返し処理、処理の数が増えるものを 分岐する繰り返し処理 と表記することにします。

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

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

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

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

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

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

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

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

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

• 独立ではない繰り返し処理で、直前の計算結果以外の過去の計算結果を利用する場合
• 繰り返しのたびに 次に行う繰り返しの処理の数が増えて分岐する場合

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

再帰呼び出しのアルゴリズムには、ボトムアップ な順番で計算を行うものと、トップダウン な順番で計算を行うものがあり、上記のような繰り返し処理はトップダウンな再帰呼び出しを使って簡潔に記述できます。そこで、最初にその違いと使い分けについて説明します。

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

以前の記事で 0 から 9 までの合計を再帰呼び出しで計算する sum9 を紹介しました。

下記は sum9 の定義と、sum9 で 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

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

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 の再帰呼び出しが答えを返すことで処理が終了します。

その流れを見えるようにしたのが、以前の記事で記述した、処理の流れを表示 するように修正した下記の sum9 で、実行結果から下記のように、上記の処理の流れが確認できます。

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

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 を追加する

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

行番号のないプログラム

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

sum9との違い

-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

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

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 をデフォルト値として設定したデフォルト引数にすることでしょう。

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

修正箇所

-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

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

print(sum_by_br(9))

実行結果

45

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

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

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

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

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)

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

print(sum_by_br(9))

実行結果

45

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

前回の記事で説明したように、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$ である

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

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

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

処理の手順がわかったので、上記の手順でトップダウンな再帰呼び出しで 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$ を表す式を計算し、その計算結果を返す

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

行番号のないプログラム

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

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

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

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

処理の流れの確認

トップダウンな再帰呼び出し の 処理の流れがわかる ように、下記のプログラムのように 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 はメッセージの表示のみで利用し、返り値の計算では利用していないので、計算結果は変わりません。

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

行番号のないプログラム

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

修正箇所

-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

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

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 文と同様の内容	漸化式をそのまま記述する

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

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$ を求めることができます。なお、ボトムアップな処理の場合は、前回の記事で紹介した $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$ を求めることができますが、その繰り返し処理も直線的です。従って、直前の計算結果のみ で表される 漸化式 の場合は トップダウン な手順によっても 直線的な繰り返し処理 で答えを求めることができます。

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

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

• 漸化式 の計算は、ボトムアップ な手順で 必ず直線的な繰り返し処理 によって計算を行うことができる

• 直前以外 の計算結果を利用する漸化式を トップダウン な手順で計算すると、 繰り返し処理が分岐する

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

再帰呼び出しは、初心者にはわかりづらいので 以前の記事では、while 文で記述した 0 から 9 までの合計を計算する処理を、再帰呼び出しで書き換えるという方法で説明を行いました。そのため、その際に記述した sum9 による再帰呼び出しでは、while 文と同様のボトムアップ手順で繰り返し処理が計算が行われます。

下記の while 文によるプログラムと、ボトムアップな再帰呼び出しによるプログラムを比較してみて下さい。おそらく、再帰呼び出しのほうがわかりづらいと思う人が多いのではないかと思います。また、以前の記事で説明したように、下記の 2 つのプログラムは、while 文で記述したほうが処理時間が短くなるという問題と、以前の記事 で説明したように、再帰呼び出しには繰り返しの回数に制限があるという問題があります。

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

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

print(total)

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

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

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

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

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

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

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

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

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

具体的には、前回の記事で紹介した、直前の 2 回分 の繰り返し処理の結果を使う必要がある、フィボナッチ数 $F_n$ の計算を再帰呼び出しで記述します。

フィボナッチ数 $F_n$ は下記の漸化式で計算でき、前回の記事では for 文 でボトムアップな手順で繰り返し処理を行う方法について説明しました。

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

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

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

 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

行番号のないプログラム

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

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

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

ボトムアップな再帰呼び出しを行う関数の定義

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

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 の定義です。プログラムの説明はこの後で行います。

 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

行番号のないプログラム

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

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

 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 で計算し、計算結果が並べて表示されます。実行結果からどちらも同じ計算を行うことが確認できます。

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 の再帰呼び出しの 実引数 に直接 次の計算に必要なデータを表す式を記述 することができます。なお、下記のプログラムがわかりづらいと思った方は、無理に下記のように修正する必要はありません。

 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

行番号のないプログラム

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

修正箇所

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

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

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}$ のような、漸化式でもっと数多くの直前以外の計算結果を計算するような場合は、記録しておいたデータの更新の処理の記述が大変になるので、ボトムアップな再帰呼び出しを検討しても良いかもしれません。

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

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

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

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 を計算して返すようにする

 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

行番号のないプログラム

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

修正箇所

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

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

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

今回の記事のまとめ

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

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

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

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

リンク	説明
marubatsu.ipynb	本記事で入力して実行した JupyterLab のファイル

次回の記事

1. 最初に呼び出された f は、f から呼び出されていないので、再帰呼び出しではありません。そのため、再帰呼び出しの回数を表す深さは 0 になります ↩

2. Python では名前の先頭に _ をつけると特別な意味を持つようになるので、単に名前を区別するためだけに _ を使う場合は、末尾に付けたほうが良いでしょう。_ を先頭に付けた場合の特別な意味については、必要があれば今後の記事で説明します ↩

3. このプログラムは、比較するために同じ行に異なる関数の処理を横に並べて記述したものなので、実際に実行することはできません ↩