求两个数的最大公约数

1
2
3
4
5
6
7
8
long gcd(long m, long n) {
while (n != 0) {
long ren = m % n;
m = n;
n = ren;
}
return m;
}

幂运算

时间复杂度为O(logN)的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 求幂运算
*
* @param x
* 底数
* @param n
* 指数
* @return 结果
*/
long pow(int x, int n) {
if (n == 0) {
return 1;
}
if (n % 2 == 0) {
return pow(x * x, n / 2);
} else {
return pow(x * x, n / 2) * x;
}
}

阶乘

传统递归版:

1
2
3
long fab(n) {
return n==1 ? 1 : n * fab(n-1);
}

尾递归版:

尾递归: 避免每一次递归都在堆栈中保存一个局部变量(普通递归会在每个栈中存储中间值n)。性能更优,可防止内存溢出。

1
2
3
4
5
6
7
long fab(n) {
return fab(n,1);
}

long fab(n,a) {
return n==1? a : fab(n-1,n*a);
}