第七章

递归

7.1  基本概念

按照原书的流程,现在应该讲到递归了。递归是一种有力的数学工具。不知道各位学过Lisp或者它的方言没有(例如Scheme),如果学过的话,一定会对递归非常熟悉,因为在Lisp和它的方言中,是没有循环语句的,如果您要构造一个循环,必须通过递归的形式来实现。当时我的脑袋怎么也转不过弯来,因为我已经习惯了在C/C++里面使用for、while等语句来循环了,在Lisp里面刚开始我几乎没有办法写出一个不出错的循环来。

例如,下面的代码:

for (int i = 0; i <= 10; ++i)
{
}

可以被转换成递归:

void recursion_loop(int i)
{
    if (i == 10)
        return;
    else
        recursion_loop(i + 1);
}

// 调用:
recursion_loop(0);

递归具有以下的性质:

  1. 递归就是在某个过程中重复调用它本身。例如在上面的例子中,就是在recursion_loop()这个函数中再调用它本身。

  2. 必须有停止条件。这很容易理解,因为如果没有停止条件的话,那么这个递归就会子子孙孙无穷溃也。例如在上面的例子中,if (i == 10) 就是停止的条件。

  3. 递归会受到现实中的限制,例如栈的大小不够而导致失败。这是因为在计算机中,栈的大小是有上限的,而每次递归调用函数本身,都需要在栈中保存返回地址、参数等信息,在经过N次递归之后,栈很可能就会满了,这样就会导致无法进行第(N+1)次递归。

根据上面的性质3我们可以知道,并不是所有的语言都支持递归的——如果某种语言能够支持递归,那么它必须是支持“栈”这种结构的。目前就我所知道的对递归的使用发挥得最淋漓尽致的语言,Lisp和它的方言是当之无愧的王者。

7.2  应用

唉,本来都不想写递归的例子了,因为这些例子已经被写过无数次。提到递归,就一定会说到阶乘、斐波那契数列和汉诺塔这三个例子,但本着把教科书过一遍的目的,我还是再进行一次重复劳动吧(但不再对这三个例子进行讲解了,随便找一本数据结构的书都会有这方面的内容)。最后增加一个帕斯卡三角形,在我国也就是著名的杨辉三角。

7.2.1  阶乘

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   factorial.c
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-8 21:23:16
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

static long factorial(const long n)
{
    return 0 == n || 1 == n ? 1  : n * factorial(n - 1);
}

int main()
{
    long lResult = factorial(10);
    printf("%ld\n", lResult);
}

7.2.2  斐波那契数列

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   fib.c
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-8 21:28:56
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

static long fib(const long n)
{
    return 0 == n || 1 == n ? 1 : fib(n - 1) + fib(n - 2);
}

int main()
{
    long lResult = fib(10);
    printf("%ld\n", lResult);
}

7.2.3  汉诺塔

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   hanoi.c
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-8 21:40:44
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

static void move(const char x, const int n, const char z)
{
    printf("把圆盘 %d 从柱子 %c 移动到 %c 上\n", n, x, z);
}

static void hanoi(const int n, const char x, const char y, const char z)
{
    if (1 == n)
        move(x, 1, z);          // 如果只有一个盘,则直接将它从x移动到z
    else
    {
        hanoi(n - 1, x, z, y);  // 把1 ~ n - 1个盘从x移动到y,用z作为中转
        move(x, n, z);          // 把第n个盘从x移动到z
        hanoi(n - 1, y, x, z);  // 把1 ~ n - 1个盘从y移动到z,用x作为中转
    }
}

int main()
{
    hanoi(1, 'X', 'Y', 'Z');
}

7.2.4  帕斯卡三角形(杨辉三角)

下面的数值被称为帕斯卡三角形,在我国则是著名的杨辉三角:

    1
    1    1
    1    2    1
    1    3    3    1
    1    4    6    4    1

三角形边界上的数都是1,内部的每个数是位于它上面的两个数之和。

利用递归我们可以很容易地把问题转换为这个性质:

假设f(row, col)表示杨辉三角的第row行的第col个元素,那么:

  1. f(row, col) = 1 (col = 1 或者 row = col),也就是递归的停止条件。

  2. f(row, col) = f(row - 1, col - 1) + f(row - 1, col),也就是上一行的两个相邻元素的和。

有了这个性质,我们的递归程序就容易写了。^_^

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   pascaltriangle.c
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-9 14:53:57
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

static long GetElement(const long row, const long col)
{
    // 每行的外围两个元素为1
    if ((1 == col) || (row == col))
        return 1;
    else
        // 其余的部分为上一行的(col - 1)和(col)元素之和
        return GetElement(row - 1, col - 1) + GetElement(row - 1, col);
}

static long PascalTriangle(const long n)
{
    int row;
    int col;

    for (row = 1; row <= n; ++row)
    {
        for (col = 1; col <= row; ++col)
            printf(" %4ld", GetElement(row, col));
        printf("\n");
    }
}

int main()
{
    PascalTriangle(5);
}