Python(10)再帰のお勉強:自然数の階乗

前の関連記事：Python(9)再帰のお勉強:ユークリッドの互除法

return f(x) となっている場合と違って、return x * f(x) は末尾再帰にはなりません。再帰で呼び出したf(x)の戻り値を計算をしてからreturnしているからです。

return n * factorial(n-1)で終わるのは末尾再帰ではない

自然数Nの階乗　N! = 1 × 2 ×…×(N-1) × N

def factorial(n):
    for i in range(1, n):
        n *= i
    return n
print(factorial(4))

普通はfor文でこんな感じに書けますけど、これを再帰で書いてみます。

漸化式で書けるということは再帰で書けるということですのでまずは漸化式にしてみます。
$$N! =\begin{cases}
1 & (N=1)\\
N\times (N-1) & (N>1)
\end{cases}$$
これを関数factorial()で定義します。

$$${\rm factorial}(n) = n!$$$ (nは自然数)

関数factorial()の漸化式で書くと以下になります。
$$\begin{cases}
{\rm factorial}(1) = 1\\
{\rm factorial}(n) = n\times{\rm factorial}(n-1)& (n>1)
\end{cases}$$
これを再帰で書くと

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)
print(factorial(4))

これを実行すると24が出力されます。

def factorial(n):
    if n == 1:
        return 1
    else:
        m = n
        n -= 1
        return m * factorial(n)
print(factorial(4))

自分自身を呼び出していることをはっきりさせるために引数の式を外にだすとこのようになります。

factorial(n)が関数の最後に書いてあり一見末尾再帰に見えますが、factorial(n)の戻り値にmをかけてからreturnしているので末尾再帰にはなりません。


青色の行きだけでなく、帰りのピンク色のところでも計算しているのがわかります。

線形再帰の型にはめて再帰を除去する

Python(8)線形再帰を非再帰に変換する方法で再帰を除去してみます。

def factorial(n):

    if n == 1:  # CODE_A
        return 1

    if n > 1:  # CONDITION_A

        m = n  # CODE_B
        n -= 1

        return m * factorial(n)  # CODE_C

print(factorial(4))

11行目のm * がCODE_Cに相当すると思われます。

CODE_Dはありません。

これを非再帰に変換します。

リストstackにはmを収納します。

def factorial(n):
    if n == 1:
        return 1
    stack = list()
    while n > 1:
        m = n
        n -= 1
        stack.append(m)
        if n == 1:
            return 1
    while stack:
        n *= stack.pop()
    return n
print(factorial(4))

うーん、これは1が出力されてしまいます。

CODE_Aが不要なのですよね。

def factorial(n):
    stack = list()
    while n > 1:
        m = n
        n -= 1
        stack.append(m)
    while stack:
        n *= stack.pop()
    return n
print(factorial(4))

CODE_Aをなしにするとうまくいきます。

なかなか機械的に変換というわけにはいきませんね。

if文とreturn文を型にはめるところがよくわからないのですよね。

帰り道の計算も引数にして末尾再帰にする

この図で青字部分が行きの計算です。

ピンクの字が帰り道の計算です。

行きで得たmを帰り道で使っています。

帰りで計算しているものを行きで計算しても同じことなのでこのmを引数にいれてfactorial()を末尾再帰に変換します。

def factorial(n, m=1):
    if n == 1:
        return m
    return factorial(n-1, n*m)
print(factorial(4))

これで同じ結果が得られます。

これはPython(9)再帰のお勉強:ユークリッドの互除法の関数gcd()と同じパターンにできますね。

def factorial(n, m=1):

    if n == 1:  # CODE_A
        return m

    if n > 1:  # CONDTION_A

        m *= n  # CODE_B
        n -= 1

        return factorial(n, m)

print(factorial(4))

この再帰を除去します。

def factorial(n, m=1):
    if n == 1:
        return m
    while n > 1:
        m *= n
        n -= 1
        if n == 1:
            return m
print(factorial(4))

while文を抜るのに7行目でif文を使っていますがwhile文を抜けるときはn > 1なので n == 1といえるのでif文は省略できますね。

def factorial(n, m=1):
    while n > 1:
        m *= n
        n -= 1
    return m
print(factorial(4))

再帰の深さの限界を調べる

再帰には呼び出せる数の限界があります。

sys.getrecursionlimit()で調べることができます。

import sys
print(sys.getrecursionlimit())

これを実行してみると結果は、1000。

もっとすごい数字が出てくるのかと期待しましたがこんなものでしょうか。

def factorial(n, m=1):
    if n == 1:
        return m
    return factorial(n-1, n*m)
print(factorial(998))

やってみると998が限界でした。

999以上にするとRuntimeError: maximum recursion depth exceeded in comparisonというエラーがでてきます。

この限界はsys.setrecursionlimit(limit)で変更できます。

import sys
sys.setrecursionlimit(500)

500に限界を変更するとprint(factorial(498))が限界になりました。

逆に限界を2000に増やしてみると、、、

import sys
sys.setrecursionlimit(2000)
def factorial(n, m=1):
    if n == 1:
        return m
    return factorial(n-1, n*m)
print(factorial(1998))

1998まで求められます。

あんまり増やすとクラッシュするらしいです。

どこでクラッシュするかはプラットフォームによって異なるそうです。

数学 - JavaScriptとPython、再帰 & メモ化でアッカーマン関数！( @codeiq , @nkawagashira より) | Kamimura's blogでは10000000まで増やしています。

factorial()でやると結果がすごいことになりそうなので試していません。

メモ化 - Wikipediaというのは情報工学の専門用語なのですね。

Python(5)クロージャ(Closure)のお勉強のときにメモ化という単語を知ったのですけど専門用語とは知りませんでした。

参考にしたサイト

sys.getrecursionlimit()
現在の最大再帰数を返します。デフォルトでは1000になるようです。

sys.setrecursionlimit(limit)
Python インタプリタの、スタックの最大の深さを limit に設定します。

数学 - JavaScriptとPython、再帰 & メモ化でアッカーマン関数！( @codeiq , @nkawagashira より) | Kamimura's blog
sys.setrecursionlimit(10000000)を使って再帰の深さの限界を増やしています。

メモ化 - Wikipedia
メモ化、は情報工学の専門用語です。

次の関連記事:Python(11)再帰のお勉強:フィボナッチの数列