|
|
|
|
|
|
递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为N的解，当N=1时，解或为已知，或能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1, 2,…, i-1的一系列解构造出问题规模为i的解。这样，程序可从i=0或i=1出发，重复地，由已知i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。
|
|
|
|
|
|
Fibonacci级数数列为0, 1, 1, 2, 3, 5, 8, 13, …, 即F（0）=0，F（1）=1，…，F（n）=F（n-1）+F（n-2）（n>1）。递推法实现算法如下：
|
|
|
|
|
|
|
|
|
|
|
|
