15. 计算 n！（非递归方法）

题目：

编写非递归函数计算 n！。测试你的代码。

思路：

首先，计算阶乘可以使用递归函数，代码如下：

1 long long factorial_recursion (int n) {
2     if (n <= 1) {
3         return 1;
4     } else {
5         return n * factorial_recursion ( n - 1 );
6     }
7 }

我们观察上面的递归函数，可以发现计算思路：从给定值进行倒推，直到计算出结果。这样做的好处是代码符合思路，好看简洁也容易写，但是问题在于，递归计算容易造成栈溢出和中间值溢出。

不用递归，自然就用迭代，递归倒着推，那迭代就正着算。

代码：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 long long factorial_recursion (int n) {
 5     if (n <= 1) {
 6         return 1;
 7     } else {
 8         return n * factorial_recursion ( n - 1 );
 9     }
10 }
11 
12 long long factorial (int n) {
13     int temp = 1;
14     for (int i = 1; i <= n; ++i) {
15         temp *= i;
16     }
17 
18     return temp;
19 }
20 
21 int main() {
22     int n;
23     cout << "Enter n : ";
24     cin >> n;
25     long long result = factorial_recursion (n);
26     cout << "result(recursion) : " << result << endl;
27 
28     result = factorial(n);
29     cout << "result(non-recursion) : " << result << endl;
30 
31     return 0;
32 }

代码中有几处需要说明：

第一，注意将局部变量 temp 初始化为 1，因为这是乘法。

第二，循环内控制变量从 1 开始，到 n 结束，中间 temp 作为累乘的计算结果。最后返回 temp。

第三，第一个函数是递归计算，第二个函数是迭代计算，放在一起有利于对比。