递归算法一般用于解决三类问题：
(1)数据的定义是按递归定义的。（Fibonacci函数）
(2)问题解法按递归算法实现。
这类问题虽则本身没有明显的递归结构，但用递归求解比迭代求解更简单，如Hanoi问题。
(3)数据的结构形式是按递归定义的。
如二叉树、广义表等，由于结构本身固有的递归特性，则它们的操作可递归地描述。
递归的缺点：
递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
递归典型问题： 梵塔问题（汉诺塔问题）
已知有三根针分别用A, B, C表示，在A中从上到下依次放n个从小到大的盘子，现要求把所有的盘子
从A针全部移到B针，移动规则是：可以使用C临时存放盘子，每次只能移动一块盘子，而且每根针上
不能出现大盘压小盘，找出移动次数最小的方案.
[2]
/*Name:HANOITOWER
*Description:solvethehanoitowerproblembyrecursion
*/
#include<stdio.h>
#include<stdlib.h>
/*movenplates:from-->to,
*thebuffercanbeusedifneeded*/
inthanoi(intn,charfrom,charbuffer,charto)
{
if(n==1)
{
/*movetheNO.1platedirectly:from-->to*/
printf("Moveplate#%dfrom%cto%c\n",n,from,to);
/*theNO.1plateismovedsoreturn*/
return0;
}
else
{
/*nplatestobemoved:from-->to,
*movethen-1platesabove:from-->buffer,
*givethistasktothenextrecursion*/
hanoi(n-1,from,to,buffer);
/*then-1platesaboveweremovedtobuffer,
*sotheNO.nplatecanbemoveddirectly*/
printf("Moveplate#%dfrom%cto%c\n",n,from,to);
/*howeverthen-1platesarestillinbuffer,
*movethemtotheterminalposition,
*(the"from"positionhasnoplate,&canbeoneso-calledbuffer)*/
hanoi(n-1,buffer,from,to);
/*thetaskgivenisdonesoreturn*/
return0;
}
}
intmain()
{
#defineN4
/*NplatesinA,let'smovethemtoC*/
hanoi(N,'A','B','C');
return0;
}
如：
//pascal
procedurea;
begin
a;
end;
这种方式是直接调用.
又如：
//pascal
procedureb;
begin
c;
end;
procedurec;
begin
b;
end;
这种方式是间接调用.
例1计算n!可用递归公式如下：
1 当 n=0 时
fac(n)={n*fac(n-1) 当n>0时
可编写程序如下：
//pascal
programfac2;
var
n:integer;
functionfac(n:integer):real;
begin
ifn=0thenfac:=1elsefac:=n*fac(n-1)；
end;
begin
write('n=');readln(n);
writeln('fac(',n,')=',fac(n):6:0);
end.
例2 楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，编一程序计算共有多少种不同的走法.
设n阶台阶的走法数为f(n)
显然有
1 n=1
f(n)={2 n=2
f(n-1)+f(n-2) n>2
可编程序如下：
//pascal
programlouti;
varn:integer;
functionf(x:integer):integer;
begin
ifx=1thenf:=1else
ifx=2thenf:=2elsef:=f(x-1)+f(x-2);
end;
begin
write('n=');read(n);
writeln('f(',n,')=',f(n))
end.
2.2 如何设计递归算法
1.确定递归公式
2.确定边界（终了)条件
练习：
用递归的方法完成下列问题
1.求数组中的最大数
2.1+2+3+...+n
3.求n个整数的积
4.求n个整数的平均值
5.求n个自然数的最大公约数与最小公倍数
6.有一对雌雄兔，每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子
7.已知：数列1,1,2,4,7,13,24,44,...求数列的第 n项.
2.3典型例题
例3 快速排序
快速排序的思想是：先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边，再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1,处理结束.
程序如下：
programkspv;
var
a:array[0..10000]oflongint;
i,n:integer;
procedurequicksort(l,r:longint);
vari,j,mid:longint;
begin
i:=l;j:=r;mid:=a[(l+r)div2];
repeat
whilea[i]<middoinc(i);
whilea[j]>middodec(j);
ifi<=jthen
begin
a[0]:=a[i];a[i]:=a[j];a[j]:=a[0];
inc(i);dec(j);
end;
untili>j;
ifi<rthenquicksort(i,r);
ifl<jthenquicksort(l,j);
end;
begin
write('inputdata:');
readln(n);
fori:=1tondoread(a[i]);
writeln;
quicksort(1,n);
write('outputdata:');
fori:=1tondowrite(a[i],'');
writeln;
end.
练习：
1.计算ackerman函数值:
n+1 m=0
ack(m,n)={ ack(m-1,1) m<>0,n=0
ack(m-1,ack(m,n-1)) m<>0,n<>0
求ack(5,4) |
收藏
淘帖
踩
