Pythonでフィボナッチ数列の関数作成とtree recursion algorithm

code warの課題でフィボナッチ数を求める課題があったのですが、苦戦したので記録がてらout putしてみます。
課題：https://www.codewars.com/kata/529adbf7533b761c560004e5
そもそも、code warsというのはプログラミングの練習が無料でできるサイトという感じなので、興味あれば皆さまやってみると良いと思うのですが、本題からずれるため詳細は各自調べてみてください。

私は、Tommy blogというブログを主に独学でPythonの学習を行っているのですが、
参照⇦このロードマップを完走した。
このロードマップの課題の中にフィボナッチ数列の作成という記事があるので、回帰関数によるフィボナッチ数列の作成は理解していました。
詳しくはこの記事

def fibonacci(n):
    if n in [0, 1]: # nが０または１のとき
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

またこの様にlistを使って書くこともできるようですね。（codewarsの課題から引用）
しかし、このままではnが５０とか１００とか大きい数になってくると時間がかかってしまいます。

それはなぜかと言うと、例えば、n = 100のときはfibonacci(99) とfibonacci(98)をまず記憶し、次にfibonacci(99)の中ではfibonacci(98)とfibonacci(97)。その中のfibonacci(98)ではfibonacci(98)とfibonacci(97)。。。。（以下略）という風に枝分かれ式に計算が行われていき。同様のことが元のfibonacci(98)でも行われるという風になっているからです。

すこし、わかりにくいですね。すみません。
せっかく、fibonacci(97)を求めているのに、別のところでもfibonacci(97)を求めるという非常にもったいない？方法が取られているのです。
これをtree recursion というらしいですね。
生物の進化などで使われる樹形図みたいな感じですかね。
英語ですがわかりやすい図と解説が乗っているPDFがありましたので参考にしてください。参考PDF
また、このPDFにはこの時間が非常にかかるプログラムを改善する方法が乗っていましたので日本語でわかる様に解説しておきたいと思います。（著作権侵害あれば削除するのでコメントください）

def fibonacci(n):
    fib, fib_pre = 1, 0 # nが０または１のとき
    if n == 0 : return fib_pre
    elif n == 1 : return fib
    else:
        for i in range(n-1):
            fib, fib_pre = fib+fib_pre, fib #右辺のfib, fib_preは一つ前のもの。
        return fib

賢いですね。こうすれば別のところで同じ数値を計算することがなくなります。
しかし、これだけでは課題のクリアにはなりませんでした。

まだ、遅いらしいです。

その理由ですが、確かに、数値一つn=1000とかだけを求めるならば、一番簡単なコードが上記のようなものになるのですが、一回にn=1000, n=800, n=900, n=1020とか複数のフィボナッチ数を求めるとなるとさっき、n=1000まで求めたのに使えないやんとなり、もったいないですし、いちいち計算することが時間を余計につかってしまうことになるのです。

そこで、解決法としては辞書型に収納する方法が考えられました。
（まあ、順番通りだしリストでもいいのか。）

fib_dct = {0:0, 1:1} #関数よりも前に辞書を定義してしまう。
def fibonacci(n):
  fib, fib_pre = 1, 0 #tree recursion の回避を行うために必要
  if len(fib_dct)>n: #fib_dctに収納されている数がn以上ならすでに計算されているはず。
    return fib_dct[n]
  else:
    if n > 1: #n=0, 1はすでにretrunされているので不要ではある
      i =0 #これもi=0から始まるのでなくても大丈夫だけどわかりにくいからつけた
      for i in range(n-1):　# n = 3のときiは[0, 1, 2]となる
        fib, fib_pre = fib+fib_pre, fib
        if i > len(fib_dct)-3: #ここがむずい。まだ辞書に入っていないものを収納したいけど、初めからlen(fib_dct)は２以上なので、３を引いておかないといけない。
          fib_dct[n] = fib
        i +=1
    return fib_dct[n]

こう言う感じになってしまい、めちゃくちゃわかりにくくなってしまいました。
すみません。スマートさがなく。

しかし、この辞書型の考えを使い、辞書を関数の外で定義する必要も内容にスマートにすることができました。（これを残したかったから記事にした。）

def fibonacci(n):
    dct = {0:0,1:1} #n=0の時０、n=1のとき1
    def fib(n): #あらたな関数の定義
        if n not in dct: #nが初めて出た時には辞書に収納する
            dct[n] = fib(n-1)+fib(n-2)
        return dct[n]
    return fib(n)

これは辞書型に回帰的な関数の使用、さらに中に関数を使っているので少し抽象的になってしまいますが短くてつよいですね。

このような感じです。長文でわかりにくくなってしまいますたが、似た様なことで悩んでいる初心者がいれば参考になれば幸いです。