昨日の投稿では再帰を説明した。あくまでも説明にフォーカスするため、42SV Piscine 2017の課題から離れて、独自の問題を用いた。考えやすい問題で、再帰する価値のある処理を示すためだ。
42 SILICON VALLEY Piscine 2017 match/nmatchを考える（番外編） 再帰の説明 - Technically Impossible
今回は再帰の実践として、Day 04 Exercise 04に挑戦する。これはフィボナッチ数列の問題だ。実際のところ、フィボナッチ数列は再帰を用いることなく解くことができる。むしろ再帰を用いるのは非効率だ。しかし課題は再帰を使用することを求めている。
本日の投稿では、実践と共に次のことを示そうと思う。
この投稿がPiscine受講生の一助になれば、と思う。
準備
Pythonに限らず、言語や開発ツールのインストール不用で、直接オンラインでコードを実行することのできる環境が用意されている。例えば次のサイトだ。サンプル・コードをコピーし、試行錯誤しながら参照してほしい。
paiza.io
Exercise 04
• Create a function ft_fibonacci that returns the n-th element of the Fibonacci
sequence, the first element being at the 0 index. We’ll consider that the Fibonacci
sequence starts like this: 0, 1, 1, 2.
• Obviously, ft_fibonacci has to be recursive.
指定された個数のフィボナッチ数列を列記せよ、というのが課題だ。再帰を使え、と指示されている。
フィボナッチ数列とは、n番目の数字が「n-1番目 ＋ n-2番目」になる数列のことだ。最初は0、その次は1と決まっている。従って3番目の数字は1、4番目は2 = 1 + 1、5番目は3 = 2 + 1と続いていく。
再帰を使わない解き方
単純にループで、最初の数列から順番に必要な数字を足し算すればよい。最初の0、その次の1は決まっているので、その部分だけは例外だ。この処理を関数化すればよい。このような具合だ。
def fibonacci(val): fib = [] for i in range(val): if i == 0: fib.append(0) continue; elif i == 1: fib.append(1) continue; fib.append(fib[i - 1] + fib[i - 2]) return fib
考えなければならないのは、どの部分が再帰するのかということだ。
再帰を使う解き方
前回、再帰の特徴として次のことに触れた。
- 再帰は、関数内部から、同じ関数を呼び出す。
- 最後に呼ばれた関数が、最初に出力を返す。
- 呼ばれた関数全ての結果を引き次いで、最初に呼ばれた関数が、最後に出力を返す。
例えばフィボナッチ数列の先頭3個、出力すると考える。先頭2個の数字は決まっているので、この部分の再帰は不要だろう。ならば再帰が始まるのは3個目からだ。
3個目の数字は先頭2つの数字の和なので、再帰で求めるならば、
- 最後に呼ばれた関数が、最初の数字を出力する。
- 最初に呼ばれた関数が、3個目の数字を出力する。
つまり、上記コードでの次の箇所が再帰呼び出しに書き換わることが推察できる。
fib.append(fib[i - 1] + fib[i - 2])
ならば、この足し算自体を再帰処理すべきなのだろうか、あるいは別々に再帰すべきだろうか？
- 関数は数字を返す。
- その数字は足し算の結果だ。
再帰処理は同じ関数が入れ子構造で呼び出されるので、その処理は共通でなければならない。従って、別々に再帰することになるのだろう。該当部分の処理は次のように書き換わるのではないか。2つの再帰処理が必要とされる。
fibonacci(i - 1) + fibonacci(i - 2)
残った処理はループだ。これは再起に含めるべきだろうか？前回、次のことにも触れた。
もしループを再帰に含めるならば、再帰構造と合わせて多重ループ的な構造になる。これは複雑になりそうで、避けたほうが良さそうだ。
関数外のループ中から関数を呼び出すほうが、再帰処理構造がシンプルになるだろう。ここまでの前提で処理を関数化すれば、このようになる。
def fibonacci(val): if val == 0 or val == 1: return val return fibonacci(val - 1) + fibonacci(val - 2)
この関数を、関数外のループ処理から繰り返し呼び出す。前回同様、再帰を用いない場合に比べて、コードの見た目は簡素になった。コードの全体は、サンプル・コードを参照してほしい。
大いなる無駄？
ループで処理した場合の流れは非常に考えやすい。数列を構成する数字を順番に作成し、出力すればよいからだ。再帰を用いた場合も同様だが、この処理には大いなる無駄が隠されている。分かるだろうか？
仮に先頭4個の数字を出力する（n = 4）としよう。最終的な再帰処理は、このようになる。処理が重複しているのが分かるだろうか？
n = 4の場合でこれだ。ここに至るまでにn = 3の場合、n = 2の場合のロジックも同様の構造で処理が実行される。つまり呼び出しの度に引数が0になるまでの処理を繰り返している。いくら言語処理系、CPUのキャッシュや効率化があるとはいえ、非効率に感じないだろうか？
n = 10の場合、ここまでの構造になる。描き切れないので引数の数字だけを記載している。ちなみに図示されている構造はn - 1の側の再帰で、n - 2の再起は省略している。つまり、全体構造の約半分だ。
指定された数が増えるほど、処理は非効率になる。しかし課題で求められているのはここまでなので、問題はない。しかし現実的には問題だ。
余談－メモ化再帰
この問題には解決法がある。動的計画法の一つ、メモ化再帰と呼ばれる方法だ。この方法を実装することによって、一度計算した処理を飛ばすことができる。
ja.wikipedia.org
これは計算結果を再帰処理中に記録しておき、計算済みであれば再帰せず、計算済みの結果を返す仕組みだ。これを実装すると、コードは次のように変わる。
def fibonacci(val, ret): if val == 0 or val == 1: return val if len(ret) >= val: return ret[val] else: return fibonacci(val - 1, ret) + fibonacci(val - 2, ret)
関数外のループ処理中に、戻り値を配列に格納している。この配列を関数中から参照し、計算済みを判定している。計算済みならば、その結果を返し、そうでなければ再帰する仕掛けだ。
ならば、この結果を課題として提出したらどうか？それはダメなのだ。問題文に次の指定がある。この引数指定ではメモ化は使えない。
• Here’s how it should be prototyped :
int ft_fibonacci(int index);
ちなみにこのテクニックは、再帰を分かりやすく実装するための一案でもある。再帰の分かりづらさの一つは、戻り値を繰り返し継承することにあるのではないだろうか。共通の配列変数を用意し、戻り値の代わりに配列変数を操作することで、繰り返し継承される戻り値を意識する必要は無くなる。
前回のサンプルで、戻り値を指定せずにポインタ的に配列を用いた処理を示した。目的が異なるだけで、メモ化が実現してることは、前回のコードと同じことなのだ。前回コードと見比べてほしい。
もし前回の内容が理解できていたならば、メモ化という新しい概念は、実は馴染みのある考え方だったはずだ。
impsbl.hatenablog.jp
サンプル・コード
再帰を使わない場合
def fibonacci(val): fib = [] for i in range(val): if i == 0: fib.append(0) continue; elif i == 1: fib.append(1) continue; fib.append(fib[i - 1] + fib[i - 2]) return fib n = 10 print(fibonacci(n))
再帰を使う場合
def fibonacci(val): if val == 0 or val == 1: return val return fibonacci(val - 1) + fibonacci(val - 2) n = 10 fib = [] for i in range(n): fib.append(fibonacci(i)) print(fib)
メモ化再帰
def fibonacci(val, ret): if val == 0 or val == 1: return val if len(ret) >= val: return ret[val] else: return fibonacci(val - 1, ret) + fibonacci(val - 2, ret) n = 10 fib = [] memo = [] for i in range(n): fib.append(fibonacci(i, memo)) print(fib)
