记忆化搜索递推与递归

1、递推和递归1、递推的概念递推就是逐步推导的过程。先看一个简单。例 20：一个数列的第 0 项为 0，第 1 项为 1，以后每一项都是前两项的和，这个数列就是著名的数列，求数列的第 N 项。分析：可以根据数列的定义：从第 2 项开始，逐项推算，直到第 N 项。因此可以设计出如下算法：F0 := 0; F1:=1;FOR I := 2 TO NDOFI := FI1 + FI 2;从这个问题可以看出，在计算相邻两项之间的变化有一定的规律性，数列的每一项目时，都可以由前两项推出。这样，可以将这种规律归纳成如下简捷的递推关系式：Fn=g(Fn-1)，这就在数的序列中，建立起后项和前项之间的关系。然后从

2、初始条件（或是最终结果）入手，按递推关系式递推，直至求出最终结果（或初始值）。很多问题就是这样逐步求解的。对一个试题，要是能找到后一项与前一项的关系并清楚其起始条件（或最终结果），问题就可以递推了，接下来便是让计算机一步步计算了。让高速的计算机从事这种重复运算，真正起到“物尽其用”的效果。递推分倒推法和顺推法两种形式。算法流程如下：2、递归的概念1.概念满足求解初始条件 F1Y顺推N倒推由题意（或递推关系）定初始值 F1（边界条件）求出顺推关系式 Fi=g(Fi-1)；由题意（或递推关系）确定最终结果Fn；求出倒推关系式 Fi-1=g(Fi)；I=1；由边界条件 F1 出发进行顺推I=n；从最

3、终结果 Fn 出发进行倒推While 当前结果 Fi 非最终结果 Fn doWhile 当前结果 Fi 非初始值 F1 do由 Fi=g(Fi-1)顺推后项；由 Fi-1=g(Fi)倒推前项；输出顺推结果 Fn 和顺推过程；输出倒推结果 F1 和倒推过程；一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).如:procedure a; begin.a;.end;这种方式是直接调用.又如:procedure begin.c;.end;b;procedure c; begin.b;.end;这种方式是间接调用.例 1 计算n!可用递归公式如下:1（当n=0 时）fac

4、(n)=n*fac(n-1) （当 n0 时）可编写程序如下:$N+program fac2; varn:eger;function fac(n:eger):extended; beginif n=0 then fac:=1 else fac:=n*fac(n-1)end;beginwrite(n=);readln(n);wrin(fac(,n,)=,fac(n):0:0);end.例 2 楼梯有n 阶台阶,上楼可以一步上 1 阶,也可以一步上 2 阶,编一程序计算共有多少种不同的走法.设 n 阶台阶的走法数为 f(n)显然有12n=1n=2f(n)=f (n-1)+f (n-2) n2可编程

5、序如下：program louti; var n:eger;function f(x:eger):eger; beginif x=1 then f:=1 elseif x=2 then f:=2 else f:=f(x-1)+f(x-2);end; beginwrite(n=);read(n); wrin(f(,n,)=,f(n)end.2.2 如何设计递归算法1、大可以化为性质相同的规模较小2、确定递归公式3、确定边界(终了)条件专题问题：递推与递归的关系怎样？递推的优点在哪儿？递归与递推表面看来是相逆的过程，其实也是相似的，最终的计算都是从小算到大。就是递推的使用环境要求高导致了递推的高效

6、性，递推没有重复计算什么数据，保持了高效。递归大多数会重复计算子问题，导致时间浪费，所以一般不要使用过深的递归，甚至会空间溢出。但是也不能说递推好，递归差，因为递归却能解决很多递推做不到的事情，在某些特定的环境下也能实现高效，并且递归容易使用。要就事论事！对于递归和递推的效率问题，一般认为递推比递归优，举一个简单的例子:最简单的数列（Fibonacci）：对于 F（30），如果使用递归则需要运行 1664079 次，而递推只需 30 次就可以了，速度悬殊。递归：function f (n: long) : long; beginif i3 then exit(1); f : =f(i-1)+f

7、(i-2);end;递推：f0:=0; f1:=1;for i:=2 to n do beginf i+2:=f i+f i+1;end;F0F1F2F3F4F5F6F7F801123581321递推与递归（Recur）递推要求数据关系较密切，有明确的公式和单调性，也就因此用途比较狭窄，但是绝不意味这在竞赛中没有用处，下面的例子就是一个很好的例子：K 上升段问题描述：对于自然数 1.n 的一个排列 A1.N 可以划分为若干个单调递增序列。每个单调递增序列由连续元素 Ast.ed组成，且满足以下条件：1=st ,ed=n ;AiAi+1 (st=i Aed+1;例如：排列 1 2 4 5 6 3

8、 9 10 7 8 可划分为 3 个单调递增序列 1 2 3 4 5；3 9 10 ；78； 所以称这是一个 3 上升段序列 。现在给定 n 和 k , 求出 n 的全排列中的，k 上升段序列 的个数。输入格式：输入仅有 1 行，包含两个数 n, k（1 n 20, 1 k n）。输出格式：输出 n 的所有 k 上升段的个数。样例 kink.inkink.out324( 说明，符合条件的排列是，)：本题看似要用回溯或组合数学来计算，但是它却确确实实只能用递推来做!先给出递推式：f(n,k) = (n-k)f(n-1,k-1) + kf(n-1,k)形成 f(n,k)的由两部分组成：第一部分是

9、f(n-1,k-1) 变化而来，例如 1 3 2 5 4 是一种f (5,3) ,在每一个不是上升段的结尾处放上“6”都可以变成 k 个上升段，不是上升段的结尾处共有(n1)1)k= nk 个;第二部分是 f(n-1,k) 是变化而来，例如 1 3 5 4 2 是一种f (5,4) ,在每一个是上升段的结尾处放上“6”都可以保持 k 个上升段，是上升段的结尾处共有 k 个。因此就有了上面的式子，只要递推即可，注意使用高精度。K 上升段问题描述：对于自然数 1.n 的一个排列 A1.N 可以划分为若干个单调递增序列。每个单调递增序列由连续元素 Ast.ed组成，且满足以下条件：1=st ,ed=

10、n ;AiAi+1 (st=i Aed+1;例如：排列 1 2 4 5 6 3 9 10 7 8 可划分为 3 个单调递增序列 1 2 3 4 5；3 9 10 ；78； 所以称这是一个 3 上升段序列 。现在给定 n 和 k , 求出 n 的全排列中的，k 上升段序列 的个数。输入格式：输入仅有 1 行，包含两个数 n, k（1 n 20, 1 k n）。输出格式：输出 n 的所有 k 上升段的个数。样例 kink.inkink.out324( 说明，符合条件的排列是，)：本题看似要用回溯或组合数学来计算，但是它却确确实实只能用递推来做!先给出递推式：f(n,k) = (n-k)f(n-1,k-1) + kf(n-1,k)形成 f(n,k)的由两部分组成：第一部分是 f(n-1,k-1) 变化而来，例如 1 3 2 5 4 是一种f (5,3) ,在每一个不是上升段的结