［Pythonクイズ］再帰で階乗計算、ちゃんとできてる？　再帰関数で再起不能？：Pythonステップアップクイズ

再帰関数は自分自身を関数の内部で呼び出す関数です。Pythonでももちろん使えます。でも、そこにはちょっとした制限もありますよ。知ってましたか？

» 2025年03月11日 05時00分公開

1000の階乗は表示される？　されない？　どっち？

【問題】

　以下に示すfact関数はパラメーターnに渡された整数値の階乗を返す。最後の行では、1000を指定してこの関数を呼び出している。この関数は1000の階乗を返す（そして、print関数がそれを表示する）だろうか？　返さないだろうか？　返さないとしたらその理由は何だろう（Pythonの実行環境の設定は特に変更していないものとする）。

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n-1)

print(fact(1000))

1000の階乗は表示される？　されない？　どっち？

　どうもHPかわさきです。

　あ、何となく問題文はif-else文にしていますけど、以下のような書き方の方がシンプルですね。

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

print(fact(1000))

else節に入れなくてもいいんじゃないかな

　一度書いちゃったので、今回は問題文の感じで進めていくことにしましょう。というか、皆さんはどっちの書き方が好きなのかな？

【答え】

　問題のコードを実行した結果を以下に示します。

RecursionError例外が発生した

　というわけで、「RecursionError例外が発生し、1000の階乗は返されない」というのが答え（の一部）となります。その理由については解説パートで見ていきましょう。

　本日はかわいいワンコの2枚目の画像はございません。大変申し訳ありません。だって、どんな感じにすればいいのか、思い付かなかったんだもん。

【解説】

　問題にあったfact関数は自身を再帰的に呼び出すことで階乗を計算します。

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n-1)

fact関数は再帰呼び出しにより階乗を計算する

　そして、Pythonでは再帰呼び出しの回数に制限を設けています。なぜかというと、関数呼び出しが無限に再帰して、関数の呼び出しスタックがオーバーフローすることを避けるためです。最大回数を超えるとRecursionError例外が発生します。この最大回数はsysモジュールのgetrecursionlimit関数で取得して、同じくsysモジュールのsetrecursionlimit関数で設定可能です。

　以下はgetrecursionlimit関数で再帰の最大回数を調べるコードの例です。

import sys

print(sys.getrecursionlimit())

getrecursionlimit関数で再帰の最大回数を調べる

　実行した結果を以下に示します。

CPythonでは1000回がデフォルト値

　手元の環境（macOS、Windows 10）用のCPythonではgetrecursionlimit関数の戻り値は1000です。つまり、最大の再帰の回数は1000回になりますね。「最大の再帰回数が1000で、1000の階乗を計算しようとしているんだからギリ何とかなるんじゃない？」と思う人もいるかもしれません。が、恐らく、対話環境が起動するまでにスタックが既に消費されているようで、「fact(1000)」呼び出しは筆者の手元の環境ではどちらでもRecursionError例外が発生しました。

　では、setrecursionlimit関数で最大の再帰回数を設定してみましょう。

sys.setrecursionlimit(1010)

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n-1)

print(fact(1000))

再帰の最大回数を1010にしたら1000の階乗が出力されるかな？

　実行結果は以下の通りです。

計算された！

　とまあ、ここまではすぐに分かるお話しです。が、Python 3.10以前とPython 3.11以降ではちょっとした断絶があります。詳しくはpython.jpにある「Python 3.11の新機能(その3）関数呼び出しのインライン化」などを参考にしてほしいのですが、Python 3.11では（Pythonで実装されている）関数の呼び出しがインライン化されました。

　関数呼び出しのインライン化が何かを詳細に書くのはこの記事では大変なので省略しますが、簡単にいえば、インライン化の副作用によって、Pythonで実装されている関数の再帰呼び出しが（実際には）何回でも行えるようになったということです。それでもなお、再帰の最大数が1000回に設定されているので、通常は再帰が深くなるとRecursionError例外が発生します。

　Python 3.11で行われた関数呼び出しのインライン化はあくまでも、Pythonコードの実行を高速化するためのものであることには注意してください。Pythonコードを評価して実行するコードはC言語で書かれていますが（これをceval関数と呼びます）、Python 3.10までは関数が呼び出されるたびに、その評価関数を再帰的に呼び出していました。しかし、Python 3.11ではこの再帰呼び出しをヤメにして、goto文によるループで処理するようにしたのです。関数呼び出しではなく、goto文によるループなので、関数呼び出しに伴うスタック消費がなくなり、その結果として再帰呼び出しを実質的には無限に行えるようになったと筆者は理解しています。

　例えば、次の関数を考えてみましょう。

import sys

def foo(n):
    if n == 0:
        print('recursion call finished')
        return
    else:
        foo(n-1)

sys.setrecursionlimit(1000000)
foo(100000)

再帰呼び出しするだけの関数

　このコードは再帰の最大回数を100万回に設定して、再帰する回数は10万回を指定してfoo関数を呼び出すものです（最大回数の方が1桁多い）。

　これをPython 3.10環境で実行すると次のようになります（Windows）。

何も言わずにPythonが終了している（プロンプトが「deep」になっている点に注目！）

　何も言わずに、プロンプトがPythonの対話環境ではなく、コマンドプロンプトのものになっている点に注目してください。これは、setrecursionlimit関数で設定した上限に届くよりも前にスタック領域を使い果たしてしまって、その結果、Python処理系そのものが落ちていることを示唆しています（macOSやUNIX系統のOSならsegmentation faultが発生するでしょう）。

　対して、Python 3.11で上のコードを実行するとどうなるでしょう（Windows）。