如何设计递归算法

如何设计递归算法
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,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子

从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上

不能出现大盘压小盘.找出移动次数最小的方案.

        

程序如下:

program fanta;

var

n:integer;

proceduremove(n,a,b,c:integer);

begin

if n=1 thenwriteln(a,'--->',c)

else begin

move(n-1,a,c,b);

writeln(a,'--->',c);

move(n-1,b,a,c);

end;

end;

begin

write('Entern=');

read(n);

move(n,1,2,3);

end.

例4 快速排序

快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束.

程序如下:

program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procedure quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
  begin
  i:=s;j:=t;x:=b;
  repeat
   while (b[j]>=x) and (j>i) do j:=j-1;
   if j>i then begin t1:=b; b:=b[j];b[j]:=t1;end;
   while (b<=x) and (i<j) do i:=i+1;
   if i<j then begin t1:=b[j];b[j]:=b;b:=t1; end
  until i=j;
  b:=x;
  i:=i+1;j:=j-1;
  if s<j then quicksort(b,s,j);
  if i<t then quicksort(b,i,t);
  end;
begin
write('input data:');
for i:=1 to n do read(a);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a:6);
writeln;
end.