Java递归算法

樵夫2021-09-08 10:52

    程序调用自身的编程技巧称为递归(recursion),它做为一种算法在程序设计语言中广泛应用。Java支持递归,在Java编程中,递归是允许方法调用自身调用的属性。调用自身的方法称为是递归的。

Java递归算法

    递归的典型例子是数字的阶乘。数字N的阶乘是1到N之间所有整数的乘积。例如3的阶乘就是1×2×3。下面的程序使用递归来计算数字的阶乘。

public class Factorial {
    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("3的阶乘是 " + f.fact(3));
        System.out.println("4的阶乘是 " + f.fact(4));
        System.out.println("5的阶乘是 " + f.fact(5));
    }
}

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

3的阶乘是 6
4的阶乘是 24
5的阶乘是 120

    如果你对递归的方法比较陌生,那么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()语句,使你可以了解程序的进程。如果发现错误,立即中止程序运行。

    下面是递归的又一个例子。递归方法printArray()打印数组values中的前i个元素。

class RecTest {
    int values[];
    RecTest(int i) {
        values = new int[i];
    }
    void printArray(int i) {
        if (i == 0){
            return;
        } else {
            printArray(i - 1);
        }
        System.out.println("[" + (i - 1) + "] " + values[i - 1]);
    }
}
class Recursion2 {
    public static void main(String args[]) {
        RecTest ob = new RecTest(10);
        int i;
        for (i = 0; i < 10; i++) {
            ob.values[i] = i;
        }
        ob.printArray(10);
    }
}

    该程序产生如下的输出:

[0] 0
[1] 1
[2] 2
[3] 3
[4] 4
[5] 5
[6] 6
[7] 7
[8] 8
[9] 9

    以上就是小编为大家整理发布的“Java递归算法”一文,更多相关内容尽在开课吧广场Java教程频道。

Java递归算法

免责声明:本站所提供的内容均来源于网友提供或网络搜集,由本站编辑整理,仅供个人研究、交流学习使用。如涉及版权问题,请联系本站管理员予以更改或删除。
有用
分享
全部评论快来秀出你的观点
登录 后可发表观点…
发表
暂无评论,快来抢沙发!
高并发编程训练营