📂アルゴリズム

再帰関数を使用する際に注意すべき理由

注意

プログラミングを初めて学ぶ際、どんな言語でも「再帰関数は慎重に使うべきだ」という警告が付く。実際再帰関数はそれほど頻繁に使われるテクニックではないため、その理由は説明されないことが多いが、学ぶ側からすると、これほど良いものをなぜ避けるのか理解が難しいかもしれない。例を見てみよう。

例

def fibo1(n) :
    if n==1 or n==2 :
        return 1
    else :
        return fibo1(n-1) + fibo1(n-2)
 
for i in range(1,11) :
    print(fibo1(i))

関数の再帰呼び出しは、プログラミングをしながら遭遇する様々な問題に対して、シンプルでありながらエレガントな解決策となる。コードを書きやすく、読みやすいというのは、大きな利点であり、通常は複雑になり得るコードを単純化する。たとえば、フィボナッチ数列を返すプログラムを作る必要がある場合、再帰関数を通じて簡単に実装することができる。上のようなPythonのコードを実行すると、次のようにフィボナッチ数列の第$10$項までを計算してくれる：

問題は、この方法が私たち人間にとっては便利だけれど、コンピュータにとって受け入れがたいほど非合理的だということだ。コンピュータは、呼び出される度にreturn fibo1(n-1) + fibo1(n-2)という計算を実行しているに過ぎず、 $$ a_{n} : = \begin{cases} 1 &, n \le 2 \\ a_{n-2} + a_{n-1} &, n \ge 3 \end{cases} $$ の再起方程式を理解しているわけではない。メモリのどこかに前に求めた項が保存されていても、再帰関数を作成する際、プログラマーが要求したのは「前の項を参照すること」ではなく「前の項を計算すること」だった。次は、上記の関数が呼び出されるたびにそれを知らせるように修正したものであり、$a_{10}$を計算する過程をGIFで表示したものである：

$a_{10}$が計算されるためには、$a_{8}$と$a_{9}$が計算されなければならない。しかし、$a_{9}$を計算するためには、$a_{7}$と$a_{8}$が計算されなければならない。この事実だけを見ても、$a_{10}$が呼び出されるためには、$a_{8}$が少なくとも２回は呼び出されなければならないことがわかる。次は、実際にfibo(10)を計算するために、各fibo(n)が何回呼び出されるかを示している：

fibo(n)	回数
fibo(9)	1
fibo(8)	2
fibo(7)	3
fibo(6)	5
fibo(5)	8
fibo(4)	13
fibo(3)	21

面白いことに、フィボナッチ数列を計算する際の重複呼び出しは、フィボナッチ数列に従って増加する。このような重複呼び出しは、メモリでも時間でも莫大な無駄を引き起こす。さらに、再帰関数の本質が「繰り返し」である以上、これらの問題は常に付きまとうことを理解しておかなければならない。

これらの問題を回避する方法として動的プログラミングというのがあるが、実際この方法は再帰関数を使わないのとほぼ同じだ。動的プログラミングは再帰呼び出しの問題を解決してくれるわけではなく、再帰呼び出しを使うべきでない問題を正確に理解した時に、再帰関数の代案として使われるのである。

コード

import time
 
def fibo1(n) :
    if n==1 or n==2 :
        return 1
    else :
        return fibo1(n-1) + fibo1(n-2)
 
for i in range(1,11) :
    print(fibo1(i))
 
def fibo(n) :
    if n==1 or n==2 :
        return 1
    else :
        print("fibo(",n,") 호출됨!")
        return fibo(n-1) + fibo(n-2)
 
for i in range(1,11) :
    print(fibo1(i))
 
print(fibo(10))

参照

• ラプラス展開