概要
のような漸化式をPythonで定義する方法を示す。そのような再帰的な関数の例として、フィボナッチ数列 と階乗 のプログラムを書く。
漸化式のプログラム
初期が である のような漸化式を考えます。これは値が10のとき と出力される漸化式です。このプログラムは以下のようにすればできます。
def a(n): if n==1: return 1 else: return 2 * a(n-1) + 1
この関数に と代入すれば、
>>> a(10) 1023
となります。
このような関数には再帰的に定義されています。つまり、 の定義に が使われていることです。
例えば、 は次のように計算されます。
(1) より、 となる。
(2) より、 となる。よって、 である。
(3) より、 である。
よって、 である。これを計算すると である。
フィボナッチ数列のプログラム
フィボナッチ数列は次のような数列です。
フィボナッチ数列は次のようなプログラムです。
def Fib(n): if n == 0: return 1 elif n == 1: return 1 else: return Fib(n-1) + Fib(n-2)
これは前のプログラムとほとんど変わりませんが、 が使われています。
つまり、 が偽であり(i.e., ) 、かつ が真である(i.e., ) であるとき、 を出力します。それ以外のとき (i.e., )は を出力します。
これによって、例えば、
>>> Fib(2) 2 >>> Fib(10) 89
最後に階乗 のプログラムを書いて終わりたいと思います。