什么是线性递归数列
当递推式中只含数列中的项,而无常数项或其它项时,就叫做递归公式。递归程序设计的公式化方法是一种简单而有效的设计思想,它把程序设计和程序理解的难点都集中到递归公式上。由递归公式设计出的程序具有标准的分支结构,编写和理解都要简单的多
程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。
递归,就是在运行的过程中调用自己。
构成递归需具备的条件:
1,子问题须与原始问题为同样的事,且更为简单;
2,不能无限制地调用本身,须有个出口,化简为非递归状况处理。
在数学和计算机科学中,递归指由一种(或多种)简单的基本情况定义的一类对象或方法,并规定其他所有情况都能被还原为其基本情况。
递推公式
如果数列{an}的第n项与它前一项或几项的关系可以用一个式子来表示,那么这个公式叫做这个数列的递推公式。
由递推公式写出数列的方法:
1,根据递推公式写出数列的前几项,依次代入计算即可
2,若知道的是末项,通常将所给公式整理成用后面的项表示前面的项的形式。
递归数列特征方程的推导过程
a(n+2)=p*a(n+1)+q*an
其特征方程为x^2-p*x-q=0
i.若其有两个不相等的根(称作特征根)α、β
则an=A*α^n+B*β^n
其中常数A、B的值由初始值a1、a2的值确定.
ii.若其有两个相等的根α
则an=(A*n+B)*α^n
其中常数A、B的值由初始值a1、a2的值确定.
最终可得:
当{an}有两个不等的特征根为根α,β时
由
a(n+2)-α*a(n+1)=β^(n-1)*(a2-α*a1)
a(n+2)-β*a(n+1)=α^(n-1)*(a2-β*a1)
得
an=((a2-β*a1)/(α-β))*α^(n-1)-((a2-β*a1)/(α-β))*β^(n-1)
或由
A*α+B*β=a1
A*α^2+B*β^2=a2
可得
A=(a2-β*a1)/(α^2-α*β)
B=(a2-β*a1)/(β^2-α*β)
得
an=((a2-β*a1)/(α-β))*α^(n-1)+((a2-β*a1)/(β-α))*β^(n-1)
当特征根为重根α时
由
an-α*a(n-1)=α^(n-2)*(a2-α*a1)
α*a(n-1)-α^2*a(n-2)=α^(n-2)*(a2-α*a1)
…
α^(n-2)*a2-α^(n-1)*a1=α^(n-2)*(a2-α*a1)
an-α^(n-1)*a1=(n-1)*α^(n-2)*(a2-α*a1)
得
an=((a2-a1*α)*n+2*a1*α-a2)*α^(n-2)
或由
(A+B)*α=a1
(2*A+B)*α^2=a2
可得
A=(a2-a1*α)/(α^2)
A=(2*a1*α-a2)/(α^2)
得
((a2-a1*α)*n+2*a1*α-a2)*α^(n-2)
由于
α+β=A
α*β=-B
由韦达定理,可构造一元二次方程
x^2-p*x-q=0
此即为二阶常系数齐次线性递推数列
a(n+2)=p*a(n+1)+q*an
的特徵方程
特殊的,当二阶常系数齐次线性递推数列
a(n+2)=p*a(n+1)+q*an
的特徵根为重根α=1时
即p=2,q=-1
a(n+2)=2*a(n+1)-an
此时,二阶常系数齐次线性递推数列
a(n+2)=2*a(n+1)-an
为等差数列
什么是递归数列?
递归数列
是一种用归纳方法给定的数列。
例如,等比数列可以用归纳方法来定义,先定义***项
a1
的值(
a1
≠
),对
于以后的项
,用递推公式an+1=qan
(q≠0,n=1,2,…)给出定义。
一般地,递归数列的前k项a1,a2,…,ak为已知数,从第k+1项起,由某一递推公式an+k=f(an,an+1,…,an+k-1)
(
n=1,2,…)所确定。k称为递归数列的阶数。例如
,已知
a1=1,a2=1,其余各项由公式an+1=an+an-1(n=2,3,…)给定的数列是二阶递归数列。这是斐波那契数列,各项依次为
1
,1
,2
,3,5
,8
,13
,21
,…,同样
,由递归式an+1-an
=an-an-1(
a1,a2
为已知,n=2,3,…
)
给定的数列,也是二阶递归数列,这是等差数列。
递推数列和递归数列有啥区别
递推=iterative;递归=recursive
递归指自我调用的函数;递推指重复进行的过程,这个重复的过程可以是,有自我调用的函数的重复的自我调用,也可以是其它过程。
关于递归数列和递归数列求斐波那契数列的介绍到此就结束了,不知道你从中找到你需要的信息了吗 ?如果你还想了解更多这方面的信息,记得收藏关注本站。