第五章 递归

递归(Recursion)

 

1. 什么是递归

简单来说,如果一个函数(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)从而降低延迟。因为栈操作需要多次使用内存,且内存的速度远慢于寄存器,递归的运行效率要低于循环结构。另外,因为一个程序的调用栈空间有限,次数过多的递归会导致调用栈溢出从而造成运行错误。

使用递归的方法可以简化代码,节省编程时间。但是,由于递归涉及到大量的调用栈操作,递归的效率通常会较低,运算时间也较长。

2. 阶乘

用递归的方法计算阶乘是一个简单明了的例子,以下代码实现了一个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)处理并返回上一级调用。上一级递归调用因为得到了返回值,所以也可以继续运行并得以返回再上一级。

avatar

全部状态的静态图如下。

avatar

为了对比,我们提供了非递归的阶乘计算函数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倍。当然必须指出的是这个实验并不精确,实际情况非常复杂。

既然递归的性能不如非递归程序,为什么还要学习?比较重要的原因有在一些比较复杂的问题中,设计递归算法比较容易,可以大量减少开发时间。

3. 斐波那契数列

斐波那契数列的生成函数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变大时,性能差距会进一步增大。所以当使用递归时,虽然缩短了开发时间,但是程序的性能会下降。

4. 使用递归逆序输出单链表

在前面我们学习过,单链表有一个特殊的性质,即我们只能从链表头(head)开始向链表尾(tail)遍历而不能逆向遍历。所以在这一小节里我们将会讨论一个有趣的问题,如果我们有一个叫做nameList的单链表,如下图所示。怎样写一个简单的算法将其所有元素逆序输出呢?如果用非递归的方法确实比较复杂,但是递归方法的实现却非常容易。

avatar

我们给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
上一章
下一章

注册用户登陆后可留言

Copyright  2019 Little Waterdrop, LLC. All Rights Reserved.