什么是递归算法？
这是个人理解，如有问题，还请多多指教。。。递归就是按照找到一个退出递归的出口，其余的部分一直按照某种规律执行，自己调用自己的方式执行代码。
递归的优势？
这也是个人理解，如有问题，还请多多指教。。。递归其实就是把一个大问题化成一个小问题，大事化小，小事化了的方式，而且递归与for循环相比的话，他是可以记录中间过程值的，每一次后一步调用都能直接获取前一步的值，如果以后再哪个环节想要使用的话是可以直接使用的，不需要再次进行计算。
用递归实现以上两算法题。
- 实现从0-n的加法：
描述思路：加法很简单啦，前面所有数量的和加上自己即可啦，一般这种情况只有正数；
代码实现：
static int sum(int n){
if (n == 0)
return 0;
if (n == 1)
return 1;
return sum(n - 1) + n;
// 如果分正负
//if(n > 0）{
// return sum(n - 1) + n;
//} else{
// return sum(n + 1) + n;
//}
}
- 实现整数n的阶乘：
首先描述一下思路，整数的阶乘，那么意味着整数分为正整数和负整数，那么我们需要分两种情况讨论，当n是正数的时候，f(n) = n f(n -1), 但是当n为负数的时候f(n) = n f(n + 1)；
看看代码实现
static int f(int n){
if (n == 0){
return 1;
} else if (n > 0){
return f(n - 1) * n;
} else if (n < 0){
return f(n + 1) * n;
}
return -1;
}
- 实现数字A的n次方（n 可负可正）
首先描述一下大众思路，在印象里面，A的多少次方就是多少个A相乘啊，那如果n是负数呢？那就是绝对值个A相乘，最后取倒数。
下面看看普通实现方式的代码
static double accelarateN(int a, int num){
if (a == 0)
return 0;
if (num >= 0){
return bZ(a, num);
} else if (num < 0){
// num = Math.abs(num);
// return 1 / bZ(a, num);
return 1 / sZ(a, num);
}
return -1;
}
static double bZ(int a, int n){
if (n == 0){
return 1;
}
return a * bZ(a, n -1);
}
static double sZ(int b, int n){
if (n == 0)
return 1;
return b * sZ(b, n + 1);
}
其实看完上面的代码，会发现，这样就可以实现功能了，但是，我们可以想一想，如何更好的实现这个算法，求一个数的整数次方，那么很明显，这里面有个重复的过程，那就是一个数的N次方等于这个数的（N/2）次方的平方，那么代码就可如下写：
static double accPower(int base, int exponent){
double result = 1;
int n = exponent;
exponent = Math.abs(exponent);
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
result *= accPower(base, exponent >> 1) * accPower(base, exponent >> 1);
if ((exponent & 1) == 1){
result = base * result;
}
if (n < 0){
result = 1 / result;
}
return result;
}
怎么样，结果是一样的，但是运算速度快了很多啦。。。每次都以次方的形式递减。。。