漸化式とプログラム - あらきけいすけの雑記帳

高校で学修する漸化式の内容はというと、例えば

$a_{n+1}=2a_{n}+1$ ,　 $a_1=1$

のような漸化式から一般項 $a_n=2^{n-1}(a_1+1)-1$ を出すような計算の演習になっている。これは微分方程式、例えば $y'=y$ から $y=y(0)e^x$ を導出することと似ている。つまり「微分方程式」の離散版が「漸化式」であり、微分方程式の解を求めることも漸化式の一般項を求めることも、「局所的な変化のルール」からグラフの全体を $x$ あるいは $n$ の関数として書き下すことに他ならない。（ということを意識して並列して整理してある高校生向けの参考書ってあるのかな？微分方程式が課程から消滅しているから存在しないかな？）
さてこの漸化式をCのソースコードで書くと次のようになる*1

int a=1;
while(1){ a= a*2 + 1; }

このコードで重要なことは変数 a に記録された値はループの各ステップで更新されてしまい、以前の値は永久に失われてしまうということ。あるいは一般項を n の関数として表現しなくてもいいこと。数値計算で実際に問題を解いた経験のある人には自明なことだが、漸化式は一般項を求めることを強制されているという洗脳を受けた人にプログラミングの講義をするときに、この部分は概念上のネックとなる。1回書けば直るけど。

*1:もちろんこのコードは無限ループであり、計算は int の表現領域を越えた時点で破綻する。手許の環境では実際に実行するとオーバーフローが起きた時点で -1 に飛んでしまい、そのまま値が固定される。それにこのコードは出力をしないので printf() などは各自で補う必要がある。