フィボナッチ数を計算する関数を再帰で素直に書く。 def fib(n): if n < 0: return n return fib(n-1) + fib(n-2) このままではものすごく遅いので、メモ化すると良い。 というのは一般常識の内だろう。 Python には 3.9 からデコレーター functools.cache があるので、簡単だ。 from functools import cache @cache def fib(n): if n < 0: return n return fib(n-1) + fib(n-2) もう少し前のバージョンを使わなければならない人も安心して欲しい。 デコレーター functools.lru_cache が 3.2 から存在していて、 lru_cache(maxsize=None) と書けば実質的に cache と同じことをしてくれる。 実は上のフィボナッチ数を計算するプログラムは functools 公式ドキュメントの lru_cache 使用例から持ってきたものだ。 話はちょっと飛ぶのだが、昔やっていた NZMATH というプロジェクトをもう一度動かそうという動きがあるとかないとか。 いや動きがあるとは聞いているのだが、実際に動き出したかどうかはまだ見えていない。 そんな NZMATH にもフィボナッチ数を計算する関数 nzmath.sequence.fibonacci があった。 FIBONACCI = {0:0, 1:1} def fibonacci(n): """ param non-negative integer n return the n-th term of the Fibonacci effect FIBONACCI[n] = fibonacci(n) """ if n < 0: raise ValueError("fibonacci(n) 0 <= n ?") if n in FIBONACCI: retu...