フィボナッチ数列の場合、Aは正則です。N+1番目のフィボナッチ数列を調べるばあい、末尾再帰 F :- F( A X)が N 回呼び出されますが、行列 A の N 乗 と ベクトル X の積と、Fの結果が一致します。 今回は素直にnumpyで行列のN乗を使ってますけれども、 スペ…

フィボナッチ数列の場合、Aは正則です。が、ちょっと脱線して、Aが正則でない場合を考えるに、X = A Xを繰り返すことで、XはAの固有値が最大になる固有ベクトル（の倍数）に近づいていきます。（べき乗法） 。。。って、放送大学 「数値の処理と数値解析（'1…

そう考えると、ならばとなります。というわけで、線形代数を使うと、（若干手間はわかかりますが） 再帰を行列のべき乗に代替したり、再帰関数が終了するかどうかを比較的容易に判定することが出来る、はずです

たとえば、フィボナッチ関数を考えます 例によって 変な擬似言語 F(0 x1 x2) :- 0 F(0 x1 x2) :- x2F(x,y) :- F(n-1,x2,x1+x2) で、ここで引数を n次のベクトルだと考えてみます X={n x1 x2 1} ベクトル F( [0 x1 x2 1]) :- 0 #ベクトルXの第1要素が0 F( [1 …

今回は再帰関数を、行列のべき乗に直してみます。その３とか書いてあるけど、記事が増えたので適当にナンバリングしてみただけです。（雑）