解递归方程的三个方法

1、主方法求解递归式

一种求解大部分递归式的公式。给出递归式: T(n) = a * T(n/b) + f(n) ，其中a>=1，b>1，f(n)是给定的函数，T(n)是定义在非负整数上的递归式。

2、递归树求解

用主方法求解不了的递归式，我们可以用递归树来猜测解的上界，然后用代入法来证明解的正确性。递归树的求解精确度稿丛取决于画递归树的精确度。

3、代入法

比如我们求解，递归式T(n) = 2T(n/2)+n，我们猜测解是O(nlgn)，我们要寻找到一个常数c，使得T(n)<=cnlgn。

即T(n) <= 2c(n/2)lg(n/2)+n <= cnlgn-cnlg2+n = cnlgn-cn+n

只要c>=1，T(n)<=cnlgn，所以我们的猜测是正确的。

要注意的是，代入法全凭经验，通常用递归树来确定上界，然后用代入法再证明。

扩展资料：

设p0，p1，…，pn，…是一个序列。如果pn和序列中在它前面的若干项联系起来的一个关系式对所有大于等于某个整数n0的整数n都是有效的，则称这个关系式为递归关系(recursive relation)式。

如：设桐敬磨(a0，a1，...，ar，...)是一个序列，把该序列中的ar和它前面的几个ai(0≤i<r)关联起来的方程称做一个递归关系。如关系式:ar=3ar-1 (r≥1)和错排数:Dn=(n-1)(Dn-1+Dn-2) (n=3，4，...)，局斗都是递归关系。

首前尺先，这个不是缓悔神matlab利用递归求解差分方程扰亏，而是递推；差分方程其实就是递推关系式。

然后这个循环：

for

i=N+1:N+length(n),

y(i)

=

-a1*y(i-N:i-1)'

+

b1*x(i-N:i-N+M)'

end

其实是因为：

y[n]

+

a1*y[n-1]

+

a2*y[n-2]...

+

an*y[n-N]

=

b0*x[n]

+

b1*x[n-1]

+

...

+

bm*x[n-M]

所以：

y[n]

=

-（a1*y[n-1]

+

a2*y[n-2]...

+

an*y[n-N]

）+

b0*x[n]

+

b1*x[n-1]

+

...

+

bm*x[n-M]

具体来说，就是：

我们已知了y1、y2、y3。。。yN，然后通过循环依次求得yN+1、yN+2等等。。。

---