fibをやろう
プログラミングの鍵は再帰関数なのか？
このワークシートはMath by Codeの一部です。
＜フィボナッチをどうする？＞
forも、whileも宣言型でリスト化できたら、
とてもうれしい。
行数が減るからよい。
あまり、１つにまとめると可読性が落ちるのでそこは注意だ。
ところで、私はgeogebraに出会ったころ
フィボナッチ数列に苦戦した。
昔は、関数型プログラミングも知らなかったので
行列を使って無理やり求める方法とかを使ってしのいでいた。
Sequence(Element({{1,1,0},{1,0,0},{0,0.1}}^(n-1),{{1},{1},{1}},2),n,1,10)
＜漸化式はIterationList＞
geogabraには漸化式にあたるiteration、iterationListがあった。
IterationList( <関数>, <開始値>, <反復回数> )
f=x^2なら、
IterationList(f, 3, 2)=> {3, 9, 81}
IterationList( <式>, <変数>, …, <開始値>, <反復回数> )
IterationList(a+b,a,b,{1,1},5) => {1, 1, 2, 3, 5, 8}
漸化式はIterationListで
＜フィボナッチ数列の立ち位置＞
中学・高校数学でのフィボナッチ数列の立ち位置は、漸化式と一般化の一例として
相似や行列や黄金比の話題にからめて扱われることが多いね。
プログラミングの文脈では、再帰関数の例として取り扱われることが多いね。
フィボナッチ数列のおもしろいところは、再帰関数をまともに作ると、
再帰関数の学習としても手頃なのに、番目が増えると急激に処理が遅くなってしまうところだ。
そのために、再帰関数の導入として使われるのに、再帰関数そのままではダメだよねという結論になる。
そこで、結局、再帰を使わないとか、再帰を使うけどメモ化を使いましょうとか、
別の方向にいくことになるんだね。
＜メモ化はキャッシュ利用＞
フィボナッチ数列を再帰関数を使う方法は
[IN]Python
#=========================
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
fib(30)
#=========================
[OUT]
832040
こんな感じです。30番目まではわりとすぐなのですが、35番目あたりから急激に待たされます。
60番目のfib(60)なんて、回答がいつになるかわかりません。
問題：なぜ番号が2倍になるだけで急に処理に時間がかかるのでしょうか？
再帰関数は、ｎ番の処理をするために、n-1番とn-2番の処理を依頼します。
だから、だから、fib(30)は、fib(31),fib(32),.....,fib(60)のために何回も呼ばれるのです。
これはnが59以下のfib(n)すべてについて当てはまります。無駄のカタマリですね。
言い方を変えてみよう。
fib(29)までの処理をA秒,fib(30)までの処理をB秒とすると、
fib(31)の処理はA+B秒ですから、Bのおよそ2倍になるのです。
だから、nを1増やしただけで2倍近くに膨れるのですから、n=30からn=60への変更は
膨大な時間増加になるのです。
そこで、キャッシュメモリーの利用です。たとえば、fib(31)を求めるのに必要なfib(30),fib(29)は
計算済みのはずです。もちろんそれ以下のnについてもfibは計算してあるはずですから、
繰り返し再計算することを避けて、一時記憶しておき、それを呼び出します。
その仕組み自体をプログラミングするのも大変なので、「パッケージ」にお任せするのです。
それが、キャッシュ利用、メモ化とも呼ばれる技ですね。
次のように、先頭に2行付け足すだけです。
1000番目でも一瞬で計算できます。すごい！
[IN]Python
#=========================
from functools import cache
@cache
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
fib(1000)
#=========================
[OUT]
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
geogebraではどうでしょう。
IterationListで求めましょう。
fib30,fib35,fib100と即座に数列を返してくれます。
geogebraさん。ありがとうございます。
IterationListでfib100もすぐ出せる
＜再帰なしのfib＞
再帰によるメモリの無駄な増殖を抑えるには、もう一つの方法があります。
それは、forやwhileにおきかえることです。番号指定ではありませんが、
大きなサイズもすぐに出せます。
[IN]Python
#==================================
def fib(n):
a, b = 1, 1
while a < n:
print(a, end=' ')
a, b = b, a+b
print()
fib(100000000000)
#==================================
[OUT]
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 20365011074 32951280099 53316291173 86267571272
途中の表示は不要なので n番目だけを表示し、whileでなくforにしてみます。
[IN]Python
#==================================
def fib(n):
a, b = 1, 1
for i in range(n-1):
a, b = b, a+b
return a
fib(1000)
#==================================
[OUT]
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
この発想は、geogebraのIterationListと同じだと思われる。
きっと、
IterationListは、再帰とはちがうロジックだから、メモリのムダ遣いがなくて素早い反応だったんだろう。
質問：geogebraのIterationListを使って、フィボナッチ数列以外の漸化式から生まれる数列はできますか。できるとしたら、どんなのができるでしょう。