简介

你去找银行经理办事。

• 经理 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 */
}

例 1

计算阶乘 $n!$。

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

$$f(n)=\{\begin{array}{ll}1& n=0\\ f(n-1)\times n& n\ge 1\end{array}$$

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$。

例 2

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

$$f(n)=\{\begin{array}{ll}1& n=1,2\\ f(n-1)+f(n-2)& n\ge 3\end{array}$$

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