public class Multiply {

	/**
	 * 
	 * @param left >= 0
	 * @param right >= 0
	 * @return left * right
	 */
	//  f1
	public int linearRecMultiply(int left, int right ){
		if (left == 0) return 0;
		else return right + linearRecMultiply(left-1,right);
	}
	
	/**
	 * 
	 * @param left >= 0
	 * @param right >= 0
	 * @return left * right
	 */
	// f2
	public int linearTailRecMultiply(int left, int right, int product ){
		if (left == 0) return product;
		else return linearTailRecMultiply(left-1,right,product+right);
	}
	
	
	
	public int pow(int base, int exp){
		// any base to the 0 = 1
		if (exp == 0)  return 1;
		else if (exp%2==0)
			  // even exponent: x^2n = (x*x)^n
			  return pow(base*base,exp/2);
		      // odd exponent: x^(2n+1) = x*(x*x)^n
		else  return pow(base*base,exp/2)*base;
	}
		
	/**
	 * 
	 * @param left >= 0
	 * @param right >= 0
	 * @return left * right
	 */
	// f4
	public int egyptianRecMultiply(int left, int right){
		if (left == 0) return 0;
		else if (left%2 == 0)
			 return egyptianRecMultiply(left/2,right*2);
		else return egyptianRecMultiply(left/2,right*2) + right;
	}
	

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO show recursion, tail recursion and equivalent iteration
		Multiply M = new Multiply();
		int product;
	    product = M.linearRecMultiply(5,19);
	    System.out.println("Linear recursive multiply: 5 * 19 = " + product);

		product = M.linearTailRecMultiply(5,19,0);
		System.out.println("Linear tail recursive multiply: 5 * 19 = " + product);
		product = M.egyptianRecMultiply(19,5);
		System.out.println("Egyptian recursive multiply: 19 * 5 = " + product);
		
		System.out.println("2^5=" + M.pow(2,5));
		System.out.println("5^2=" + M.pow(5,2));
	}
	
}