Java 算法基础 -递归

       递归对于算法来说算是基础的知识了, 最近在看<数据结构与算法分析 java语言描述> ,遇到相关递归的知识, 故在网络中找点资料,现记录下来. 如有侵权,请告知.

 

/**
	 * 阶乘的例子。其实递归递归，从字面上解释就是在方法本身调用自己的方法，或者间接调用；看上面的程序，拿multiply(5)来说：
	 *  n=5;执行 5*multiply(4); 
	 *-------------------- 
	 *这时候看multiply(4) 
      n=4 执行 4*multiply(3); 
      ------------------- 
      看multiply(3) 
      n=3,执行 3*multiply(2); 
      --------------- 
	  mulitply(2); 
	  n=2 执行 2*mulitply(1); 
	  这时候，return 1;往上返回 
	  2*1向上返回 
	  3*(2*1)向上返回 
	  4*（3*（2*1）） 向上返回 
	  5*（4*（3*（2*1）） ） = 120 
	所以程序输出120; S
	这事简单的递归的例子；所以可以看出来递归的关键得有递归出口(本体的If语句)，还有递归方法
	 * @param n
	 * @return
	 */
	public static int multiply(int n){
		if(n==1||n==0){
			return n;
		}else{
			return n*(multiply(n-1));
		}
	}
	
	
	/**
	 * 计算二进制中1的个数，
	 * N为奇数，其1的个数等于N/2二进制中表示1的个数加1
	 * 例子:
	 * num=13
	 * 1.getBinary(13/2=6)+1;   调用 getBinary(6/2=3)+1 返回2+1 =3
	 * 2.getBinary(6/2=3); 进入方法 ， 调用 getBinary(1)+1 =2;
	 * 3.getBinary(1)+1;  getBinary(1) 返回1 ， getBinary(1)+1  实际返回2
	 *  从     步骤3返回 1+1;
	 *  再返回到步骤2 ,没有做运算
	 *  再返回到步骤1 
	 * @param num
	 * @return
	 */
	public static int getBinary(int num){
		if(num==1)
			return 1;
		if(0==num%2){//是否为偶数
			return getBinary(num/2);
		}else{
			return getBinary(num/2)+1;
		}
	}
	
	/**
	 * 利用位移来解决  n>>1 右移一位，相当与 n/2
	 * @param n
	 * @return
	 */
	public static int getBinary2(int n){
		if(n==0){
			return n;
		}
		//为偶数 
		if(n%2==0){
			return getBinary2(n>>1);
		}else{
			//若N是奇数...等于N/2的二进制中1的个数加1
			return getBinary2(n>>1)+1;
		}
	}