BBS水木清华站∶精华区

发信人: ax.bbs@bbs.ee.nthu.edu.tw. (athena), 信区: test
标  题: 星星流讲座 0041
发信站: ☆清华电机☆ (Sat Jul  8 17:37:54 1995)

第 6 讲之 4            函数
                        Topic: Recursion (1)

我们前面提到过，呼叫一个函数，就是把程式的控制权交给函数，
当函数执行完之後，再把控制权交回来。例如：

void main (void)                        ↓ main() 开始执行
{                                       ↓
    /* main() start here */             ↓
    foo ();                              —┐ 把控制权交给 foo()
    /* main() continue here */       ┌→  │
}                                    │    │
                                     │  —┘
void foo (void)                      │ ↓ foo() 开始执行
{                                    │ ↓
    /* foo() work here */            │ ↓
}                                    └— 执行完毕，把控制权还给 main()

那如果我们在函数之中呼叫函数本身呢？例如：

void foo (void)
{
    foo ();
}

这时候控制权的流向就会如下：

        (第一个) foo()
                  ↓ 呼叫 foo()，把控制权交给 foo()
        (第二个) foo()
                  ↓ 呼叫 foo()，把控制权交给 foo()
        (第三个) foo()
                  ↓ 呼叫 foo()，把控制权交给 foo()
                  ：
                  ：

控制权交出去之後就不会回来了，这是一种很危险的动作，其实这就是一种
错误的递回 (recursion)。什麽叫做递回呢？递回就是函数直接或间接地叫
用自己。什麽时候我们会用的上递回函数呢？一个常见的例子是求某数的阶
乘：

int factor (int n)
{
    if (n < 0)
        return factor (n + 1) * n;
    else if (n > 0)
        return factor (n - 1) * n;
    else                                /* n == 0 */
        return 1;                       /* 0! = 1 */
}

我们知道

        n * (n - 1)! if n > 0
   n! = n * (n + 1)! if n < 0
        1            if n = 0

直觉地写成程式就变成了上面 factor() 这个函数 (当然，这个函数在实
际上并不实用，实用的阶乘函数并不容易作出来)，这是一个标准的递回
的写法。递回函数有三大要件：起始条件、递回终止条件、递回本体。
在我们上面的例子中，起始条件就是参数 n (要求 n 的阶乘)，而递回
终止条件则是 n == 0 (当 n = 0 时传回 1，不再继续递回)，递回的本
体是 factor (n + 1) * n 及 factor (n - 1) * n 这两个实际呼叫递回
函数的部份。

我们现在花点时间来 trace 一下 factor (3) 的动作：

        呼叫 factor (3)
             │
         □  │
             ↓
       return factor (2) * 3    □传回 2*3=6，函数结束
                    │      □—————————┐
   □呼叫 factor(2) │                          │
                    ↓                          │
            return factor (1) * 2       □传回 1*2=2 给 factor(3)
                      │          □————————┐
     □呼叫 factor(1) │                            │
                      ↓                            │
               return factor (0) * 1      □传回 1*1=1 给 factor(2)
                        │          □—┐
       □呼叫 factor(0) │              │
                        ↓              │
                     return 1 —————┘ □传回 1 给 factor(1)

为什麽我们说终止条件是 n == 0 呢？因为它是递回函数不再继续呼叫
自己的判断条件，所以叫做递回终止条件。每一个递回函数都必须设定
递回终止条件，至於递回终止条件要如何找出来呢？它通常是数学中所
谓的边界条件 (boundry condition)，只要多多练习大概就能一眼就看
出来了。
--
本文原作者为徐振家，原作刊载於星星神教总坛 ☆清华电机☆ test 板。
你可以以电子文件的形式将本文自由流传於台湾学术网路，但必须包含此版权声明。
原作者依中华民国著作权法之规定，享有本文之著作权，请勿抄袭以免触法。
未经授权任何人不得以任何形式对本文做任何修改及商业上之应用。
其他网路的转载或其他用途的应用，请先知会作者，并取得其同意。
对本文有任何疑问或意见请 mail 给 ax.bbs@bbs.ee.nthu.edu.tw，谢谢。