Chinaunix首页 | 论坛 | 博客
  • 博客访问: 409796
  • 博文数量: 114
  • 博客积分: 7010
  • 博客等级: 少将
  • 技术积分: 1395
  • 用 户 组: 普通用户
  • 注册时间: 2008-07-05 17:54
文章分类

全部博文(114)

文章存档

2011年(2)

2009年(1)

2008年(111)

我的朋友

分类: Java

2008-08-02 20:53:40

    如果你对递归的方法比较陌生,那么fact( )的操作可能看起来似乎有点糊涂(底下有示例代码)。它是这样工作的:当fact( ) 带着参数1被调用时,该方法返回1;否则它返回fact( n-1 ) 与n的乘积。为了对这个表达式求值,fact() 带着参数n-1 被调用。重复这个过程直到 n 等于 1,且对该方法的调用开始返回。

    为了更好地理解fact( )方法是如何工作的,让我们通过一个短例子来说明。例如当计算3 的阶乘时,对fact() 的第一次调用引起参数2的第二次调用。这个调用将引起fact 以参数1 的第三次调用,这个调用返回1,这个值接着与2(第二次调用时n的值)相乘。然后该结果(现为2)返回到fact()的最初的调用,并将该结果与3(n的初始值)相乘。这时得到答案,6。如果你在fact()中插入println() 语句,显示每次调用的阶数以及中间结果,你会觉得很有意思。

    当一个方法调用它自身的时候,堆栈就会给新的局部变量和自变量分配内存,方法代码就带着这些新的变量从头执行。递归调用并不产生方法新的拷贝。只有参数是新的。每当递归调用返回时,旧的局部变量和自变量就从堆栈中清除,运行从方法中的调用点重新开始。递归方法可以说是像“望远镜”一样,可以自由伸缩。

    许多子程序的递归版本执行时会比它们的迭代版本要慢一点,因为它们增加了额外的方法调用的消耗。对一个方法太多的递归调用会引起堆栈崩溃。因为自变量和局部变量的存储都在堆栈中,每次调用都创建这些变量新的拷贝,堆栈有可能被耗尽。如果发生这种情况,Java 的运行时系统就会产生异常。但是,除非递归子程序疯狂运行,否则你大概不会担心这种情况。

    递归的主要优点在于:某些类型的算法采用递归比采用迭代算法要更加清晰和简单。例如快速排序算法按照迭代方法是很难实现的。还有其他一些问题,特别是人工智能问题,就依赖于递归提供解决方案。最后,有些人认为递归要比迭代简单。

    当编写递归方法时,你必须使用if条件语句在递归调用不执行时来强制方法返回。如果你不这么做,一旦你调用方法,它将永远不会返回。这类错误在使用递归时是很常见的。尽量多地使用println() 语句,使你可以了解程序的进程;如果发现错误,立即中止程序运行。

 

// A simple example of recursion.


class Factorial {
// this is a recursive function

int fact(int n) {
int result;

if(n==1) return 1;
result = fact(n-1) * n;
return result;


}
}


class Recursion {
public static void main(String args[]) {
Factorial f = new Factorial();


System.out.println("Factorial of 3 is " + f.fact(3));
System.out.println("Factorial of 4 is " + f.fact(4));
System.out.println("Factorial of 5 is " + f.fact(5));


}
}


该程序产生的输出如下所示:

Factorial of 3 is 6
Factorial of 4 is 24
Factorial of 5 is 120


阅读(623) | 评论(0) | 转发(0) |
0

上一篇:java递归实现文件的删除和拷贝

下一篇:DWR

给主人留下些什么吧!~~