今回は、さまざまなアプローチでPythonの階乗を計算する方法を見ていきましょう。
Python の Factorial 関数
Python の階乗関数 factorial(n) は整数 n に対して定義されます。
これは n から 1 までのすべての項の積を計算します。
factorial(0)は1` とみなされる。
つまり、この関数は
factorial(n) = n * (n-1) * (n-2) * ... * 1, n >= 1
factorial(n) = 1, n = 0
|
したがって、factorial(4) = 4 * 3 * 2 * 1 = 24 となります。
この数学関数を Python でどのように書けばよいかを解析してみましょう。
math.factorial() を使う
を使用するために、math モジュールの階乗関数を直接使用することができます。
import math
def factorial(x):
return math.factorial(x)
print(factorial(5))
|
結果は以下の通りです。
120 |
他の方法を使ってこの関数を求めることもできます。
ここでは、繰り返し手順を使用してみましょう。
反復手順を使用する
1からnまでのすべての数を直接ループして、積を直接掛けることができる。
def factorial(n):
if n == 0:
return 1
prod = 1
for i in range(1, n+1):
prod = prod * i
return prod
if __name__ == '__main__':
print(factorial(4))
print(factorial(7))
|
結果は以下の通りです。
245040 |
それでは、Pythonの階乗関数に再帰的な方法を用いて見てみましょう。
再帰的手続きの使用
この関数を計算するために、再帰的手続きを利用することができる。
基本的に、この関数をより小さな部分問題に縮小します。
問題構造は減少積であるから、再帰を次のようにモデル化することができる。
factorial(n) = n * factorial(n-1), n >= 1factorial(0) = 1, n = 0 |
最後の行は基本ケースです。
これは再帰が停止する点であり、再帰を解くと最終的な積を得ることができる。
これに対応するPythonの関数を書くことにします。
def factorial(n):
if n == 0:
# Base case n = 0
return 1
else:
# Use the definition of factorial function
return n * factorial(n-1)
if __name__ == '__main__':
print(factorial(4))
print(factorial(7))
|
結果は以下の通りです。
245040 |
これは正しいように見える。
では、実際に再帰呼び出しで何が起こっているのかを解析してみましょう。
再帰呼び出しを使用する場合、必ず呼び出しスタックが存在し、基本ケースに到達するまで、プログラムの状態を継続的に保存します。
スタック要素は、対応するブロックから値が返された後、再帰が n = 0 から巻き戻されると、最終的に一つずつポップアウトされる。
下の図は、fact(3)を求めるためのプロセス全体を説明したものです。
全体のプロセスの最初の部分は、関数が1を返すまで、それらの再帰的な呼び出しのそれぞれが互いに積み重なるスタックの構築です。
関数が再帰的に呼び出すことができなくなったら、以下のように階乗の計算を開始します。
def fact_helper(accum, n):
if n == 0:
return accum
return fact_helper(accum*n, n-1)
def factorial(n):
return fact_helper(1, n)
if __name__ == '__main__':
print(factorial(4))
print(factorial(7))
|
関数が戻るとき，スタックの要素は上から順番に取り出される．最終的に main() スタックに到達したとき、関数は最終的に完了し、私たちは 6 という値を得ることができます。
Tail Recursive Calls
このプログラムは正常に動作しますが、再帰的関数の問題は、スタックサイズが入力サイズと同じだけ大きくなってしまうことです。
そのため、もし n が非常に大きな数であれば、再帰呼び出しのスタックは非常に大きくなり、スタックがオーバーフローする可能性があります。
これを避けるために、再帰関数をコーディングする際に、末尾再帰手続きと呼ばれる別のアプローチを使用します。
テールプロシージャコールは、中間結果を計算した後に再帰呼び出しを実行することを目的としています。
つまり、スタックサイズを大きくする代わりに、プログラムは全行程で同じスタックを使用することができるのです! 更新されるだけです。
つまり、再帰呼び出しは常に末尾になければならない。
これが「テールコール」である理由です。
245040 |
再帰呼び出しを直接最後に行うことはできないので、別のヘルパー関数を使って、実際の計算を行います。
このヘルパー関数は accumulator を保持し、この関数の現在の値を保持します。
トリックは、アキュムレータをパラメータとして再帰関数に渡し、accum*n を使って更新することです。
この方法では、中間状態を 1 つの変数に格納することになるので、1 つのスタック・フレームにしか格納されません。
結果は以下の通りです。
前と同じ出力が得られます。
まとめ
今回は、階乗関数の実装方法として、mathモジュールを使用する方法と、反復と再帰の両方を使用する方法について学びました。