問題

問題文中の(1)、(2)に当てはまるものとして、適切なものはどれか。

フィボナッチ数列とは初項と第2項を1とし、それ以降の項については、前の2つ項の和とったものとして得られる数列である。数式として表現すると次のようになる。

$$ a_1=1, a_2=1, a_{n+2}=a_{n+1}+a_{n} (n=1,2,3,...) $$

このフィボナッチ数列の第n項の値を求めるプログラムをPythonで実装したものが、以下である。

def fibonacci(n):
    #フィボナッチ数列を計算する再帰関数
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)


print(fibonacci(300))

これを実行した例は次のようになり、フィボナッチ数列を正しく実装できていることがわかる。

fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(4) = 3
fibonacci(5) = 5
fibonacci(6) = 8

しかしながらこのプログラムには、引数として与えるnの値が大きくなっていくにつれて、ある重大な問題が起こる可能性がある。その問題とは「(1)」ということであり、これを解決するために「(2)」という手法が用いられる。

空欄(1) 空欄(2)
スタックオーバーフローを引き起こす可能性がある メモ化再帰
スタックオーバーフローを引き起こす可能性がある 統治分割法
並列実行数が急増するため、スレッド数の限界値を超えてしまう可能性がある。 メモ化再帰
並列実行数が急増するため、スレッド数の限界値を超えてしまう可能性がある。 統治分割法

選択肢

(a)

(b)

(c)

(d)

  • a
  • b
  • c
  • d

Python フィボナッチ数列

答え

(a)

解説

フィボナッチ数列のプログラムに与えるnの大きさを徐々に大きくしていって、処理がどうなるのかをみていきましょう。

call_count = 0

def fibonacci(n):
    #フィボナッチ数列を計算する再帰関数
    
    global call_count
    call_count += 1
    
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)


a = fibonacci(10)
print(a, call_count)

このプログラムは、問題文中のフィボナッチ数列を求めるプログラムを改変したもので、第n項の値と、それと同時に関数が実行された回数をカウントして出力します。

fibonacci(10)の場合 値:55 実行回数:177
fibonacci(20)の場合 値:6765 実行回数:21891
fibonacci(30)の場合 値:832040 実行回数:2692537
fibonacci(100)の場合 → タイムアウトが発生
fibonacci(1000)の場合 → RecursionErrorが発生

このようにnの値を増やしていくと、関数の実行回数が急速に増えていき、PCの性能や設定にもよりますが、n=100くらいになるとほとんどの場合でタイムアウトRecursionErrorが発生してしまいます。RecursionErrorとは、以下のようなものです。

Traceback (most recent call last):
  File "Main.py", line 20, in <module>
    a = fibonacci(1000)
  File "Main.py", line 17, in fibonacci
    return fibonacci(n-1) + fibonacci(n-2)
  File "Main.py", line 17, in fibonacci
    return fibonacci(n-1) + fibonacci(n-2)
  File "Main.py", line 17, in fibonacci
    return fibonacci(n-1) + fibonacci(n-2)
  [Previous line repeated 995 more times]
  File "Main.py", line 14, in fibonacci
    if n <= 1:
RecursionError: maximum recursion depth exceeded in comparison

なぜこのようなことが起こるかというと、このまま大量に関数を実行し続けると、コンピュータのコールスタック領域の限界を超えてしまい、スタックオーバーフローとなってしまう可能性が高いからです。これを未然に防ぐために、コンピュータやPythonの設定には最大再帰深度(再帰の最大値)が設定されており、この値を超えるとRecursionErrorなどが発生するわけです。したがって、空欄(1)については「スタックオーバーフローを引き起こす可能性がある」が正解です。

この問題を解決するための手段として「nの値と、それに対応する結果を記録しておいて、過去にnが同じ値で関数が実行されていた場合には、記録からその値を取得する」というものがあります。

例えば、fibonacci(6)を実行する場合を見てみましょう。(簡単のため、fibonacciをfiと表記しています。)

fi(6)
→ fi(5) + fi(4)
→ fi(4) + fi(3) + fi(3) + fi(2)
fi(3) + fi(2) + fi(2) + fi(1) + fi(2) + fi(1) + fi(2)
→ fi(2) + fi(1) + fi(2) + fi(2) + fi(1) + fi(2) + fi(1) + fi(2)
→ 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8

となります。ここで気づいた方もいるかもしれませんが、第6項を計算するために、第3項を3回も求めてしまっています。例えば第100項を計算しようとすると、計算量が膨大な第90, 80, 70項などを、何度も実行する必要があるのです。

これが、スタックオーバーフローを引き起こす原因となっています。この問題を解決する方法は非常に簡単で、一度計算したものは記録やメモ(つまりリストなどの変数)に保存しておくことです。第3項の実行結果をメモしておけば、fibonacci(6)を求める際には、fibonacci(3)を一回実行するだけで済みます。この手法を「メモ化再帰」と言います。したがって、空欄(2)は「メモ化再帰」が正解です。

メモ化再帰を適応したプログラム:

memo = {}

def fibonacci(n):
    #メモ化を適用したフィボナッチ数列を計算する関数
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
        return n
    else:
        result = fibonacci(n-1) + fibonacci(n-2)
        memo[n] = result
        return result

このプログラムならば、nが大きくなっても値を求めることができます。

fibonacci(100):
354224848179261915075

fibonacci(200):
280571172992510140037611932413038677189525

fibonacci(300):
222232244629420445529739893461909967206666939096499764990979600

 

 

テスト一覧

スキルテストが提供しているテストの一覧です。ぜひ学習や実力チェックに役立ててください。