算法中-----递归法
算法中-----递归法
由 fulong 周五 五月 09, 2014 6:44 am
递 归 法
递归作为一种强有力的数学和算法描述工具在Pascal语言中被广泛使用。一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有定义本身的引用（在过程或自定义函数中，又包含自己调用自己），则称它们是递归的或者是递归定义的。
一个递归算法仅使用少量的程序编码就可描述出解题所需要的多次重复计算而不需要设计循环结构。使用递归求解问题，通常可以将一个比较大的问题层层转化为一个与原问题相类似的规模较小的问题来求解，进而最终导致原问题的解决。
例如：n!的定义，我们知道，在数学中n!一般定义为：
1 若n=0
n!=
n×(n-1)! 若n>0
在n>0的公式中，又包含了（n-1）!，这就是递归定义。
利用递归方法，可以用有限的语句来定义对象的无限集合。但在递归定义中，应该至少有一条是非递归的，即初始定义。如上面例子中的第一条，否则就变成了循环定义，产生逻辑性错误。
n!的递归定义的程序：
program find＿n；
var n：integer；
t：longint；
procedure find（n：integer）；
begin
if n＝0 then t：＝1
else
begin find（n-1）；
t：＝t＊n end；
end；
begin
write（'n＝'）；
readln（n）；
find（n）；
writeln（n,'!＝'，t）
end．
递归调用（n进栈）达到结束条件时（n=0，t赋初值1）就停止调用开始返回，再把保存的值取出（n出栈），使n恢复原来的值，并计算t，返回主程序，输出结果t。
3!递归是如何实现的？
（1）设n=3，开始调用过程find，称为第零层调用。
（2）由于公式3!=3 2!，必须先求2!，即程序中的f(n-1)，此时系统自动先保存n的原值3，再设n=2，进入第一层递归调用。
（3）因为2!=2 1!，所以系统又保存2，并设n=1，进入第2层调用。
（4）因为1!=1 0!，所以保存1，并设n=0，进入第3层调用。
（5）因为n=0，终止调用，t赋值1，返回4的入口点。
（6）取出执行4时保存的1，求出t=1 t=1，返回3的入口点。
（7）取出执行3时保存的2，求出t=2 t=2，返回2的入口点。
（8）取出执行2时保存的3，求出t=3 t=6，返回1的入口点。
（9）返回主程序，输出结果：t=6。
从上面分析的过程看到，由于递归调用，需用同一变量名n，但值不同，所以在调用前必须先把n的原值保存，再赋以新值，然后进入调用。调用结束后，再把保存的值取出，使n恢复原来的值。在过程中find中又包含find(n-1)，即又调用了它自己，这就是递归调用。包含有递归调用的算法，就叫做递归算法。
递归调用会产生无终止运算的可能性，因此必须在适当时候终止递归调用，即在程序中必须要有终止条件。上面程序中，过程find的第一条语句就是终止条件。一般地，根据递归定义设计的递归算法中，非递归的初始定义，就用作程序中的终止 条件。
实践证明，不是所有问题都可以用递归的方法处理，用递归算法编写的程序也不一定是好程序。可以看出，执行递归的过程既浪费时间又费存储空间，因此有的语言系统，禁止使用递归，由于计算机存储容量的限制，编译系统也不允许递归。但因递归特别符合人们的思维习惯，递归算法的设计也要比非递归算法设计容易，所以当问题是递归定义，尤其是当涉及的数据结构是递归定义的时候，使用递归算法特别合适。
应用递归算法能够求解的问题一般具有两个特点：
①存在某个特定条件，在此条件下，可得到指定的解，即递归在终止状态。
②对任意给定的条件，有明确的定义规则，可以产生新的状态并将最终导出终止状态，即存在导致问题求解的递归步骤。
递归是用栈来实现的。不过，递归恐怕不像想象得这么简单。首先，它体现了一个数学思想：化归，即把一个问题转化成另一个的方法。递归比较特殊，它是转化成性质相似，但规模更小的问题。
例3 阅读程序NOIp2001_G。
program gao7_1;
function ack(m,n:integer):integer;
begin
if m=0 then ack:=n+1
else if n=0 then ack:=ack(m-1,1)else ack:=ack(m-1,ack(m,n-1))
end;
begin writeln(ack(3,4));
readln;
end.
分析：
这个程序我们可以用下面的函数表示。在解题时，一般都是用递归的方法去实现的，而递归方法将会计算五千多步，在竞赛时这种方法是不可用的，而递归往往可以用递推去实现，因此，我们在教学过程中就讲解了该函数的递推过程，现将推导过程表示如下：
（1）我们在递归过程中发现该函数总是要调用到M=0，M=1及M=2的情况，因此，我们就考虑要推导ACK（3，N）必须首先推导ACK（0，N），ACK（1，N）以及ACK（2，N）的情况。
（2）ACK（0，N）可以由函数直接得到，公式为ACK（0，N）=N+1
（3）ACK（1，0）=ACK（0，1）=1+1=0+2
ACK（1，1）=ACK（0，ACK（1，0））=ACK（0，1+1）=1+1+1=1+2
ACK（1，2）=ACK（0，ACK（1，1））=ACK（0，1+2）=1+1+2=2+2
……
因此，我们可以联想到ACK（1，N）=N+2。这个公式可以用数学归纳法证明之。（略）
根据上面的方法，我们可以方便地推导出下面一些公式：
（4）ACK（2，0）=ACK（1，1）=1+2=3（利用M=1的公式）
ACK（2，1）=ACK（1，ACK（2，0））=ACK（1，1+2）=3+2=5
（利用M=1的公式及ACK（2，0））
ACK（2，2）=ACK（1，ACK（2，1））=ACK（1，5）=5+2=（2+1）*2+1
……
因此，我们可以联想到ACK（2，N）=（N+1）*2+1。同样，这个公式可以用数学归纳法证明之。（略）
（5）ACK（3，0）=ACK（2，1）=(1+1)*2+1=5（利用M=2的公式）
ACK（3，1）=ACK（2，ACK（3，0））=ACK（2，5）=（(1+1)*2+1+1）*2+1=2^3+2^2+1
ACK（3，2）=ACK（2，ACK（3，1））=ACK（2，13）=（2^3+2^2+1+1）*2+1=2^4+2^3+2^2+1=2^5-3
……
因此，我们可以联想到ACK（3，N）=2^(N+3)-3。
例4 仍以例1为例，找n个数的r个数的组合。
输入：n，r =5，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
total=10 {组合的总数}
分析：所提示的10组数。首先固定第一位数（如5），其后是在另4个数中再“组合”2个数。这就将“5个数中3个数的组合”推到了“4个数中2个数的组合”上去了。第一位数可以是n，r （如5，3），n个数中r个数组合递推到n-1个数中r-1个数有组合，这是一个递归的算法。即：
var i:integer;
begin for i:=n downto r do
begin {固定i的输出位置}
comb(i-1,r-1); {原过程递推到i-1个数的r-1个数组合}
end;
end;
再考虑打印输出格式。
［程序］
var k,n,r:integer;
Produrce comb(n,r:integer);
var i,temp:integer;
begin for i:=n downto r do
if (i<>n)and(k<>r) then {k为过程外定义的}
begin for temp:=1 to (k-r)*3 do write(' '); {确定i的输出位置}
end;
write(i:3);
if i>1 then comb(i-1,r-1); {递推到下一情形}
else writeln;
end;
begin {main}
write('n,r=');readln(n,r);
if r>n then
begin writeln('Input n,r error!');
halt;
end;
comb(n,r); {调用递归过程}
end;
练习题
1．邮票面值设计（postag.pas）
【题目描述】
给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+k≤40) 种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大max ，使得1-max之间的每一个邮资值都能得到。
例如，N=3，K=2，如果面值分别为1分、4分，则在l～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）：如果面值分别为1分、3分，则在1～7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到连续的邮资最大值，所以max=7，面值分别为l分、3分。
【样例输入】
3 2 {输入第一个数N，第二个数K，中间用空格间隔}
【样例输出】
1 3 {输出的第一行面值分别为l分、3分}
max=7 {输出的第二连续的邮资最大值}
2．聪明的学生（guess.pas）
【题目描述】
一位教授逻辑学的教授有三名非常善于推理且精于心算的学生A，B和C。有一天,教授给他们3人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个正整数，且某两个数的和等于第三个。于是，每个学生都能看见贴在另外两个同学头上的整数，但却看不见自己的数。
这时，教授先对学生A发问了：“你能猜出自己的数吗？”A回答：“不能。”
教授又转身问学生B：“你能猜出自己的数吗？”B想了想，也回答：“不能。”
教授再问学生C同样的问题，C思考了片刻后，摇了摇头：“不能。”
接着，教授又重新问A同样的问题，再问B和C，……，经过若干轮的提问之后，当教授再次询问某人时，此人突然露出了得意的笑容，把贴在自己头上的那个数准确无误地报了出来。
现在，如果告诉你：教授在第N次提问时，轮到回答问题的那个人猜出了贴在自己头上的数是M，你能推断出另外两个学生的头上贴的是什么数吗？
【提示】
在没有人猜出自己头上的数之前，大家对教授提问的回答始终都是“不能”；而且除此之外在A，B，C之间是没有进行任何信息交流的。也就是说，每个人推断的依据仅仅是另外两个人的头上数，以及大家对教授的提问所做出的否定回答。
教授总是从学生A开始提问的。
你可以假定，这3个聪明的学生能够根据已知的条件在最早的轮次猜出自己的数，并且永远都不会猜错。稍经分析和推理，你将得出以下结论：总是头上贴着最大的那个数的人最先猜出自己头上的数。
【输入文件】
输入文件为guess.in。
该文件包括若干组测试数据，其中的每一行代表一组测试数据，由两个整数N和M组成（即在教授第N次提问时，轮到回答问题的那个人猜出了贴在自己头上的数是M）。两个数之间用空格分隔开。最后，由-1 -1组成的一行标志着输入的数据结束。同时要求，0＜N＜500; 0＜M＜30000。
【输出文件】
输出文件为guess.out。按照输入文件中的顺序依次给出各组数据的结果。
文件中对应每组数据输出的第一行是一个整数p，是可能情况的总数。接下来的p行，每一行包括3个数，分别为贴在A、B、C头上的3个数。输出时，所有解按照A头上的数增序排列；在A头上的数相同的情况下，按照B头上的数增序排列。
【样例输入】
5 8
3 2
2 3
-1 -1
【样例输出】
3
2 8 6
5 8 3
6 8 2
1
1 1 2
1
2 3 1
递归作为一种强有力的数学和算法描述工具在Pascal语言中被广泛使用。一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有定义本身的引用（在过程或自定义函数中，又包含自己调用自己），则称它们是递归的或者是递归定义的。
一个递归算法仅使用少量的程序编码就可描述出解题所需要的多次重复计算而不需要设计循环结构。使用递归求解问题，通常可以将一个比较大的问题层层转化为一个与原问题相类似的规模较小的问题来求解，进而最终导致原问题的解决。
例如：n!的定义，我们知道，在数学中n!一般定义为：
1 若n=0
n!=
n×(n-1)! 若n>0
在n>0的公式中，又包含了（n-1）!，这就是递归定义。
利用递归方法，可以用有限的语句来定义对象的无限集合。但在递归定义中，应该至少有一条是非递归的，即初始定义。如上面例子中的第一条，否则就变成了循环定义，产生逻辑性错误。
n!的递归定义的程序：
program find＿n；
var n：integer；
t：longint；
procedure find（n：integer）；
begin
if n＝0 then t：＝1
else
begin find（n-1）；
t：＝t＊n end；
end；
begin
write（'n＝'）；
readln（n）；
find（n）；
writeln（n,'!＝'，t）
end．
递归调用（n进栈）达到结束条件时（n=0，t赋初值1）就停止调用开始返回，再把保存的值取出（n出栈），使n恢复原来的值，并计算t，返回主程序，输出结果t。
3!递归是如何实现的？
（1）设n=3，开始调用过程find，称为第零层调用。
（2）由于公式3!=3 2!，必须先求2!，即程序中的f(n-1)，此时系统自动先保存n的原值3，再设n=2，进入第一层递归调用。
（3）因为2!=2 1!，所以系统又保存2，并设n=1，进入第2层调用。
（4）因为1!=1 0!，所以保存1，并设n=0，进入第3层调用。
（5）因为n=0，终止调用，t赋值1，返回4的入口点。
（6）取出执行4时保存的1，求出t=1 t=1，返回3的入口点。
（7）取出执行3时保存的2，求出t=2 t=2，返回2的入口点。
（8）取出执行2时保存的3，求出t=3 t=6，返回1的入口点。
（9）返回主程序，输出结果：t=6。
从上面分析的过程看到，由于递归调用，需用同一变量名n，但值不同，所以在调用前必须先把n的原值保存，再赋以新值，然后进入调用。调用结束后，再把保存的值取出，使n恢复原来的值。在过程中find中又包含find(n-1)，即又调用了它自己，这就是递归调用。包含有递归调用的算法，就叫做递归算法。
递归调用会产生无终止运算的可能性，因此必须在适当时候终止递归调用，即在程序中必须要有终止条件。上面程序中，过程find的第一条语句就是终止条件。一般地，根据递归定义设计的递归算法中，非递归的初始定义，就用作程序中的终止 条件。
实践证明，不是所有问题都可以用递归的方法处理，用递归算法编写的程序也不一定是好程序。可以看出，执行递归的过程既浪费时间又费存储空间，因此有的语言系统，禁止使用递归，由于计算机存储容量的限制，编译系统也不允许递归。但因递归特别符合人们的思维习惯，递归算法的设计也要比非递归算法设计容易，所以当问题是递归定义，尤其是当涉及的数据结构是递归定义的时候，使用递归算法特别合适。
应用递归算法能够求解的问题一般具有两个特点：
①存在某个特定条件，在此条件下，可得到指定的解，即递归在终止状态。
②对任意给定的条件，有明确的定义规则，可以产生新的状态并将最终导出终止状态，即存在导致问题求解的递归步骤。
递归是用栈来实现的。不过，递归恐怕不像想象得这么简单。首先，它体现了一个数学思想：化归，即把一个问题转化成另一个的方法。递归比较特殊，它是转化成性质相似，但规模更小的问题。
例3 阅读程序NOIp2001_G。
program gao7_1;
function ack(m,n:integer):integer;
begin
if m=0 then ack:=n+1
else if n=0 then ack:=ack(m-1,1)else ack:=ack(m-1,ack(m,n-1))
end;
begin writeln(ack(3,4));
readln;
end.
分析：
这个程序我们可以用下面的函数表示。在解题时，一般都是用递归的方法去实现的，而递归方法将会计算五千多步，在竞赛时这种方法是不可用的，而递归往往可以用递推去实现，因此，我们在教学过程中就讲解了该函数的递推过程，现将推导过程表示如下：
（1）我们在递归过程中发现该函数总是要调用到M=0，M=1及M=2的情况，因此，我们就考虑要推导ACK（3，N）必须首先推导ACK（0，N），ACK（1，N）以及ACK（2，N）的情况。
（2）ACK（0，N）可以由函数直接得到，公式为ACK（0，N）=N+1
（3）ACK（1，0）=ACK（0，1）=1+1=0+2
ACK（1，1）=ACK（0，ACK（1，0））=ACK（0，1+1）=1+1+1=1+2
ACK（1，2）=ACK（0，ACK（1，1））=ACK（0，1+2）=1+1+2=2+2
……
因此，我们可以联想到ACK（1，N）=N+2。这个公式可以用数学归纳法证明之。（略）
根据上面的方法，我们可以方便地推导出下面一些公式：
（4）ACK（2，0）=ACK（1，1）=1+2=3（利用M=1的公式）
ACK（2，1）=ACK（1，ACK（2，0））=ACK（1，1+2）=3+2=5
（利用M=1的公式及ACK（2，0））
ACK（2，2）=ACK（1，ACK（2，1））=ACK（1，5）=5+2=（2+1）*2+1
……
因此，我们可以联想到ACK（2，N）=（N+1）*2+1。同样，这个公式可以用数学归纳法证明之。（略）
（5）ACK（3，0）=ACK（2，1）=(1+1)*2+1=5（利用M=2的公式）
ACK（3，1）=ACK（2，ACK（3，0））=ACK（2，5）=（(1+1)*2+1+1）*2+1=2^3+2^2+1
ACK（3，2）=ACK（2，ACK（3，1））=ACK（2，13）=（2^3+2^2+1+1）*2+1=2^4+2^3+2^2+1=2^5-3
……
因此，我们可以联想到ACK（3，N）=2^(N+3)-3。
例4 仍以例1为例，找n个数的r个数的组合。
输入：n，r =5，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
total=10 {组合的总数}
分析：所提示的10组数。首先固定第一位数（如5），其后是在另4个数中再“组合”2个数。这就将“5个数中3个数的组合”推到了“4个数中2个数的组合”上去了。第一位数可以是n，r （如5，3），n个数中r个数组合递推到n-1个数中r-1个数有组合，这是一个递归的算法。即：
var i:integer;
begin for i:=n downto r do
begin {固定i的输出位置}
comb(i-1,r-1); {原过程递推到i-1个数的r-1个数组合}
end;
end;
再考虑打印输出格式。
［程序］
var k,n,r:integer;
Produrce comb(n,r:integer);
var i,temp:integer;
begin for i:=n downto r do
if (i<>n)and(k<>r) then {k为过程外定义的}
begin for temp:=1 to (k-r)*3 do write(' '); {确定i的输出位置}
end;
write(i:3);
if i>1 then comb(i-1,r-1); {递推到下一情形}
else writeln;
end;
begin {main}
write('n,r=');readln(n,r);
if r>n then
begin writeln('Input n,r error!');
halt;
end;
comb(n,r); {调用递归过程}
end;
练习题
1．邮票面值设计（postag.pas）
【题目描述】
给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+k≤40) 种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大max ，使得1-max之间的每一个邮资值都能得到。
例如，N=3，K=2，如果面值分别为1分、4分，则在l～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）：如果面值分别为1分、3分，则在1～7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到连续的邮资最大值，所以max=7，面值分别为l分、3分。
【样例输入】
3 2 {输入第一个数N，第二个数K，中间用空格间隔}
【样例输出】
1 3 {输出的第一行面值分别为l分、3分}
max=7 {输出的第二连续的邮资最大值}
2．聪明的学生（guess.pas）
【题目描述】
一位教授逻辑学的教授有三名非常善于推理且精于心算的学生A，B和C。有一天,教授给他们3人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个正整数，且某两个数的和等于第三个。于是，每个学生都能看见贴在另外两个同学头上的整数，但却看不见自己的数。
这时，教授先对学生A发问了：“你能猜出自己的数吗？”A回答：“不能。”
教授又转身问学生B：“你能猜出自己的数吗？”B想了想，也回答：“不能。”
教授再问学生C同样的问题，C思考了片刻后，摇了摇头：“不能。”
接着，教授又重新问A同样的问题，再问B和C，……，经过若干轮的提问之后，当教授再次询问某人时，此人突然露出了得意的笑容，把贴在自己头上的那个数准确无误地报了出来。
现在，如果告诉你：教授在第N次提问时，轮到回答问题的那个人猜出了贴在自己头上的数是M，你能推断出另外两个学生的头上贴的是什么数吗？
【提示】
在没有人猜出自己头上的数之前，大家对教授提问的回答始终都是“不能”；而且除此之外在A，B，C之间是没有进行任何信息交流的。也就是说，每个人推断的依据仅仅是另外两个人的头上数，以及大家对教授的提问所做出的否定回答。
教授总是从学生A开始提问的。
你可以假定，这3个聪明的学生能够根据已知的条件在最早的轮次猜出自己的数，并且永远都不会猜错。稍经分析和推理，你将得出以下结论：总是头上贴着最大的那个数的人最先猜出自己头上的数。
【输入文件】
输入文件为guess.in。
该文件包括若干组测试数据，其中的每一行代表一组测试数据，由两个整数N和M组成（即在教授第N次提问时，轮到回答问题的那个人猜出了贴在自己头上的数是M）。两个数之间用空格分隔开。最后，由-1 -1组成的一行标志着输入的数据结束。同时要求，0＜N＜500; 0＜M＜30000。
【输出文件】
输出文件为guess.out。按照输入文件中的顺序依次给出各组数据的结果。
文件中对应每组数据输出的第一行是一个整数p，是可能情况的总数。接下来的p行，每一行包括3个数，分别为贴在A、B、C头上的3个数。输出时，所有解按照A头上的数增序排列；在A头上的数相同的情况下，按照B头上的数增序排列。
【样例输入】
5 8
3 2
2 3
-1 -1
【样例输出】
3
2 8 6
5 8 3
6 8 2
1
1 1 2
1
2 3 1
fulong- 帖子数 : 59
注册日期 : 14-05-09
您在这个论坛的权限：
您不能在这个论坛回复主题