递归

递归的定义：参见 递归.

你去找银行经理办事.

• 经理 A：不关我的事. 找经理 B.

• 经理 B：不关我的事. 找经理 A.

于是你在两个经理之间往返了一整天. 在程序中，该行为称作「递归」.

函数 f() 在内部调用了自己.

void f() {
    /* Do something */
    f();
}

这和以下死循环等价.

while (true) {
    /* Do something */
}

这类似于两个银行经理的情况.

void A() {
    B();
}

void B() {
    A();
}

合法的递归需要边界条件，使函数在恰当的时机停止.

void f() {
    if (.../* 边界条件 */)
        return;
    /* Do something */
    f();
}

这和以下循环等价.

while (.../* 边界条件 */) {
    /* Do something */
}

计算阶乘 $n!$.

$f(n)=n!$ 可以定义为

$$f(n)= \begin{cases} 1 & n=0 \\ f(n-1)\times n & n\geq1 \end{cases}$$

int f(int n) {
    if (n == 0)
        return 1;
    return f(n - 1) * n;
}

运行 f(3):

• A：来人，计算 $f(3)$.
  • B：来人，计算 $f(2)$.
    • C：来人，计算 $f(1)$.
      • D：来人，计算 $f(0)$.
        • E：报告，$f(0)=1$.
      • D：报告，$f(1)=f(0)\times 1=1$.
    • C：报告，$f(2)=f(1)\times 2=2$.
  • B：报告，$f(3)=f(2)\times 3=6$.
• A：报告，$f(3)=6$.

计算斐波那契数列的第 $i$ 项.

$$f(n)= \begin{cases} 1&n=1,2\\ f(n-1)+f(n-2)&n\geq 3 \end{cases}$$

int f(int n) {
    if (n == 1 || n == 2)
        return 1;
    return f(n - 1) + f(n - 2);
}