1 递归简论
需求：求出f(x)=2f(x-1)+x²的值。满足f(0)=0
public class Recursion {
// 需求： 求出f(x)=2f(x-1)+x²的值。满足f(0)=0
public static void main(String[] args) {
int f = f(1);
System.out.println(f);
}
public static int f(int x){
// 1 当x=1的时候f(1)=1 f(0)=0 f(2)=2f(1)+4=6
if(x==0)
return x;
return 2*f(x-1)+x*x;
}
}像上面的情况来说。我们知道f(0)=0;如果不知道这个情况，那么程序将不会计算出来。这种情况称之为基准情况，也就是说不需要经过递归而直接就可以计算出来。这就是基准情况。
接着我们再来看一个情况：如下代码所示。
public static int bad(int n){
if(n==0)
return 0;
return bad(n/3+1)+n-1;
}Exception in thread “main” java.lang.StackOverflowError
at com.gosaint.firstChapter.Introduction.Recursion.bad(Recursion.java:25)
at com.gosaint.firstChapter.Introduction.Recursion.bad(Recursion.java:25)
at com.gosaint.firstChapter.Introduction.Recursion.bad(Recursion.java:25)
程序出现了栈溢出。这是因为没有基准情况的。当n=1,此时bad(1)。但是bad(1)的值不知道，因此无法继续递归下去。也就是说，递归必须要满足的条件:
a 必须存在基准情况
b 能够持续不断的进行单方向的循环
需求：计算 一个数N中的二进制中1的个数：
计算说明：
1 对于一个数，首先将其转换为二进制，对于其中1或者0的个数分别可以如下的计算：
n&(n-1):其中计算1的个数
n|(n+1):其中计算出0的个数
详细的解释下：如9的二进制是：1001。其中的1的个数为2。9&8的结果是1000。消除了右边的1。继续循环消除。从而得到1的个数。
2 对于一个奇数而言，其中二进制中1的个数为n/2的数中二进制的个数加1
递归的方式计算一个数中二进制中1的个数
public static int binarySystem(int N){
if(N%2!=0){
return binarySystem(N/2)+1;
}else {
// 如果N为偶数，二进制中1的个数计算如下：
int n;
for ( n=0;N>0;n++){
N&=(N-1);
}
return n;
}
}直接进行计算，不适用递归的方式
/**
* 由于n&(n-1)的这种方式可以直接计算，因此可以不用使用递归的方式操作
* @param N
* @return
*/
public static int binarySystem02(int N) {
int n;
for (n = 0; N > 0; n++) {
N &= (N - 1);
}
return n;
}