尾递归
每次都使用1个stack， 不会造成 栈溢出
大多数并没有优化
java 会优化
def factn(x):
return factn_iter(x, 1)
def factn_iter(x, product):
if x == 1:
return product
return factn_iter(x-1, x * product)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| package realtest;
import java.math.BigInteger;
/**
* @author peterjiao
* @date 2018/4/12
*/
public class TRecursion {
private BigInteger fact(int x){
if (x == 1){
return BigInteger.ONE;
}
return fact(--x).multiply(BigInteger.valueOf(x));
}
private BigInteger nfact(int x){
return nfactInter(x, BigInteger.ONE);
}
private BigInteger nfactInter(int x, BigInteger res){
if (x == 1){
return res;
}
return nfactInter(--x, res.multiply(BigInteger.valueOf(x)));
}
public static void main(String[] args) {
// BigInteger fact = new TRecursion().fact(10000);
// System.out.println(fact.toString());
BigInteger fact = new TRecursion().nfact(10000);
System.out.println(fact.toString());
}
}
|
