【ためになるpython】再帰関数の限界〜maximum recursion depth exceeded〜

こんにちは、ゆきぽんずです。

今日はpythonの再帰関数の実行限界が問題となって起こるエラーであるmaximum recursion depth exceededについて紹介していきます。

言葉にするとわかりにくいので実例をみていきます。

問題の解決策のみ知りたい方は、目次のmaximum recursion depth exceededの解決策だけご覧ください。

環境
うまくいく再帰関数
- 実行結果
- 豆知識 : 等差数列の和の公式
うまくいかない再帰関数
- 実行結果
再帰関数の実行回数を調査
- 実行結果
maximum recursion depth exceededの解決策
- ソースコード
- 実行結果

環境

python 3.7.6

Mac OS 10.15.3

うまくいく再帰関数

0〜100までを足していく再帰関数を実装します。

def sum(n, count):
    if count > 100:
        print(n)
        print("finish")
        return 0
    n += count
    # print(n)
    count += 1
    sum(n, count)

sum(0, 1)

実行結果

実行結果1

うまく実行できました。

ちなみに1〜100までの足し算は、等差数列の和の公式を使えば簡単に計算できます。

豆知識 : 等差数列の和の公式

引用サイト : https://mathwords.net/1karannowa

1〜100までの足し算は、1/2 * 100 * 101 = 5050となり、実行結果とも一致します。

本題に戻します。

うまくいかない再帰関数

0〜1000までを足していく再帰関数を実装します。

def sum(n, count):
    if count > 1000:
        print(n)
        print("finish")
        return 0
    n += count
    # print(n)
    count += 1
    sum(n, count)

sum(0, 1)

足し算する個数を100から1000に変えただけの関数です。

実行結果

見切れるほどのエラーが出るので、一部だけ掲載します。

実行結果2

要は、再帰関数の繰り返しの数が多すぎるんだよというエラーが出ています。

「えっそんなことあるのかよ」と戸惑いながらもgoooooooooogle先生で検索したところpythonの仕様的に再帰関数の実行回数には制限があるとのこと。

windows、ubuntu等のOSごとに制限回数は異なりはしますが、全てのOSで再帰関数の実行回数には制限がかかっているみたいです。

再帰関数の実行回数を調べてくれる関数があったので結果も合わせて載せます。

再帰関数の実行回数を調査

# coding: UTF-8
import sys

#再帰関数の実行回数の上限を表示
print(sys.getrecursionlimit())

sys.exit()

実行結果

実行結果3

あれっ？うまくいかない再帰関数って実行回数1000回じゃなかったっけ？

そのとおりです。

どうも再帰関数の実行回数の上限はOSだけでなくPCにもよるみたいです。要は、Mac OSのPCでもMacbookAir、Macbook、MacbookPro等で実行回数の上限は異なるということです。

このままでは再帰関数を1000回実行することができないので、ちょっとソースコードを書き換えます。

maximum recursion depth exceededの解決策

以下の2つの関数を使えば解決できます。

sys.setrecursionlimit() : インタプリタ側の設定を変更する
threading.stack_size() : 実際にスタックとして使える領域の容量の設定を変更

point

特に注意して欲しいのは、2で行うスタックサイズの調整です。1だけを行ってもpythonの設定が変わっているだけで、PCの設定を変えていないのでそのままエラーになります。

変更後のソースコードを載せます。

ソースコード

# coding: UTF-8
import sys
import threading

#変更前の再帰関数の実行回数の上限を表示
print(sys.getrecursionlimit())

sys.setrecursionlimit(67108864) #64MB
threading.stack_size(1024*1024)  #2の20乗のstackを確保=メモリの確保

#変更後の再帰関数の実行回数の上限を表示
print(sys.getrecursionlimit())

def sum(n, count):
    if count > 1000:
        print(n)
        print("finish")
        return 0
    n += count
    # print(n)
    count += 1
    sum(n, count)

sum(0, 1)