フィボナッチ数列にお世話になりました。

こんにちは。
自分なりに書き方を色々検討してみました。

参考にして頂ければ幸いです。
以下の記述はよく見る奴です。

fib_1.py

def fib(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    else:
        return fib(n-1) +fib(n-2) 

こんな書き方もあると思います。

fib_2.py

def fib(n):
    if n == 1 or n == 2:
        return n-1
    return fib(n-1) +fib(n-2) 

シンプルな記述に最適化が出来て、手を叩いて喜びましたが、
重複する計算が多いので、何とか最適化したいです。
有識者のアドバイスを参考にするとメモを用意し、
該当するものから取り出すことで計算を削減できるそうです。

fib_3.py

class fib:
    def __init__(self):
        self.table ={}
    def cal(self,n):
        if n <= 2:
            return n-1
        
        if n in self.table:
            return self.table[n]
        
        self.table[n] = self.cal(n-2)+self.cal(n-1)
        return self.table[n]

fib_sequence = fib()

再帰処理 + メモ、なるほど。
こんなことも出来るんですね。
ちょっといじりました。

fib_4.py

def fib(n):
    if n <= 2:
        return n-1
    
    if n in memo:
        return memo[n]
    memo[n] = fib(n-2)+fib(n-1)

    return memo[n]

memo = {}

メモで簡略化する以外にも貪欲法というアプローチがあるようですが、
それはまた今度にします。

やりたいことをイメージし、
アプローチを色々試してみる事は楽しいです。

ココには for 文を使った方法もありました。素晴らしい!!

イメージが付かなくて困っている方は、ワンランクレベルを下げて、
こちら の記事で準備運動をすると良いと思います。
参考になります、これも素晴らしい記事でした。