javascript算法集：阶乘
阶乘 方法一（递归）
|
1
2
3
4
5
6
7
8
9
10
11
12
|
/*
* 阶乘
* @param {number} n 需要求的阶乘
* @return {number} 阶乘值
*/
function factorialize1(n){
if(typeof n !== 'number') throw new Error('参数必须为整整')
if(n === 1) return 1;
// 建议不要使用 arguments.callee，目前已经废弃了。
return n * factorialize1(n - 1);
}
|
PS：上面代码是一个阶乘函数，计算n的阶乘，最多需要保存n个调用记录，复杂度 O(n) 。
递归非常耗费内存，因为需要同时保存成千上百个调用帧，很容易发生“栈溢出”错误（stack overflow）。
阶乘 方法二（ES6尾调用优化）
（递归优化版）
|
1
2
3
4
5
6
7
8
9
10
11
12
|
/*
* 阶乘
* @param {number} n 需要求的阶乘
* @return {number} 阶乘值
*/
function factorialize2(n, total = 1){
if(typeof n !== 'number' || typeof total !== 'number') throw new Error('参数必须为整整')
if(n === 1) return total;
return factorialize2(n - 1, n * total)
// f(3) => f(2, 3 * 2) => f(1, 6) => 6
}
|
PS：ES6尾调用优化但对于尾递归来说，由于只存在一个调用帧，所以永远不会发生“栈溢出”错误。
尾调用（Tail Call）是函数式编程的一个重要概念，本身非常简单，一句话就能说清楚，就是指某个函数的最后一步是调用另一个函数。
阶乘 方法三（循环）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
/*
* 阶乘
* @param {number} n 需要求的阶乘
* @return {number} 阶乘值
*/
function factorialize3(n){
if(typeof n !== 'number') throw new Error('参数必须为整整')
if(n === 1) return 1;
let total = 1;
while(n>1){
total = n * total;
n--;
}
return total;
}
|
测试：factorialize1(3) // 6
THE END
