Java递归算法
程序调用自身的编程技巧称为递归(recursion),它做为一种算法在程序设计语言中广泛应用。Java 支持递归,在 Java 编程中,递归是允许方法调用自身调用的属性。调用自身的方法称为是递归的。
递归的典型例子是数字的阶乘。数字 N 的阶乘是 1 到 N 之间所有整数的乘积。例如 3 的阶乘就是 1×2×3。下面的程序使用递归来计算数字的阶乘。
为了更好地理解 fact( ) 方法是如何工作的,让我们通过一个短例子来说明。例如当计算 3 的阶乘时,对 fact( ) 的第一次调用引起参数 2 的第二次调用。这个调用将引起 fact 以参数 1的第三次调用,这个调用返回 1,这个值接着与 2(第二次调用时 n 的值)相乘。然后该结果(现为 2)返回到 fact( ) 的最初的调用,并将该结果与 3(n 的初始值)相乘。这时得到答案 6。可以在 fact( ) 中插入 println() 语句,显示每次调用的阶数以及中间结果。
当一个方法调用它自身的时候,堆栈就会给新的局部变量和自变量分配内存,方法代码就带着这些新的变量从头执行。递归调用并不产生方法新的拷贝。只有参数是新的。每当递归调用返回时,旧的局部变量和自变量就从堆栈中清除,运行从方法中的调用点重新开始。递归方法可以说是像“望远镜”一样,可以自由伸缩。
许多子程序的递归版本执行时会比它们的迭代版本要慢一点,因为它们增加了额外的方法调用的消耗。对一个方法太多的递归调用会引起堆栈崩溃。因为自变量和局部变量的存储都在堆栈中,每次调用都创建这些变量新的拷贝,堆栈有可能被耗尽。如果发生这种情况,Java 的运行时系统就会产生异常。但是,除非递归子程序疯狂运行,否则你大概不会担心这种情况。
递归的主要优点在于:某些类型的算法采用递归比采用迭代算法要更加清晰和简单。例如快速排序算法按照迭代方法是很难实现的。还有其他一些问题,特别是人工智能问题,就依赖于递归提供解决方案。最后,有些人认为递归要比迭代简单。
当编写递归方法时,你必须使用 if 条件语句在递归调用不执行时来强制方法返回。如果你不这么做,一旦你调用方法,它将永远不会返回。这类错误在使用递归时是很常见的。尽量多地使用 println() 语句,使你可以了解程序的进程。如果发现错误,立即中止程序运行。
下面是递归的又一个例子。递归方法 printArray( ) 打印数组 values 中的前 i 个元素。
递归的典型例子是数字的阶乘。数字 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( ) 方法是如何工作的,让我们通过一个短例子来说明。例如当计算 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
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频