再帰 の

再帰について

再帰とは、関数が自分自身を呼び出すことで、その関数の中のコードを繰り返し実行する方法です。自分自身を呼び出す関数は_再帰関数_と呼ばれます。再帰は、ループ、つまり繰り返しのもう一つの方法と考えることができます。そしてループと同じように、再帰的な実行をいつ止めるかを決めるために、真偽値の式やTrue/Falseの判定を使います。

ループとは_異なり_、Pythonでは終了しない再帰を無限に実行し続けることはできません。それぞれの関数呼び出しで使われる値は、Pythonのインタプリターのスタック上にある、その呼び出し専用のフレームに置かれます。関数呼び出しの合計数がスタックの容量を超えると、エラーになります。

ループによる実装と再帰による実装

ループと再帰は、どちらも繰り返しであるという点で_似ている_と感じるかもしれません。しかし、コードのレベルでも実装のレベルでも、_見た目_は異なります。ループは、コールスタック上の同じフレーム内で行うことができます。これは通常、1つまたは複数の変数の値を更新しながら、繰り返しごとに状態を少しずつ保つことで実現します。効率的な実装ですが、コードを見るとやや雑然として見えることがあります。

再帰は、_変数の状態_を更新するのではなく、_更新された値_をそのまま引数として、同じ関数の次の呼び出し（次の繰り返し）に渡すことができます。これにより関数の本体がすっきりし、それぞれの更新がどのように行われるかが分かりやすくなります。ただし、同じ関数を呼び出すたびにスタックに新しいフレームが追加されるため、効率はむしろ悪くなります。

再帰：使う理由と使わない理由

スタックのエラーやオーバーフローを引き起こすおそれがあるのに、なぜ再帰的な方法で問題を解くのでしょうか？　読みやすさ、追いやすさ、そして意図です。 ループで表すよりも再帰で表したほうが、解答が読みやすかったり、考えをたどりやすかったりする状況があります。また、データの使用や変更、複雑さの管理、責任の委譲、作業量の整理といった点で、プログラム上の制約がある場合もあります。

再帰に適した問題には、時間とともに小さくなっていく、複雑でありながら反復的な問題があります。特に分割統治アルゴリズムや累積アルゴリズムがそうです。ただし、Pythonではスタックに置けるフレームの数に上限があるため、すべての問題が完全に再帰的な方法でうまくいくわけではありません。再帰にあまり向かない問題には、安定した状態を保ちつつ一定の回数だけ繰り返す必要があるもの、非同期に実行する必要があるもの、非常に多くの繰り返しが求められる状況などがあります。

ループと再帰の戦略：インディラの不安

インディラは、毎月の社会保障の給付金が、毎月の**第2水曜日**に銀行口座へ自動で振り込まれています。インディラは小切手帳の残高を合わせることを心配しています。お金が振り込まれる前に小切手を切ってしまうのではないかと恐れているのです。彼女は孫娘のアディヤに、お金が口座に入る日付のリストを作ってほしいと頼みます。

アディヤはちょうどPythonのプログラミングを学び始めたところで、最初に思いついたとおりにプログラムを書きます。印刷できるように、入金日のlistを返したいと考えます。_どんな年_でも動く関数を書きたいとも考えます。予定が変わったとき（あるいは、他の親戚がアディヤに自分の入金日を計算してほしいと頼んだとき）に備えて、関数に_曜日_の仮引数を追加する必要があると決めます。最後に、その月の_何番目_の曜日なのか（第1、第2など）を表す仮引数も必要だと決めます。これらの要件をすべて満たすために、datetimeからインポートしたdateクラスを使うことにします。これらをすべてまとめると、アディヤは次のように書きました：

from datetime import date


def paydates_for_year(year, weekday, ordinal):
    """Returns a list of the matching weekday dates.
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    output = []

    for month in range(1, 13):
        for day_num in range(1, 8):
            if date(year, month, day_num).isoweekday() == weekday:
                output.append(date(year, month, day_num + (ordinal - 1) * 7))
                break
    return output

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year(2022, 3, 2))

この最初の繰り返しはうまく動きますが、アディヤはもっと少ない行数と入れ子の少ないループでコードを書き直せないかと考えます。また、状態の変更は最小限にするのがよいと読んだことがあるので、output、month、day_numなどの変数を変更せずに済ませられないか試したいと思っています。

彼女は再帰についても知っているので、プログラムを再帰的な方法に変えるにはどうすればよいか考えます。ループの関数で作られ、変更されている変数は、代わりに引数として渡すことができます。関数の_中で_変数を変更するのではなく、_更新された値を引数として_次の関数呼び出しに渡せるのです。そう考えて、彼女は次の再帰的な方法に行き着きました：

from datetime import date


def paydates_for_year_rec(year, weekday, ordinal, month, day_num, output):
    """Returns a list of the matching weekday dates
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
        month (int): The month number currently being processed.
        day_num (int): The day number of the month currently being processed.
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    if month == 13:
        return output
        
    if date(year, month, day_num).isoweekday() == weekday:
        return paydates_for_year_rec(
                 year, weekday, ordinal, month + 1, 1, output
                 + [date(year, month, day_num + (ordinal - 1) * 7)]
                 )
    
    return paydates_for_year_rec(year, weekday, ordinal, month, day_num + 1, output)

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year_rec(2022, 3, 2, 1, 1, []))

入れ子のループがなくなり、変更される状態もなく、コードも2行短くなったことをアディヤは喜んでいます。

彼女は、再帰的な方法はループの方法よりも手順が多く、そのため「性能」が低いことを少し気にしています。しかし、問題を再帰で書き直したことで、見にくい入れ子のループ（性能上の危険）、大量の状態変更、複雑な条件分岐をめぐる混乱に対処するのに確かに役立ちました。また、より「読みやすい」と感じられます。このコードをしばらくぶりに見直したときにも、すんなり読み通して、何をするものだったかを思い出しやすくなるはずだと確信しています。

これからは、アディヤはまず問題を再帰的に解いてみるかもしれません。入れ子や変更、複雑さが最小限に抑えられていれば、最初は問題を明確な手順でたどるほうが簡単だと感じるかもしれません。基本的な論理を組み立てたあとで、最初の再帰的な手順を、より性能の高いループの方法へと最適化することに集中できます。

さらに後になってtuplesについて学んだら、アディヤは、list comprehensionとCalendar.itermonthdatesを使ったり、特定の値をメモ化したりするなど、さらなる「最適化」の方法を検討できるでしょう。

再帰のバリエーション：末尾呼び出し

末尾呼び出しとは、関数の最後の文が自分自身を呼び出すだけで、それ以外に何もしないものをいいます。次の例は末尾呼び出しではありません。この関数は、自分自身を呼び出した結果に1を足しているからです：

def print_increment(step, max_value):
    if step > max_value:
        return 1
    print(f'The step is {step}')
    return 1 + print_increment(step + 1, max_value)


def main():
    retval = print_increment(1, 2)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

これは次のように出力します：

The step is 1
The step is 2
retval is 3 after recursion

末尾呼び出しに書き直すには、retvalをprint_incrementの仮引数にします。

def print_increment(step, max_value, retval):
    if step > max_value:
        return retval
    print(f'The step is {step}')
    return print_increment(step + 1, max_value, retval + 1)


def main():
    retval = print_increment(1, 2, 1)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

末尾呼び出しは、末尾呼び出しではない再帰呼び出しよりも、さらに考えをたどりやすいと感じるかもしれません。ただし、再帰を使うときは、スタックがあふれるほど多くの繰り返しを行わないように、常に気をつけることが大切です。

Pythonの再帰の上限

一部の言語では末尾呼び出しを最適化でき、スタックにフレームを追加するのではなく、再帰呼び出しのたびに、その関数の最初の呼び出しのスタックフレームを再利用します（ループがフレームを再利用するのと同じように）。Pythonはそのような言語の一つではありません。スタックのオーバーフローを防ぐために、Pythonにはデフォルトで1000フレームという再帰の上限があります。再帰の上限を超えたことをインタプリターが検出すると、RecursionError例外が発生します。sys.setrecursionlimitメソッドを使って再帰の上限を増やすこともできますが、そうすると実行時にセグメンテーションフォールトが起きてプログラムがクラッシュし、場合によってはオペレーティングシステムもクラッシュするおそれがあります。

参考資料

Pythonでの再帰の使い方をもっと学びたいときは、まず次のものから始めるとよいでしょう。

• python-programming: recursion
• Real Python: python-recursion
• Real Python: python-thinking-recursively