第3回: フィボナッチ数列や階乗などの再帰的な関数をPythonで作る

概要
のような漸化式を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

最後に階乗 のプログラムを書いて終わりたいと思います。

階乗のプログラム

一見すると階乗は再帰的な関数とは思われないかもしれません。例えば、3の階乗は です。しかし、階乗も上のプログラムと同様に再帰的に定義されます。

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

このように定義することによって、

>>> Factorial(3)
6
>>> Factorial(5)
120

と表示されます。プログラムの仕組みは前のと同じです。

だいたいこんな感じです。参考になってくれたら嬉しいです。

僕から以上