No testdata at current.

在前面的习题里，我们看到了这样的程序：

#include <iostream>
using namespace std;
int fun1(int n) {
	if (n <= 1) {
		return 1;
	}
	return n;
}
int fun2(int n) {
	if (n <= 1) {
		return 1;
	}
	return n * fun1(n - 1);
}
int fun3(int n) {
	if (n <= 1) {
		return 1;
	}
	return n * fun2(n - 1);
}
int fun4(int n) {
	if (n <= 1) {
		return 1;
	}
	return n * fun3(n - 1);
}
int main() {
	int n;
	cin >> n;
	cout << fun4(n) << endl;
	return 0;

}

借助这个程序，我们可以计算 0 到 5 之间每个数的阶乘。如果要计算任意正整数 n 的阶乘呢？

---

很显然，我们不能定义无限多个函数，不然这个程序就要“长度爆炸”了。

int fun1(int n) {
	if (n <= 1) {
		return 1;
	}
	return n;
}
int fun2(int n) {
	if (n <= 1) {
		return 1;
	}
	return n * fun1(n - 1);
}
int fun3(int n) {
	if (n <= 1) {
		return 1;
	}
	return n * fun2(n - 1);
}
...

那么，如果我们通过如下的方式：

int fun(int n) { 
    if (n <= 1) { 
        return 1; 
    } 
    return n * fun(n - 1); 
} 

是不是就可以了？在这个函数中，就用到了函数的“递归调用”。什么叫递归调用呢？

---

所谓函数的递归调用，是指一个函数调用自身从而产生循环的过程。例如，对于刚才的程序：

int fun(int n) {
    if (n <= 1) { 
        return 1; 
    } 
    return n * fun(n - 1); 
} 

我们把fun(5)的递归过程描述出来：

---

也许你会有这样的疑问：为什么我要在fun函数里的一开始加上那个条件分支呢？下面这个程序有什么问题呢？

int fun(int n) { 
    return n * fun(n - 1); 
} 

程序调用fun(3)以后，会执行如下的过程：

调用fun(3)

计算3 * fun(2)，调用fun(2)

计算2 * fun(1)，调用fun(1)

计算1 * fun(0)，调用fun(0)

计算0 * fun(-1)，调用fun(-1) ......

整个函数就会无限地反复调用下去了。我们将递归过程中用来结束递归的条件分支称为递归的边界条件。

在递归函数的实现里，边界条件是非常重要的，如果没有正确的写出边界条件，可能会导致程序永远地执行下去。

---

递归与作用域

在一个带有递归过程的函数中，如果定义了变量，那么这个变量在递归的过程中，作用域会是怎样的呢？

int fun(int n) {
    if (n == 1) { 
        return 1; 
    } 
    int a = 0; 
    a++; 
    return 2 * fun(n - 1); 
}

当我们调用fun(3)时，会经过如下的过程：

在fun(3)里定义的a，作用域为红色框；在fun(2)里定义的a，作用域为蓝色框；在fun(1)里定义的a，作用域为绿色框。它们之间互不干扰，因此，既不会出现变量名冲突的情况，也不会出现同一个变量a的值被反复累加的情况。