在Java中,方法可以调用自身.这个过程称为递归(recursion),调用自己的方法称为递归方法(recursive).一般而言,递归是某一事物内部定义自己的过程,与循环定义有些相似.递归方法的关键在于调用自身的语句.递归是一种功能强大的控制机制.

递归的经典实例是计算数值的阶乘,数N的阶乘是从1到N的所有整数的积.例如,3个阶乘是1X2X3=6,下面的程序展示了计算数值的阶乘的递归方法.为了进行比较,程序中还有一个非递归的等价方法:

public class test2
{
    // @param args
    public static void main(String args[])
    {
     Factorial f = new Factorial();
     
     System.out.println("Factorials using  recursive method:");
     System.out.println("Factorial of 3 is  "+f.factR(3));
     
     System.out.println("Factorials using  iterative method:");
     System.out.println("Factorial of 3 is  "+f.factI(3));
    }
}
class Factorial
{
    int factR(int n)
    {
        if(n == 1) return n;
        return factR(n-1) * n;
    }
    
    int factI(int n)
    {
        int t,result;
        
        result = 1;
        for(t=1;t<=n;t++) result *= t;
        return result;
    }
}

输出:

Factorials using recursive method:
Factorial of 3 is 6
Factorials using iterative method:
Factorial of 3 is 6

非递归方法factI()的运算应该很清楚,他使用一个从1开始的循环,将每一个数值与不断变化的乘积相乘.

递归方法factR()的运算这有点复杂,当实参为1时调用facR(),返回1;否则返回的结果为factR(n01)*n.为计算这个表达式,就要以形参n-1来调用factR(),这个过程会重复进行,直到n等于1为止,然后对方法的调用开始返回.例如,计算2的阶乘时,第一次调用factR()会导致以1为实参的factR()被第二次调用.这次调用会返回1,然后该值与2相乘(即n的初值),那么答案就是2,如果把println()语句放入factR()中来显示每一级调用以及中间的结果,你可能会发现这是十分有趣的.

当方法调用自身时,新的局部变量和形参存储到堆栈中,然后从堆栈的开始用这些新的变量来执行方法代码.递归调用不会生成方法新的副本,只有实参是新生成的.在每个递归调用返回时,旧的局部变量和形参将从堆栈中删除,执行继续从方法内部的调用点开始.递归方法可以被看成把”压缩式望远镜”抽出,又缩回.

许多例程的递归版本比相应的循环版本执行速度慢,这是因为有了额外的方法调用开销.某个方法的过多的递归调用会导致堆栈溢出.因为形参和局部变量都存储在堆栈中,而且每一次新的调用都会创建这些变量的新副本,所以这可能会把堆栈的空间耗尽,如果发生溢出,就会导致Java运行时错误.然而,只要递归不疯狂运行,一般无须担心溢出.递归的主要优点是,与使用循环相比,在实现某些类型的算法时更清楚,更简单.例如,快速排序算法用循环方法实现是十分困难的.同时,有些问题,特别是与人工智能相关的问题看起来更适合用递归方法来解决.当编写递归方法时,必须在某处有条件语句,如if,以强迫方法在没有执行递归调用时返回.如果没有这样做,一旦调用方法,就再也不会返回了.在使用递归时这种类型的错误十分常见.可以自由使用println()语句,这样就可以观察正在执行什么,并且在发现有错误时终止执行.