顺推法编程

A. 背包问题的算法

3.2 背包问题
背包问题有三种

1.部分背包问题

一个旅行者有一个最多能用m公斤的背包，现在有n种物品，它们的总重量分别是W1，W2，...,Wn,它们的总价值分别为C1,C2,...,Cn.求旅行者能获得最大总价值。

解决问题的方法是贪心算法:将C1/W1,C2/W2,...Cn/Wn,从大到小排序,不停地选择价值与重量比最大的放人背包直到放满为止.

2.0/1背包

一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。

<1>分析说明:

显然这个题可用深度优先方法对每件物品进行枚举(选或不选用0,1控制).

程序简单,但是当n的值很大的时候不能满足时间要求，时间复杂度为O（2n）。按递归的思想我们可以把问题分解为子问题,使用递归函数

设 f(i，x)表示前i件物品，总重量不超过x的最优价值

则 f（i，x）=max(f(i－1，x-W[i])+C[i]，f（i－1，x））

f（n，m）即为最优解，边界条件为f（0，x）＝0 ，f(i,0)=0;

动态规划方法(顺推法)程序如下:

程序如下：

program knapsack02;
const maxm=200;maxn=30;
type ar=array[1..maxn] of integer;
var m,n,j,i:integer;
c,w:ar;
f:array[0..maxn,0..maxm] of integer;
function max(x,y:integer):integer;
begin
if x>y then max:=x else max:=y;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
for i:=1 to m do f(0,i):=0;
for i:=1 to n do f(i,0):=0;

for i:=1 to n do
for j:=1 to m do
begin
if j>=w[i] then f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])
else f[i,j]:=f[i-1,j];
end;
writeln(f[n,m]);
end.

使用二维数组存储各子问题时方便，但当maxm较大时如maxn=2000时不能定义二维数组f,怎么办,其实可以用一维数组,但是上述中j:=1 to m 要改为j:=m downto 1,为什么?请大家自己解决。

3.完全背包问题

一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn,

每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多.

求旅行者能获得的最大总价值。

本问题的数学模型如下：

设 f(x)表示重量不超过x公斤的最大价值，

则 f(x）=max{f(x-w[i])+c[i]} 当x>=w[i] 1<=i<=n

程序如下:（顺推法）

program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
f:array[0..maxm] of integer;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
f(0):=0;
for i:=1 to m do
for j:=1 to n do
begin
if i>=w[j] then t:=f[i-w[j]]+c[j];
if t>f[i] then f[i]:=t
end;
writeln(f[m]);
end.

B. 在C语言中，什么是迭代法

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法，即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法（Iterative Method）。

一般可以做如下定义：对于给定的线性方程组x=Bx+f（这里的x、B、f同为矩阵，任意线性方程组都可以变换成此形式），用公式x(k+1）=Bx(k)+f（括号中为上标，代表迭代k次得到的x，初始时k=0)逐步带入求近似解的方法称为迭代法（或称一阶定常迭代法）。如果k趋向无穷大时limx（k）存在，记为x*，称此迭代法收敛。显然x*就是此方程组的解，否则称为迭代法发散。

跟迭代法相对应的是直接法（或者称为一次解法），即一次性的快速解决问题，例如通过开方解决方程x +3= 4。一般如果可能，直接解法总是优先考虑的。但当遇到复杂问题时，特别是在未知量很多，方程为非线性时，我们无法找到直接解法（例如五次以及更高次的代数方程没有解析解，参见阿贝耳定理），这时候或许可以通过迭代法寻求方程（组）的近似解。

最常见的迭代法是牛顿法。其他还包括最速下降法、共轭迭代法、变尺度迭代法、最小二乘法、线性规划、非线性规划、单纯型法、惩罚函数法、斜率投影法、遗传算法、模拟退火等等。

利用迭代算法解决问题，需要做好以下三个方面的工作：
确定迭代变量
在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。
建立迭代关系式
所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以顺推或倒推的方法来完成。
对迭代过程进行控制
在
什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数
是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需
要进一步分析出用来结束迭代过程的条件。
举例
例 1 ：一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，问到第 12 个月时，该饲养场共有兔子多少只？

分析：这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为 u 1 ，第 2 个月时兔子的只数为 u 2 ，第 3 个月时兔子的只数为 u 3 ，……根据题意，“这种兔子从出生的下一个月开始，每月新生一只兔子”，则有

u 1 = 1 ， u 2 = u 1 + u 1 × 1 = 2 ， u 3 = u 2 + u 2 × 1 = 4 ，……

根据这个规律，可以归纳出下面的递推公式：

u n = u(n － 1）× 2 (n ≥ 2）

对应 u n 和 u(n － 1），定义两个迭代变量 y 和 x ，可将上面的递推公式转换成如下迭代关系：

y=x*2

x=y

让计算机对这个迭代关系重复执行 11 次，就可以算出第 12 个月时的兔子数。参考程序如下：

cls

x=1

for i=2 to 12

y=x*2

x=y

next i

print y

end

例 2 ：阿米巴用简单分裂的方式繁殖，它每分裂一次要用 3 分钟。将若干个阿米巴放在一个盛满营养参液的容器内， 45 分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴 220,220个。试问，开始的时候往容器内放了多少个阿米巴？请编程序算出。

分析：根据题意，阿米巴每 3 分钟分裂一次，那么从开始的时候将阿米巴放入容器里面，到 45
分钟后充满容器，需要分裂 45/3=15 次。而“容器最多可以装阿米巴2^ 20 个”，即阿米巴分裂 15 次以后得到的个数是
2^20。题目要求我们计算分裂之前的阿米巴数，不妨使用倒推的方法，从第 15 次分裂之后的 2^20 个，倒推出第 15 次分裂之前（即第 14
次分裂之后）的个数，再进一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的个数。

设第 1 次分裂之前的个数为 x 0 、第 1 次分裂之后的个数为 x 1 、第 2 次分裂之后的个数为 x 2 、……第 15 次分裂之后的个数为 x 15 ，则有

x 14 =x 15 /2 、 x 13 =x 14 /2 、…… x n-1 =x n /2 (n ≥ 1）

因为第 15 次分裂之后的个数 x 15 是已知的，如果定义迭代变量为 x ，则可以将上面的倒推公式转换成如下的迭代公式：

x=x/2 （x 的初值为第 15 次分裂之后的个数 2^20）

让这个迭代公式重复执行 15 次，就可以倒推出第 1 次分裂之前的阿米巴个数。因为所需的迭代次数是个确定的值，我们可以使用一个固定次数的循环来实现对迭代过程的控制。参考程序如下：

cls

x=2^20

for i=1 to 15

x=x/2

next i

print x

end

ps:java中幂的算法是Math.pow（2,20）；返回double，稍微注意一下

例 3 ：验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象：对于任意一个自然数 n ，若 n 为偶数，则将其除以 2 ；若 n 为奇数，则将其乘以 3 ，然后再加 1。如此经过有限次运算后，总可以得到自然数 1。人们把谷角静夫的这一发现叫做“谷角猜想”。

要求：编写一个程序，由键盘输入一个自然数 n ，把 n 经过有限次运算后，最终变成自然数 1 的全过程打印出来。

分析：定义迭代变量为 n ，按照谷角猜想的内容，可以得到两种情况下的迭代关系式：当 n 为偶数时， n=n/2 ；当 n 为奇数时， n=n*3+1。用 QBASIC 语言把它描述出来就是：

if n 为偶数 then

n=n/2

else

n=n*3+1

end if

这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次，才能使迭代变量 n 最终变成自然数 1
，这是我们无法计算出来的。因此，还需进一步确定用来结束迭代过程的条件。仔细分析题目要求，不难看出，对任意给定的一个自然数 n
，只要经过有限次运算后，能够得到自然数 1 ，就已经完成了验证工作。因此，用来结束迭代过程的条件可以定义为：n=1。参考程序如下：

cls

input "Please input n=";n

do until n=1

if n mod 2=0 then

rem 如果 n 为偶数，则调用迭代公式 n=n/2

n=n/2

print "—";n;

else

n=n*3+1

print "—";n;

end if

loop

end

迭代法开平方：

#include<stdio.h>

#include<math.h>

void main()

{

double a,x0,x1;

printf("Input a:\n");

scanf("%lf",&a);//为什么在VC6.0中不能写成“scanf("%f",&a）；”？

if(a<0)

printf("Error!\n");

else

{

x0=a/2;

x1=(x0+a/x0)/2;

do

{

x0=x1;

x1=(x0+a/x0)/2;

}while(fabs(x0-x1）>=1e-6）；

}

printf("Result:\n");

printf("sqrt(%g)=%g\n",a,x1）；

}

求平方根的迭代公式：x1=1/2*(x0+a/x0）。

算法：1.先自定一个初值x0，作为a的平方根值，在我们的程序中取a/2作为a的初值；利用迭代公式求出一个x1。此值与真正的a的平方根值相比，误差很大。

⒉把新求得的x1代入x0中，准备用此新的x0再去求出一个新的x1.

⒊利用迭代公式再求出一个新的x1的值，也就是用新的x0又求出一个新的平方根值x1，此值将更趋近于真正的平方根值。

⒋比较前后两次求得的平方根值x0和x1，如果它们的差值小于我们指定的值，即达到我们要求的精度，则认为x1就是a的平方根值，去执行步骤5；否则执行步骤2，即循环进行迭代。

迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x），然后按以下步骤执行：

⑴ 选一个方程的近似根，赋给变量x0；

⑵ 将x0的值保存于变量x1，然后计算g(x1），并将结果存于变量x0；

⑶ 当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤⑵的计算。

若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为：

【算法】迭代法求方程的根

{ x0=初始近似根；

do {

x1=x0；

x0=g(x1）； /*按特定的方程计算新的近似根*/

} while (fabs(x0-x1）>Epsilon）；

printf（“方程的近似根是%f\n”，x0）；

}

迭代算法也常用于求方程组的根，令

X=（x0，x1，…，xn-1）

设方程组为：

xi=gi(X) (I=0，1，…，n-1）

则求方程组根的迭代算法可描述如下：

【算法】迭代法求方程组的根

{ for (i=0;i

x=初始近似根；

do {

for (i=0;i

y=x;

for (i=0;i

x=gi(X);

for (delta=0.0,i=0;i

if (fabs(y-x)>delta) delta=fabs(y-x）；

} while (delta>Epsilon）；

for (i=0;i

printf（“变量x[%d]的近似根是 %f”，I，x）；

printf（“\n”）；

}

具体使用迭代法求根时应注意以下两种可能发生的情况：

⑴ 如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制；

⑵ 方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败。

递归

递归是设计和描述算法的一种有力的工具，由于它在复杂算法的描述中被经常采用，为此在进一步介绍其他算法设计方法之前先讨论它。

能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。

【问题】 编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）。

斐波那契数列为：0、1、1、2、3、……，即：

fib(0)=0;

fib⑴=1;

fib(n)=fib(n-1）+fib(n-2） （当n>1时）。

写成递归函数有：

int fib(int n)

{ if (n==0) return 0;

if (n==1） return 1;

if (n>1） return fib(n-1）+fib(n-2）；

}

递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问
题（规模小于n）的求解。例如上例中，求解fib(n），把它推到求解fib(n-1）和fib(n-2）。也就是说，为计算fib(n），必须先计算
fib(n-1）和fib(n-
2），而计算fib(n-1）和fib(n-2），又必须先计算fib(n-3）和fib(n-4）。依次类推，直至计算fib⑴和fib(0），分别能
立即得到结果1和0。在递推阶段，必须要有终止递归的情况。例如在函数fib中，当n为1和0的情况。

在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如得到fib⑴和fib(0）后，返回得到fib⑵的结果，……，在得到了fib(n-1）和fib(n-2）的结果后，返回得到fib(n）的结果。

在编写递归函数时要注意，函数中的局部变量和参数知识局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各有自己的参数和局部变量。

由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n）应采用递推算法，即从斐波那契数列的前两项出发，逐次由前两项计算出下一项，直至计算出要求的第n项。

【问题】 组合问题

问题描述：找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5，r=3的所有组合为：⑴5、4、3 ⑵5、4、2 ⑶5、4、1

⑷5、3、2 ⑸5、3、1 ⑹5、2、1

⑺4、3、2 ⑻4、3、1 ⑼4、2、1

⑽3、2、1

分析所列的10个组合，可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int
m,int
k）为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时，其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m
个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[
]存放求出的组合的数字，约定函数将确定的k个数字组合的第一个数字放在a[k]中，当一个组合求出后，才将a[
]中的一个组合输出。第一个数可以是m、m-1、……、k，函数将确定组合的第一个数字放入数组后，有两种可能的选择，因还未去顶组合的其余元素，继续递
归去确定；或因已确定了组合的全部元素，输出这个组合。细节见以下程序中的函数comb。

【程序】

# include

# define MAXN 100

int a[MAXN];

void comb(int m,int k)

{ int i,j;

for (i=m;i>=k;i--)

{ a[k]=i;

if (k>1）

comb(i-1,k-1）；

else

{ for (j=a[0];j>0;j--)

printf（“%4d”，a[j]);

printf（“\n”）；

}

}

}

void main()

{ a[0]=3;

comb（5,3）；

}

【问题】 背包问题

问题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。

设n
件物品的重量分别为w0、w1、…、wn-1，物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案，并
保留了其中总价值最大的方案于数组option[ ]，该方案的总价值存于变量maxv。当前正在考察新方案，其物品选择情况保存于数组cop[
]。假定当前方案已考虑了前i-1件物品，现在要考虑第i件物品；当前方案已包含的物品的重量之和为tw；至此，若其余物品都选择是可能的话，本方案能达
到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时，继续考察当前方案变成无意义的工作，应终止
当前方案，立即去考察下一个方案。因为当方案的总价值不比maxv大时，该方案不会被再考察，这同时保证函数后找到的方案一定会比前面的方案更好。

对于第i件物品的选择考虑有两种可能：

⑴ 考虑物品i被选择，这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后，继续递归去考虑其余物品的选择。

⑵ 考虑物品i不被选择，这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。

按以上思想写出递归算法如下：

try（物品i，当前选择已达到的重量和，本方案可能达到的总价值tv)

{ /*考虑物品i包含在当前方案中的可能性*/

if（包含物品i是可以接受的）

{ 将物品i包含在当前方案中；

if (i

try(i+1,tw+物品i的重量，tv);

else

/*又一个完整方案，因为它比前面的方案好，以它作为最佳方案*/

以当前方案作为临时最佳方案保存；

恢复物品i不包含状态；

}

/*考虑物品i不包含在当前方案中的可能性*/

if （不包含物品i仅是可男考虑的）

if (i

try(i+1,tw,tv-物品i的价值）；

else

/*又一个完整方案，因它比前面的方案好，以它作为最佳方案*/

以当前方案作为临时最佳方案保存；

}

为了理解上述算法，特举以下实例。设有4件物品，它们的重量和价值见表：

物品 0 1 2 3

重量 5 3 2 1

价值 4 4 3 1

并设限制重量为7。则按以上算法，下图表示找解过程。由图知，一旦找到一个解，算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解，算法不会在该分支继续查找，而是立即终止该分支，并去考察下一个分支。

按上述算法编写函数和程序如下：

【程序】

# include

# define N 100

double limitW,totV,maxV;

int option[N],cop[N];

struct { double weight;

double value;

}a[N];

int n;

void find(int i,double tw,double tv)

{ int k;

/*考虑物品i包含在当前方案中的可能性*/

if (tw+a.weight<=limitW)

{ cop=1;

if (i

else

{ for (k=0;k

option[k]=cop[k];

maxv=tv;

}

cop=0;

}

/*考虑物品i不包含在当前方案中的可能性*/

if (tv-a.value>maxV)

if (i

else

{ for (k=0;k

option[k]=cop[k];

maxv=tv-a.value;

}

}

void main()

{ int k;

double w,v;

printf（“输入物品种数\n”）；

scanf（（“%d”，&n);

printf（“输入各物品的重量和价值\n”）；

for (totv=0.0,k=0;k

{ scanf（“%1f%1f”，&w,&v);

a[k].weight=w;

a[k].value=v;

totV+=V;

}

printf（“输入限制重量\n”）；

scanf（“%1f”，&limitV);

maxv=0.0;

for (k=0;k find(0,0.0,totV);

for (k=0;k

if (option[k]) printf（“%4d”，k+1）；

printf（“\n总价值为%.2f\n”，maxv);

}

作为对比，下面以同样的解题思想，考虑非递归的程序解。为了提高找解速度，程序不是简单地逐一生成所有候选解，而是
从每个物品对候选解的影响来形成值得进一步考虑的候选解，一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况：当该物品被包含在候选
解中依旧满足解的总重量的限制，该物品被包含在候选解中是应该继续考虑的；反之，该物品不应该包括在当前正在形成的候选解中。同样地，仅当物品不被包括在
候选解中，还是有可能找到比目前临时最佳解更好的候选解时，才去考虑该物品不被包括在候选解中；反之，该物品不包括在当前候选解中的方案也不应继续考虑。
对于任一值得继续考虑的方案，程序就去进一步考虑下一个物品。

【程序】

# include

# define N 100

double limitW;

int cop[N];

struct ele { double weight;

double value;

} a[N];

int k,n;

struct { int ;

double tw;

double tv;

}twv[N];

void next(int i,double tw,double tv)

{ twv.=1;

twv tw=tw;

twv tv=tv;

}

double find(struct ele *a,int n)

{ int i,k,f;

double maxv,tw,tv,totv;

maxv=0;

for (totv=0.0,k=0;k

totv+=a[k].value;

next(0,0.0,totv);

i=0;

While (i>=0)

{ f=twv.;

tw=twv tw;

tv=twv tv;

switch(f)

{ case 1: twv.++;

if (tw+a.weight<=limitW)

if (i

{ next(i+1,tw+a.weight,tv);

i++;

}

else

{ maxv=tv;

for (k=0;k

cop[k]=twv[k].!=0;

}

break;

case 0: i--;

break;

default: twv.=0;

if (tv-a.value>maxv)

if (i

{ next(i+1,tw,tv-a.value);

i++;

}

else

{ maxv=tv-a.value;

for (k=0;k

cop[k]=twv[k].!=0;

}

break;

}

}

return maxv;

}

void main()

{ double maxv;

printf（“输入物品种数\n”）；

scanf（（“%d”，&n);

printf（“输入限制重量\n”）；

scanf（“%1f”，&limitW);

printf（“输入各物品的重量和价值\n”）；

for (k=0;k

scanf（“%1f%1f”，&a[k].weight,&a[k].value);

maxv=find(a,n);

printf（“\n选中的物品为\n”）；

for (k=0;k

if (option[k]) printf（“%4d”，k+1）；

printf（“\n总价值为%.2f\n”，maxv);

}

C. 运筹学动态规划关于最短路问题用逆推法和顺推法差不多吧，用逆推法要写很多…

差不多的，就好像是对换了起点和终点。最短路的问题用dijkstra算法是最简单的！动态规划解决资源分配和背包问题用逆推法！

D. pascal取数游戏（递推） 递推是什么意思如何用递推公式编程

别听他的废话，任何循环都可以是递推，如输入n，求1+2+3+4+5+……+n
var
i,n,sum:longint;
begin
sum:=0;
readln(n);
for i:=1 to n do
inc(sum,i);
write(sum);
readln
end;
这就是一个递推，也就是说for i:=a to b都是递推
至于你说的取数游戏，似乎是用递推算法来解这道题

E. 递推算法是怎么回事

递推定义
递推算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。

递推算法分为顺推和逆推两种。

顺推法
所谓顺推法是从已知条件出发，逐步推算出要解决的问题的方法叫顺推。

如斐波拉契数列，设它的函数为f(n),已知f(1)=1，f(2)=1;f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。则我们通过顺推可以知道,f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3……直至我们要求的解。

逆推法
所谓逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为逆推。

递推与递归的比较
相对于递归算法,递推算法免除了数据进出栈的过程，也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值.

比如阶乘函数：f(n)=n*f(n-1)

在f(3)的运算过程中,递归的数据流动过程如下:

f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}

而递推如下:

f(0)-->f(1)-->f(2)-->f(3)

由此可见,递推的效率要高一些,在可能的情况下应尽量使用递推.但是递归作为比较基础的算法,它的作用不能忽视.所以,在把握这两种算法的时候应该特别注意.

F. 我是PASCAL的菜鸟，动态规划学的一塌糊涂，希望各位大侠指导一下动规要怎么做

1.1 多阶段决策过程的最优化问题
1、问题的提出

首先，例举一个典型的且很直观的多阶段决策问题:
[例] 下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A->E。求A->E的最省费用。

如图从A到E共分为4个阶段，即第一阶段从A到B，第二阶段从B到C，第三阶段从C到D，第四阶段从D到E。除起点A和终点E外，其它各点既是上一阶段的终点又是下一阶段的起点。例如从A到B的第一阶段中，A为起点，终点有B1，B2，B3三个，因而这时走的路线有三个选择，一是走到B1，一是走到B2，一是走到B3。若选择B2的决策，B2就是第一阶段在我们决策之下的结果，它既是第一阶段路线的终点，又是第二阶段路线的始点。在第二阶段，再从B2点出发，对于B2点就有一个可供选择的终点集合(C1，C2，C3)；若选择由B2走至C2为第二阶段的决策，则C2就是第二阶段的终点，同时又是第三阶段的始点。同理递推下去，可看到各个阶段的决策不同，线路就不同。很明显，当某阶段的起点给定时，它直接影响着后面各阶段的行进路线和整个路线的长短，而后面各阶段的路线的发展不受这点以前各阶段的影响。故此问题的要求是：在各个阶段选取一个恰当的决策，使由这些决策组成的一个决策序列所决定的一条路线，其总路程最短。具体情况如下：

（1）由目标状态E向前推，可以分成四个阶段，即四个子问题。如上图所示。

（2）策略：每个阶段到E的最省费用为本阶段的决策路径。

（3）D1，D2是第一次输人的结点。他们到E都只有一种费用，在D1框上面标5，D2框上面标2。目前无法定下，那一个点将在全程最优策略的路径上。第二阶段计算中，5，2都应分别参加计算。
（4）C1，C2，C3是第二次输入结点，他们到D1，D2各有两种费用。此时应计算C1，C2，C3分别到E的最少费用。
C1的决策路径是 min{（C1D1），（C1D2）}。计算结果是C1+D1+E，在C1框上面标为8。
同理C2的决策路径计算结果是C2+D2+E，在C2框上面标为7。
同理C3的决策路径计算结果是C3+D2+E，在C3框上面标为12。
此时也无法定下第一，二阶段的城市那二个将在整体的最优决策路径上。
（5）第三次输入结点为B1，B2，B3，而决策输出结点可能为C1，C2，C3。仿前计算可得Bl，B2，B3的决策路径为如下情况。
Bl:B1C1费用 12+8=20， 路径:B1+C1+D1+E
B2:B2C1费用 6+8=14， 路径:B2+C1+D1+E
B3:B2C2费用 12+7=19， 路径:B3+C2+D2+E
此时也无法定下第一，二，三阶段的城市那三个将在整体的最优决策路径上。
（6）第四次输入结点为A，决策输出结点可能为B1，B2，B3。同理可得决策路径为
A：AB2，费用5+14=19，路径 A+B2+C1+D1+E。
此时才正式确定每个子问题的结点中，那一个结点将在最优费用的路径上。19将结果显然这种计算方法，符合最优原理。子问题的决策中，只对同一城市（结点）比较优劣。而同一阶段的城市（结点）的优劣要由下一个阶段去决定。
1.2 动态规划的概念
在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。

与穷举法相比，动态规划的方法有两个明显的优点:
(1)大大减少了计算量
(2)丰富了计算结果
从上例的求解结果中，我们不仅得到由A点出发到终点E的最短路线及最短距离，而且还得到了从所有各中间点到终点的最短路线及最短距离，这对许多实际问题来讲是很有用的。

动态规划的最优化概念是在一定条件下，我到一种途径，在对各阶段的效益经过按问题具体性质所确定的运算以后，使得全过程的总效益达到最优。
应用动态规划要注意阶段的划分是关键，必须依据题意分析，寻求合理的划分阶段(子问题)方法。而每个子问题是一个比原问题简单得多的优化问题。而且每个子问题的求解中，均利用它的一个后部子问题的最优化结果，直到最后一个子问题所得最优解，它就是原问题的最优解。
1.3 动态规划适合解决什么样的问题
准确地说，动态规划不是万能的，它只适于解决一定条件的最优策略问题。
或许，大家听到这个结论会很失望：其实，这个结论并没有削减动态规划的光辉，因为属于上面范围内的问题极多，还有许多看似不是这个范围中的问题都可以转化成这类问题。
上面所说的“满足一定条件”主要指下面两点：
(1)状态必须满足最优化原理；
(2)状态必须满足无后效性。
动态规划的最优化原理是无论过去的状态和决策如何，对前面的决策所形成的当前状态而言，余下的诸决策必须构成最优策略。 可以通俗地理解为子问题的局部最优将导致整个问题的全局最优在上例中例题1最短路径问题中，A到E的最优路径上的任一点到终点E的路径也必然是该点到终点E的一条最优路径，满足最优化原理。

动态规划的无后效性原则某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶段之后，阶段 I 中的状态只能由阶段 I+1 中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系，这就是无后效性。

1.1 多阶段决策过程的最优化问题
1、问题的提出

首先，例举一个典型的且很直观的多阶段决策问题:
[例] 下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A->E。求A->E的最省费用。

2.1 为什么要用动态规划法解题
首先，看下面一个问题:

【例题1】数字三角形问题。

7

3 8

8 1 0

2 7 7 4

5 5 2 6 5

示出了一个数字三角形宝塔。数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。假设三角形行数≤100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值。输人数据：由文件输入数据，文件第一行是三角形的行数N。以后的N行分别是从最顶层到最底层的每一层中的数字。
如输入： 5
7
3 8
8 1 0
2 7 7 4
4 5 2 6 5
输出：30
【分析】对于这一问题，很容易想到用枚举的方法（深度搜索法）去解决，即列举出所有路径并记录每一条路径所经过的数字总和。然后寻找最大的数字总和，这一想法很直观，很容易编程实现其程序如下：

program sjx;
const maxn=10;
var
a:array[1..maxn,1..maxn] of integer;
max:longint;
n,i,j:integer;
fname:string;

inputf:text;

procere try(x,y,dep:integer;sum:longint);
begin
if (dep=n) then
begin
if sum>max then max:=sum;
exit
end;
try(x+1,y,dep+1,sum+a[x+1,y]);
try(x+1,y+1,dep+1,sum+a[x+1,y+1]);
end;
begin
readln(fname);

assign(inputf,fname);

reset(inputf);

readln(inputf,n);
for i:=1 to n do
for j:= 1 to i do
read(inputf,a[i,j]);
max:=0;
try(1,1,1,a[1,1]);
writeln(max);
end.

但是当行数很大时，当三角形的行数等于100时，其枚举量之大是可想而知的，用枚举法肯定超时，甚至根本不能得到计算结果，必须用动态规划法来解。
2.2 怎样用动态规划法解题
1.逆推法:

按三角形的行划分阶段，若行数为 n，则可把问题看做一个n-1个阶段的决策问题。先求出第n-1阶段(第n-1行上各点)到第n行的的最大和，再依次求出第n-2阶段、第n-3阶段……第1阶段(起始点)各决策点至第n行的最佳路径。
设：f[i,j]为从第i阶段中的点j至第n行的最大的数字和；
则: f[n,j]=a[n,j] 1<=j<=n

f[i,j]=max{a[i,j]+f[i+1,j],a[i,j]+f[i+1,j+1]} 1<=j<=i.

f[1,1]即为所求。

程序如下：

program datasjx;
const maxn=100;
var
fname:string;
inputf:text;
n,i,j:integer;
a:array[1..maxn,1..maxn] of integer;
f:array[1..maxn,1..maxn] of integer;
begin
readln(fname);
assign(inputf,fname);
reset(inputf);
readln(inputf,n);
for i:=1 to n do
for j:=1 to i do
read(inputf,a[i,j]);
for i:=1 to n do
f[n,i]:=a[n,i];
for i:=n-1 downto 1 do
for j:=1 to i do
if f[i+1,j]>f[i+1,j+1] then f[i,j]:=a[i,j]+f[i+1,j]
else f[i,j]:=a[i,j]+f[i+1,j+1];
writeln(f[1,1]);
end.

2. 顺推法

按三角形的行划分阶段，若行数为 n，则可把问题看做一个n-1个阶段的决策问题。先求第2行各元素到起点的最大和

,再依次求出第3,4，5,......,.n-1,n到起点的最大和,最后找第n行的最大值

设f[i,j]为 第i行第j列上点到起点的最大和

则 f[1，1]=a[1,1];

f[i，1]=a[i, 1]+f[i-1,1];

f[ i，j ]=max{ a[i,j]+f[i-1,j-1],a[i,j]+f[i-1,j]} 2<=j<=i

max(f[n,1],f[n,2],.......,f[n,n]}即为所求。

程序如下：

program datasjx;
const maxn=100;
var
fname:string;
inputf:text;
n,i,j:integer;
a:array[1..maxn,1..maxn] of integer;
f:array[1..maxn,1..maxn] of integer;
maxsum:integer;
begin
readln(fname);
assign(inputf,fname);
reset(inputf);
readln(inputf,n);
for i:=1 to n do
for j:=1 to i do
read(inputf,a[i,j]);
fillchar(f,sizeof(f),0);

f[1,1]:=a[1,1];
for i:=2 to n do
begin
f[i,1]:=a[i,1]+f[i-1,1];
for j:=2 to i do
if f[i-1,j-1]>f[i-1,j] then f[i,j]:=a[i,j]+f[i-1,j-1]
else f[i,j]:=a[i,j]+f[i-1,j];
end;
maxsum:=0;
for i:=1 to n do
if f[n,i]>maxsum then maxsum:=f[n,i];
writeln(maxsum);
end.

说明一下：

1.用动态规划解题主要思想是用空间换时间.

2.本题如果n较大，用2维数组空间可能不够,可以使用1维数组.

程序如下:

program datasjx;
const maxn=100;
var
fname:string;
inputf:text;
n,i,j:integer;
a:array[1..maxn,1..maxn] of integer;
f:array[1..maxn] of integer;
maxsum:integer;
begin
readln(fname);
assign(inputf,fname);
reset(inputf);
readln(inputf,n);
for i:=1 to n do
for j:=1 to i do
read(inputf,a[i,j]);
fillchar(f,sizeof(f),0);
f[1]:=a[1,1];
for i:=2 to n do
begin
for j:=i downto 2 do
if f[j-1]>f[j] then f[j]:=a[i,j]+f[j-1]
else f[j]:=a[i,j]+f[j];
f[1]:=a[i,1]+f[1];
end;
maxsum:=0;
for i:=1 to n do
if f[i]>maxsum then maxsum:=f[i];
writeln(maxsum);
end.

练习:用一维数组和逆推法解本题.

2.3 用动态规划法解题的一般模式

动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。
┌———┐┌———┐┌———┐
初始状态→│决策1│→│决策2│→…→│决策n│→结束状态
└———┘└———┘└———┘
(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两段各状态之间的关系来确定决策。
(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
(5)程序设计实现：动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。
根据上述动态规划设计的步骤，可得到大体解题框架如下:

1.初始化(边界条件)

2.for i:=2 to n (顺推法) 或 for i:=n-1 to 1(逆推法)

对i阶段的每一个决策点求局部最优

3.确定和输出结束状态的值.

G. 1加2等于25,2加3等于36,3加4等于47,4加5等于多少

4加5等于58。

1+2＝25

2+3＝36

3+4＝47

每一项都是比前一项多11，也就是1+2＝3＝25，2+3＝5＝36，3+4=47，也就是说36比25多11，47比36多11，由此得出4+5=58。

顺推法是从已知条件出发，逐步推算出要解决的问题的方法叫顺推。

如斐波拉契数列，设它的函数为f(n),已知f(1)=1，f(2)=1;f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。则我们通过顺推可以知道,f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3……直至我们要求的解。

逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为逆推。

(7)顺推法编程扩展阅读

编程语言中，函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。递归函数不能定义为内联函数。

在数学上，关于递归函数的定义如下：对于某一函数f(x)，其定义域是集合A，那么若对于A集合中的某一个值X0，其函数值f(x0)由f(f(x0))决定，那么就称f(x)为递归函数。

一个含直接或间接调用本函数语句的函数被称之为递归函数，在上面的例子中能够看出，它必须满足以下两个条件：

1） 在每一次调用自己时，必须是（在某种意义上）更接近于解；

2） 必须有一个终止处理或计算的准则。

H. 定量背包PASCAL

如果K是未指定的，
f(m,volume) = 0 m=0时
f(m,volume) = f(m-1,volume) volume-vol[m]<0时
f(m,volume)
= max { value[m]+f(m-1,volume-vol[m]) , f(m-1,volume) }
f(m,volume)指从编号为1到m的物品中选取总体积不超过volume的物品所能达到的最大价值。
f(N,V)即为所求。

如果K是指定的，
f(m,L,volume)
= max { value[m]+f(m-1,L-1,volume-vol[m]) , f(m-1,L，volume)}
f(m,L,volume) = 0 l=0或m<l时
f(m,L,volume) = f(m-1,L，volume) volume-vol[m]<0时
f(m,L,volume)指从编号为1到m的物品中选取总体积不超过volume的L个物品所能达到的最大价值。
f(N,K,V)即为所求。
至于记录选取物品情况，可以用字符串或数组记录。如N=8，现在从1到6中选，如果选取6，从1到5中选取的结果是00001010，不选6，从1到5中选取的结果是00010011，那么就看00101010（第6位置1）和00010011哪个的价值大，便把所求的f和相应的串作为返回值。
有很多地方重复计算了，可以优化剪枝，不过程序就会比较复杂了。

补充：

我说的K未指定时的方法实际上就是6楼所用到的方法，从编号为1到i的物品中取出总体积不超过t的物品使得总价值最大，无非分两种情形，一种是不取物品n，从1到n-1中选取总体积不超过t的物品使价值最大；另一种是选取物品i，然后从1到i-1中选取总体积不超过t-tt[i]的物品使价值最大。这两种情况中总价值更大的那个即为所求。

本来这是要用递归来完成的，非递归方法则要用到栈，但是若每个物品的体积都是正整数的话，则可以用递推方法来完成。6楼正是用的此种方法。

二重循环中，外层循环是物品编号1到N，内层循环是体积V到0，其中i=k一个循环下来，数组b[]的每个元素b[j]中存储了从物品1到k中选取物品使得体积之和刚好为j，所能达到的最大价值，若a[j]=false，则表示无法选取物品组合使得体积之和恰好为j，此时相对应的b[j]=0。

例如物品5的体积为tt[5]=8，价值为w[5]=13，i=4循环结束时，b[8]=0，b[28]=46，b[29]=0，b[36]=55，那么i=5循环结束后，由于a[0]=true，于是a[0+tt[5]]即a[8]=true，b[8]显然由原来的0变为15，b[28]+w[5]=59>b[28+tt[5]]=55，于是b[36]变为59，而a[29]=false，b[29]=0，因而a[37]和b[37]保持不变。最后i=N循环结束后，b[1]到b[V]z中的最大者，即为所求。

若是体积不是整数，使精确到小数点后两位的数，可以将物品体积和指定的V全部扩大100倍，化为整数问题来解决。

6楼程序里的判断语句中的(j+tt[i]<=t) 一项可以去掉，但是数组a[]、b[]的范围要重新设，因为最后j+tt[i]会达到所有N个物品的总体积。最后仍在b[1]到b[V]中去最大值，超过V的那些b[]不理。

7楼的方法则是要求价值p为正整数，外层循环仍然是物品编号，内层循环则是价值p从P到0，P为所有物品的总价值。

思路如下，从编号为1到k的物品中取出总价值不低于p的物品使得总体积最小，同样分取和不取物品k两种情形，取两种情形中体积小者。

程序实现和6楼类似，只不过b[]换成f[p]，表示从1到k中选取物品使价值之和恰好为p，所能达到的最小体积。外层最后一轮循环k=N结束后，从f[1]到f[P]中寻找小于V的那些f[p]，其中最大的那个p极为所求。

取法记录：C中可以用数组、结构、枚举来记录。比如对于6楼的方法，增设一个M[V][N]记录取法。M[35][]={1，0，1，0，0，...0，1，0}表示取第1、3、N-1个物品，这三个物品的体积之和为35，上面举例中b[8]和b[36]发生改变，于是M[8][]和M[36][]要相应改变，即M[8][5]和M[36][5]由0遍1，这里5代表第五个元素，不是按C的习惯代表第六个元素。

K指定的话方法其实是一样的，分两种情况讨论。我最早学的BASIC，后来就是C，pascal泛泛浏览过，没写过pascal程序，现在是能读不能写。只好说明大致的思路如下：

value[1]到value[N]，vol[1]到vol[N]为物品价值，体积，V为背包体积，K为要取的物品个数。

if L=0 or m<L then return 0 and return pickup=none //要取0个物品或是要取物品数大于剩余物品数当然是只有什么都不取了

if volume-vol[m]<0 then f(m,L,volume) = f(m-1,L，volume) return f and pickup //物品m体积大于剩余空间，只有考虑不取物品m，从1到m-1中取L件的情况了，pickup不变

f(m,L,volume) = max { value[m]+f(m-1,L-1,volume-vol[m]) , f(m-1,L，volume)} //以上两种情况都不成立的话，那么就分两种情况了，一是去m，从1到m-1中取L-1件，一是不取m,从1到m-1中取L件

return f and pickup //f(m-1,L，volume)大的话则pickup即为f(m-1,L，volume)返回的pickup,否则pickup为f(m-1,L-1,volume-vol[m])返回的pickup进行修改，把物品m标记为选取。

f(N.K,V)即为所求最大价值，返回的pickup为取法。

pascal程序应该是个function f()函数吧，主程序直接对value、vol、V等初始化，然后调用f(N,K,V)。由于函数进行了递归，在N增大时所要求的空间和时间会很大。如果用非递归的方法会稍好，可以用分支定界法剪枝，比如不取5，从1到4中选取的结果已经求出，而选取了5，不选4，现在从1到3中取，v不超过6.4，而前面算1到4时已经有了1到3，v不超过7.1的结果，这个结果加上5的价值都不如前面算的1到4的结果，更不用说v不超过6.4了，因此就不用继续计算1到3，v不超过6.4的结果了。不过这样将需要更多的变量保存中间结果，即搜索树上的中间结点，程序也将复杂化。

上面所有的讨论都没有考虑有多解的情形，如果取1、2、6和取2、4都是总体积58，总价值97，且为最优解，则上面的所有方法都只能得到其中一组解，如果要得到所有解，需要对保存取法的变量进行改动，通常建立一个索引即可。M[1]到M[V]可以作为V个指向链表的指针，如果v=28有三组解，可以用num[28]=3保存或是保存在M[28]指向的链表的头结点。上面所谓的a[m]为true或false也不用了，num[m]=0(此时M[m]指向null)或者M[m]指向的头结点是个单结点。其实无需记录解的数目，v=36的解变更时，自然会读取v=28的解的链表，从头读到尾。

I. 做数学题的方法

1、学数学最重要的就是解题能力

要想会做数学题目，就要有大量的练习积累，知道各类型题目的解题步骤与方法，题目做多了就有手感了，再拿出类似的题目才会有解题思路。

2、其次是学会预习

解题思路不是直接就有的，也并非通过做几道简单的题目就能轻易获得，而是在预习过程中不断积累出来的。因此，预习在数学学习过程中起到了非常重要的作用。预习一方面能够让大家提前对数学知识有所了解，另一方面能够培养数学独立学习能力。

3、学数学必须多做题

理解了数学基本定义和知识点以后，就需要通过做对应习题去巩固知识，多做多练才能更好地掌握所学知识，学数学也是看花容易绣花难的，只有真正动手去做题、经历了实操过程能学会。

4、做完题要学会总结

对于做过的题型及做错的题目要善于进行分类总结，再遇到类似的题目要会分析，知道哪里容易出现问题，然后尽量去避免。同时在做题和总结过程中，要学会举一反三，抓住考点去复习。

5、学数学要会看书和查缺补漏

数学基础考点都来源于课本，大家之所以觉得书没什么可看，是因为对教材掌握程度不够。书上的每个定义都要理解后倒背如流，深究每个词语的含义，做懂每个例题，会推导数学公式及变形公式。

做数学题目方法不唯一，只要是逻辑合理、能一步步推导出结论的方法都可以，不必拘泥于老师讲授的方法。做数学小题也可以采用画图、试值法、代入法等去做，只要沉下心去研究，功夫不负有心人，数学总能够学好。

J. 什么是递推法和递归法两者在思想上有何联系

1、递推法：递推算法是一种根据递推关系进行问题求解的方法。通过已知条件，利用特定的递推关系可以得出中间推论，直至得到问题的最终结果。递推算法分为顺推法和逆推法两种。 

2、递归法：在计算机编程中，一个函数在定义或说明中直接或间接调用自身的编程技巧称为递归。通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归做为一种算法在程序设计语言中广泛应用。 

3、两者的联系：在问题求解思想上，递推是从已知条件出发，一步步的递推出未知项，直到问题的解。从思想上讲，递归也是递推的一种，只不过它是对待解问题的递推，直到把一个复杂的问题递推为简单的易解问题。然后再一步步的返回去，从而得到原问题的解。 

(10)顺推法编程扩展阅读

相对于递归算法,递推算法免除了数据进出栈的过程，也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值。

比如阶乘函数：f(n)=n*f(n-1)  

在f(3)的运算过程中,递归的数据流动过程如下:   f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}  

而递推如下:   f(0)-->f(1)-->f(2)-->f(3)   由此可见,递推的效率要高一些,在可能的情况下应尽量使用递推。

但是递归作为比较基础的算法,它的作用不能忽视。所以,在把握这两种算法的时候应该特别注意。