您现在的位置是：亿华云 > 知识

Java递归算法

亿华云2025-10-05 01:40:51【知识】0人已围观

简介在程序设计中，递归的设计就是利用了栈的“后进先出”的思想。利用栈可以将递归程序转换为非递归程序。 3.3.1 递

在程序设计中，递归递归的算法设计就是利用了栈的“后进先出”的思想。利用栈可以将递归程序转换为非递归程序。递归

3.3.1 递归

递归是算法指在函数的定义中，在定义自己的递归同时又出现了对自身的调用。如果一个函数在函数体中直接调用自己，算法就称为直接递归函数。递归如果经过一系列的算法中间调用，间接调用自己的递归函数就称为间接递归调用。

1. 递归函数

例如，算法n 的递归阶乘递归定义如下：

n 的阶乘算法如下：

public static long fact(int n)

//n 的阶乘的非递归算法实现

{

long f = 1;

int i;

for(i=1;i<n+1;i++) // 直接利用迭代消除递归

f = f * i;

return f;

}

Ackerman 函数定义如下：

Ackerman 函数相应算法如下：

public static long Ack(long m,long n)

//Ackerman 递归算法实现

{

if(m == 0)

return n + 1;

else if(n==0)

return Ack(m - 1, 1);

else

return Ack(m - 1, Ack(m, n - 1));

}

2. 递归调用过程

递归问题可以分解成规模小且性质相同的问题加以解决。下面我们以著=名的算法汉诺塔问题为例来说明递归的调用过程。

n 阶汉诺塔问题。递归假设有3 个塔座X 、算法Y 、递归Z ，在塔座X 上放置n 个直径大小各不相同、站群服务器从小到大编号为1 ，2 ，… ，n 的圆盘，如图3-9 所示。要求将X 轴上的n 个圆盘移动到塔座Z 上并要求按照同样的叠放顺序排列，圆盘移动时必须遵循以下规则：

（1 ）每次只能移动一个圆盘。

（2 ）圆盘可以放置在X 、Y 和Z 中的任何一个塔座。

（3 ）任何时候都不能将一个较大的圆盘放在较小的圆盘上。

如何实现将放在X 上的圆盘按照规则移动到Z 上呢？当n=1 时，问题比较简单，直接将编号为1 的圆盘从塔座X 移动到Z 上即可。当n>1 时，需要利用塔座Y 作为辅助塔座，若能将放置在编号为n 上的n -1 个圆盘从塔座X 上移动到Y 上，则可以先将编号为n 的圆盘从塔座X 移动到Z 上，然后将塔座Y 上的n -1 个圆盘移动到塔座Z 上。而如何将n -1 个圆盘从一个塔座移动到另一个塔座又成为与原问题类似的问题，只是规模减小了1 ，源码库因此可以用同样的方法解决。这是一个递归问题，汉诺塔的算法描述如下：

public static void Hanoi(int n,String A,String B,String C)

// 将塔座A 上从小到大自上而下编号为1 到n 的圆盘按照规则搬到塔座C 上，B 可以作为辅助塔座

{

if(n == 1)

move(1, A, C); // 将编号为1 的圆盘从A 移动到

else {

Hanoi(n - 1, A, C, B); // 将编号为1 到n-1 的圆盘从A 移动到B ，C 作为辅助塔座 move(n, A, C); // 将编号为n 的圆盘从A 移动到

Hanoi(n - 1, B, A, C); // 将编号为1 到n-1 的圆盘从B 移动到C ，A 作为辅助塔座

}

public static void move (int n, String tempA, String tempB) {

System.out.println("move plate"+n+" from column "+tempA+" to column "+ tempB);

}