【海外エンジニア転職活動】Coding Interview鍛錬: 01.Recursion - フィボナッチ数（Fibonacci numbers）

問：フィボナッチ数（一般にF(n)と表記）

ja.wikipedia.org
のn番目の数を求めよ。

このような数式で表される。

f(0) = 0, f(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

例えばn=8の時、
答えは13

0, 1, 1, 2, 3, 5, 8, 13, 21

早速解いていく

早速解いていくよ

再帰の問題で定番のフィボナッチ。
今回も前回に引き続きRecursion（再帰）で攻めていく！
atsashimipy.hatenablog.com

1. 最初の0, 1 はそのまま。
2. それ以降はfib自身を繰り返す関数をコードしていく。

class Solution:
    def fib(self, n: int) -> int:
        
        if n == 0:
            return 0
        elif n == 1:
            return 1
        
        return self.fib(n - 1) + self.fib(n - 2)

秒！！

いやいや、これは流石に定番すぎー！

...と思いきや、

Time Complexity は O(2N)

秒で解けても、実際にこのコードでは

再帰の各レベルでの必要な演算量が、nに近づくにつれて指数関数的に増加してしまう！

圧倒的に遅い...

企業にもよると思うけど、これでクリアってところもあれば
O(N)で解いてねっていうところもあるかもしれないので、

次回

Memoization

乞うご期待！

ありがとうございましたー！