简单来说,如果一个函数(function或者method)在函数体中调用自己,那么它就是一个递归函数。比如下面的Java代码就定义了一个递归函数foo()因为它显示的调用自身。当然如果我们实现并运行这个函数,程序将运行直到程序的调用栈(call stack)溢出(stack overflow)。
public void foo() {
foo();
}
如果一个函数foo1()不是直接调用自身而是通过调用另一个函数foo2()来调用自身,这也是递归。如下代码所示,这是一个隐式的递归。
public void foo1() {
foo2();
}
public void foo2() {
foo1();
}
当我们用一个函数(即caller)调用另一个函数(即callee)的时候,caller的下一条指令的内存地址(即callee结束后应该返回caller继续运行的指令地址),caller的形参,以及本地变量都要存入在内存的程序调用栈中。当callee运行结束返回caller的时候,caller应该运行的下一条指令地址,caller本地的形参和变量都会从程序调用栈中恢复出来。对于CPU(中央处理单元),寄存器的存取速度是最快的,使用循环结构可以大量的使用寄存器(register)从而降低延迟。因为栈操作需要多次使用内存,且内存的速度远慢于寄存器,递归的运行效率要低于循环结构。另外,因为一个程序的调用栈空间有限,次数过多的递归会导致调用栈溢出从而造成运行错误。
使用递归的方法可以简化代码,节省编程时间。但是,由于递归涉及到大量的调用栈操作,递归的效率通常会较低,运算时间也较长。
用递归的方法计算阶乘是一个简单明了的例子,以下代码实现了一个factorial()递归函数来计算整数n的阶乘。
public long factorial(int n) {
if(n<=1) {
// 基本情况。
return 1;
} else {
// 递归情况。
return n*factorial(n-1);
}
}
该函数通过if-else结构区分了两种情况:基本情况(base case)和递归情况(recursive case)。如果是递归情况,函数将n减1,然后将其作为下一次递归调用的实参继续调用自身进入下一轮递归;如果是基本情况,当前调用则返回1给其调用函数。通过该设计我们可以知道,对于任何n,在通过多次递归调用后,都会最终变为1,然后进入基本情况从而从递归调用中返回。
下面的动图给出了当用递归计算3的阶乘的过程。需要注意的是尽管每次函数的递归调用的都是自身,但是传递的参数n却在不断地变化直到可以用基本情况(base case)处理并返回上一级调用。上一级递归调用因为得到了返回值,所以也可以继续运行并得以返回再上一级。
全部状态的静态图如下。
为了对比,我们提供了非递归的阶乘计算函数factorial_non_recursive。
public long factorial_non_recursive(long n) {
long result = 1;
for(long i = n; i>1; i--) {
result = result * i;
}
return result;
}
我们也在Java中粗略对比了两者的性能。在一次实验中我们计算了0-19共二十个整数各自的阶乘,递归函数共消耗1375906纳秒,非递归函数消耗了819783纳秒。即在这次实验中,非递归函数的性能是递归函数的大约1.68倍。当然必须指出的是这个实验并不精确,实际情况非常复杂。
既然递归的性能不如非递归程序,为什么还要学习?比较重要的原因有在一些比较复杂的问题中,设计递归算法比较容易,可以大量减少开发时间。
斐波那契数列的生成函数fibonacci()可以定义为
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
下面的Java代码是递归版本的计算斐波那契数列的函数。我们看到,代码几乎就是直白的翻译了斐波那契数列的定义。所以该函数的实现非常省时省力,但是代码效率不高。因为根据定义,当计算fibonacci(n)的时候,计算量是计算fibonacci(n-1)和fibonacci(n-2)之和。同理,计算fibonacci(n-1)时,计算量是计算fibonacci(n-2)和fibonacci(n-3)之和。也就是说,随着n的增大,计算复杂度的增加是指数级的。另外,一个递归函数可以有两个或者多个基本情况(分支)。
public int fibonacci(int n) {
if(n == 0) {
// 基本情况1。
return 0;
} else if(n == 1) {
// 基本情况2。
return 1;
} else {
// 递归情况。
return fibonacci(n-1) + fibonacci(n-2);
}
}
如果我们用一个循环来输出n为0到40的斐波那契数列,结果如下:
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(4) = 3
fibonacci(5) = 5
fibonacci(6) = 8
fibonacci(7) = 13
fibonacci(8) = 21
fibonacci(9) = 34
fibonacci(10) = 55
fibonacci(11) = 89
fibonacci(12) = 144
fibonacci(13) = 233
fibonacci(14) = 377
fibonacci(15) = 610
fibonacci(16) = 987
fibonacci(17) = 1597
fibonacci(18) = 2584
fibonacci(19) = 4181
fibonacci(20) = 6765
fibonacci(21) = 10946
fibonacci(22) = 17711
fibonacci(23) = 28657
fibonacci(24) = 46368
fibonacci(25) = 75025
fibonacci(26) = 121393
fibonacci(27) = 196418
fibonacci(28) = 317811
fibonacci(29) = 514229
fibonacci(30) = 832040
fibonacci(31) = 1346269
fibonacci(32) = 2178309
fibonacci(33) = 3524578
fibonacci(34) = 5702887
fibonacci(35) = 9227465
fibonacci(36) = 14930352
fibonacci(37) = 24157817
fibonacci(38) = 39088169
fibonacci(39) = 63245986
fibonacci(40) = 102334155
注意在n接近40的时候,系统已经要花我们可以感觉到的时间来计算。
下面是非递归版本的fibonacci函数。程序结构较递归版本更复杂,行数更多,写代码的时间相应的也会更长。但是这段代码的复杂度是线性的,即运行速度远大于递归版本,尤其是在n的值较大的时候。
public static int fibonacci_non_recursive(int n) {
if(n == 0) {
return 0;
} else if(n == 1) {
return 1;
} else {
int fibo = 1;
int fibo_previous = 0;
for(int i=2; i<=n; i++) {
int current = fibo;
fibo = fibo + fibo_previous;
fibo_previous = current;
}
return fibo;
}
}
如果我们用一个循环来输出n为0到40的斐波那契数列,会发现这段代码的效率要比递归版本快得多,结果如下(为了节省空间,我们忽略了中间结果)。
fibonacci_non_recursive(0) = 0
fibonacci_non_recursive(1) = 1
fibonacci_non_recursive(2) = 1
.
.
.
fibonacci_non_recursive(39) = 63245986
fibonacci_non_recursive(40) = 102334155
在一个粗略的性能对比测试中,当n=25时,非递归版的时间消耗为154256纳秒;递归版消耗了1166585纳秒,即递归版的性能在n=25时大约是非递归版的7.5倍。当n变小时,性能差距会缩小;当n变大时,性能差距会进一步增大。所以当使用递归时,虽然缩短了开发时间,但是程序的性能会下降。
在前面我们学习过,单链表有一个特殊的性质,即我们只能从链表头(head)开始向链表尾(tail)遍历而不能逆向遍历。所以在这一小节里我们将会讨论一个有趣的问题,如果我们有一个叫做nameList的单链表,如下图所示。怎样写一个简单的算法将其所有元素逆序输出呢?如果用非递归的方法确实比较复杂,但是递归方法的实现却非常容易。
我们给LinkedList类添加了一个递归函数printListInBackOrder。当调用该递归函数的时候,将表头作为实参n,如果当前n的next值不为0,那么就递归调用自身,将n.next(下一节点引用)作为下一个递归调用的实参。直到n.next为0,即我们到达表尾。
基本情况为在当n.next为null时,表示当前n为表尾,则打印其元素值然后返回上一级调用函数。在上一级调用函数的递归情况里,从递归调用中返回后打印出当前节点的元素值再返回上一级节点。即函数在从递归调用返回后才打印当前的元素值。所以最后的输出结果为链表的逆序。
public void printListInBackOrder(Node n) {
if(n.next == null) {
// 基本情况。
System.out.println(n.element);
} else {
// 递归情况。
printListInBackOrder(n.next);
System.out.println(n.element);
}
}
为了在LinkedList类之外获取表头head,我们给LinkedList类添加了一个方法getHead()用来返回表头。
public Node getHead() {
return head;
}
我们用下面的语句调用printListInBackOrder函数从而获取链表的逆序输出。
nameList.printListInBackOrder(nameList.getHead());
输出结果如下图所示。
Frank
Eric
David
Chris
Bob
Adam
注册用户登陆后可留言