利用递归法求阿克曼函数

这里给出C语言的阿克曼递归函数：首先，阿克曼函数标准定义：#include <stdio.h>

#include <stdlib.h>int Ackmann(int n,int m)

{

if(m==0)return n+1

else if(m>0 &&n==0)return Ackmann(m-1,1)

else return Ackmann(m-1,Ackmann(m,n-1))

}int main()

{

int m,n

printf("输入m和n：")

scanf("%d,%d",&m,&n)

printf("结果是：%d",Ackmann(n,m))

system("pause")

return 0

}

1.概念

一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).

如:

procedure

a

begin

.

.

.

a

.

.

.

end

这种方式是直接调用.

又如:

procedure

b

procedure

c

begin

begin

.

.

.

.

.

.

c

b

.

.

.

.

.

.

end

end

这种方式是间接调用.

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

1

当

n=0

时

fac(n)={n*fac(n-1)

当n>0时

可编写程序如下:

program

fac2

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('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

可编程序如下：

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.

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

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

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

程序如下:

program

fanta

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

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:=sj:=tx:=b[i]

repeat

while

(b[j]>=x)

and

(j>i)

do

j:=j-1

if

j>i

then

begin

t1:=b[i]

b[i]:=b[j]b[j]:=t1end

while

(b[i]<=x)

and

(i<j)

do

i:=i+1

if

i<j

then

begin

t1:=b[j]b[j]:=b[i]b[i]:=t1

end

until

i=j

b[i]:=x

i:=i+1j:=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[i])

writeln

quicksort(a,1,n)

write('output

data:')

for

i:=1

to

n

do

write(a[i]:6)

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)

---