确定递推公式有没有什么通法?

题目

确定递推公式有没有什么通法?
每次写程序一点头绪都没有,

答案

通法是没有的.关键是看递推公式的形式,不同的形式方法不同.
如
an=a(n-1)+p或an=qa(n-a)
这是最简单的等差型与等比型,这里就不赘述.
又如
an=p*a(n-1)+q,这种形式可以用不动点法
令an-d=p[a(n-1)-d]
通过比较系数,可以把d用p与q表示出来（d=q/(1-p)）
然后就化成了等比型,就可以求出an+d,进而求出an.
又如
an=p*a(n-1)+q*a(n-2)这样的形式
可以设
an-d*a(n-1)=p*[a(n-1)-d*a(n-2)]
仍然可以解出d,然后可以把an-d*a(n-1)求出,最后再求an.
还有an=[a*a(n-1)+b]/[c*a(n-1)+d],这是分式型.
这时要设
an-k=a*[a(n-1)-k]/[c*a(n-1)+d],然后通常可以解出两个k值（k1、k2）
然后再两式相比,得：
(an-k1)/(an-k2)=[a(n-1)-k1][a(n-1)-k2],则可以求出(an-k1)/(an-k2),进而求出an
总之,由递推公式求通项公式的类型相当多,每一种方法都不太一样,作此题时应该好好考虑考虑,确定一种最优解法.