递归算法:计算机科学中解决问题的一种方法-中文百科频道

实现

如何设计递归算法

1.确定递归公式

2.确定边界(终了)条件

递归的一般模式

procedure aaa(k:integer);

begin

if k=1 then (边界条件及必要操作)

else begin

aaa(k-1);

(重复的操作);

end;

C#:例子

例：一列数的规则如下: 1、1、2、3、5、8、13、21、34...... 求第30位数是多少。

public class MainClass

{

public static void Main()

{

Console.WriteLine(Foo(30));

}

public static int Foo(int i)

{

if (i <= 0)

return 0;

else if(i > 0 && i <= 2)

return 1;

else return Foo(i -1) + Foo(i - 2);

}

又如:

procedure a;

begin

end;

这种方式是直接调用.

又如:

procedure c(形参);forward;

procedure b;

局部说明

begin

. .

c(实参);

. .

end;

procedure c;

局部说明；

begin

. .

end;

这种方式是间接调用.

例1计算n!可用递归公式如下:

fac:=n*fac(n-1) {当n>0时}

fac(n)={

fac:=1; { 当n=0时}

可编写程序如下:

program facn;

var

n:integer;

function fac(n:integer):real;

begin

if n=0

then fac:=1

else fac:=n*fac(n-1);

end;

begin

write('n=');readln(n);

writeln(n,'!=',fac(n):0:0);

end.

应用

例1：把一个整数按n(2<=n<=20)进制表示出来，并保存在给定字符串中。比如121用二进制表示得到结果为：“1111001”。

参数说明：s: 保存转换后得到的结果。

n: 待转换的整数。

b: n进制（2<=n<=20）

void

numbconv(char *s, int n, int b)

{

int len;

if(n == 0) {

strcpy(s, "");

return;

}

/* figure out first n-1 digits */

numbconv(s, n/b, b);

/* add last digit */

len = strlen(s);

s[len] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[n%b];

s[len+1] = '0';

}

void

main(void)

{

char s;

int i, base;

FILE *fin, *fout;

fin = fopen("palsquare . in", "r");

fout = fopen("palsquare.out", "w");

assert(fin != NULL && fout != NULL);

fscanf(fin, "%d", &base);

/*PLS set START and END*/

for(i=START; i <= END; i++) {

numbconv(s, i*i, base);

fprintf(fout, "%sn", s);

}

exit(0);

}

例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.

设n阶台阶的走法数为f(n)

显然有

n=1

f(n)={f(n-1)+f(n-2)} n>2

可编程序如下：

program louti;

var n:integer;

function f(x:integer):integer;

begin

if x=1 then f:=1 else

if x=2 then f:=2 else f:=f(x-1)+f(x-2);

end;

begin

write('n=');read(n);

writeln('f(',n,')=',f(n))

end.

例3汉诺塔问题

如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子

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

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

程序如下:

program hanoi;

var

n:integer;

procedure move(n,a,b,c:integer);

begin

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

else begin

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

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

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

end;

begin

write('Enter n=');

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

if i

until i=j;

b:=x;

i:=i+1;j:=j-1;

if s

if i

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.

例5求最大公约数

最大公约数算法：给两个数，如果两个数相等，最大公约数是其本身；如果不等，取两个数相减的绝对值和两个数中最小的数比较，相等则为最大公约，不等则继续上面的算法，直到相等。

程序如下：

public class YueShuTest{

public static void yueshu（int num1，int num2）{

if(num1==num2){System.out.println(num1);

}

else{

//递归调用本身

yueshu(Math.abs(num1-num2),Math.min(num1,num2));

}

汉诺塔C语言递归算法

汉诺（Hanoi）塔问题：古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上(如图)。有一个和尚想把这64个盘子从A座移到C座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。在移动过程中可以利用B座，要求打印移动的步骤。

这个问题在盘子比较多的情况下，很难直接写出移动步骤。我们可以先分析盘子比较少的情况。假定盘子从大向小依次为：盘子1，盘子2，...，盘子64。

如果只有一个盘子，则不需要利用B座，直接将盘子从A移动到C。

如果有2个盘子，可以先将盘子1上的盘子2移动到B；将盘子1移动到c；将盘子2移动到c。这说明了：可以借助B将2个盘子从A移动到C，当然，也可以借助C将2个盘子从A移动到B。

如果有3个盘子，那么根据2个盘子的结论，可以借助c将盘子1上的两个盘子从A移动到B；将盘子1从A移动到C，A变成空座；借助A座，将B上的两个盘子移动到C。这说明：可以借助一个空座，将3个盘子从一个座移动到另一个。

如果有4个盘子，那么首先借助空座C，将盘子1上的三个盘子从A移动到B；将盘子1移动到C，A变成空座；借助空座A，将B座上的三个盘子移动到C。

上述的思路可以一直扩展到64个盘子的情况：可以借助空座C将盘子1上的63个盘子从A移动到B；将盘子1移动到C，A变成空座；借助空座A，将B座上的63个盘子移动到C。

根据以上的分析，不难写出程序：

void Move(char chSour,char chDest)

{

/*打印移动步骤*/

printf("nMove the top plate of %c to %c",chSour,chDest);

}