遞歸算法:計算機科學中解決問題的一種方法-中文百科頻道

實現

如何設計遞歸算法

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);

}