Technically Impossible

Lets look at the weak link in your statement. Anything "Technically Impossible" basically means we haven't figured out how yet.

42 SILICON VALLEY Piscine 2017 Day04 Exercise 04 フィボナッチ数列と再帰の実践

昨日の投稿では再帰を説明した。あくまでも説明にフォーカスするため、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)としよう。最終的な再帰処理は、このようになる。処理が重複しているのが分かるだろうか?
f:id:espio999:20191219005149p:plain
n = 4の場合でこれだ。ここに至るまでにn = 3の場合、n = 2の場合のロジックも同様の構造で処理が実行される。つまり呼び出しの度に引数が0になるまでの処理を繰り返している。いくら言語処理系、CPUのキャッシュや効率化があるとはいえ、非効率に感じないだろうか?
n = 10の場合、ここまでの構造になる。描き切れないので引数の数字だけを記載している。ちなみに図示されている構造はn - 1の側の再帰で、n - 2の再起は省略している。つまり、全体構造の約半分だ。
f:id:espio999:20191219005216p:plain
指定された数が増えるほど、処理は非効率になる。しかし課題で求められているのはここまでなので、問題はない。しかし現実的には問題だ。

余談-メモ化再帰

この問題には解決法がある。動的計画法の一つ、メモ化再帰と呼ばれる方法だ。この方法を実装することによって、一度計算した処理を飛ばすことができる。
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)