主观题：经典递归问题

所谓递归，是指一个函数调用自己。

请编程实现几个经典的递归函数。

（1）阶乘

$$
fact(n) = \begin{cases} 1, & n \le 1,\\ n \times fact(n-1), & n>1. \end{cases}
$$

（2）自然数的和

$$
sum(n) = \begin{cases} 1, & n=1,\\ n + sum(n-1), & n>1.\end{cases}
$$

有人说 $1+2+3+\cdots = -\frac{1}{12}$，可惜计算机没法验证它 :-)

（3）斐波那契数列

$$
fib(n) = \begin{cases} 0, & n=0,\\ 1, & n=1,\\ fib(n-1)+fib(n-2), & n>1. \end{cases}
$$

（4）快速幂

$$
power(x,n) = \begin{cases} 1, & n=0,\\ x, & n=1,\\ power(x^2,\frac{n}{2}), & n>2, n \text{ 是偶数},\\ x \times power(x,n-1), & n>2, n \text{ 是奇数.} \end{cases}
$$

（5）最大公约数

$$
gcd(m,n) = \begin{cases}m, & n=0,\\ gcd(n, m\%n), & n \ne 0.\end{cases}
$$

函数原型如下：
c
// 递归计算 n 的阶乘
long long fact(int n);
// 递归计算 1+2+...+n
int sum(int n);
// 递归计算斐波那契数列第 n 项
int fib(int n);
// 递归计算 x 的 n 次幂
double power(double x, int n);
// 递归计算 m 和 n 的最大公约数
int gcd(int m, int n);


程序运行结果：


fact(20) = 2432902008176640000
sum(100) = 5050
fib(40) = 102334155
power(3.14159, 100) = 5.18741E+49
gcd(9527, 6553) = 1









答案：（1）先用伪代码描述每个问题的思路，然后实现之。

（2）编写主函数进行简单测试。